Lower bounds to the graph partitioning problem through generalized linear programming and network flows. (English) Zbl 0657.90095

The general idea to find an exact solution of the well-known graph partitioning problem (GPP) is to construct an efficient branch-and-bound algorithm with sharp bounds; but the question how to find such good bounds is still open. In this excellent paper the author proposes a new approach to getting lower bounds for the solution of the GPP. The approach is based on a reformulation of GPP in its weighted version (positive weights assigned to the edges in the graph) as a large-scale set partitioning problem with, normally, a huge number of variables, i.e. a large-scale Boolean linear programming (LP) problem. There is no hope really to solve such a problem directly but its special structure allows to be exploited in a suitable manner. The author develops an approach to solve the continuous relaxation of the set partitioning problem (SPP) by generalized LP. A column generation subproblem which is the crucial part of solving the continuous relaxation of SPP by the generalized LP approach is formulated as a quadratic pseudo-Boolean minimization problem. It is shown in the paper how to reduce the quadratic pseudo- Boolean minimization problem to a max-flow problem in an appropriately constructed network. The polynomial solvability of the max-flow problem implies the polynomial solvability of the column generation subproblem and hence the polynomial solvability of the large scale continuous relaxation of SPP the exact solution of which could serve as a lower bound to the initial GPP. Analyzing the results obtained by computational tests the author suggests that “sharp bounds which are usually necessary to have branch-and-bound procedures work efficiently cannot be expected from the generalized LP approach to the GPP”. It seems that such a conclusion is rather preliminary because no results of using the proposed scheme combined with a branch-and-bound method to produce exact solutions of at least some classes of graph partitioning problems are presented.
Reviewer: V.G.Rumchev


90C35 Programming involving graphs or networks
05C35 Extremal problems in graph theory
90B10 Deterministic network models in operations research
90C27 Combinatorial optimization
68Q25 Analysis of algorithms and problem complexity
90C05 Linear programming
90C06 Large-scale problems in mathematical programming
90C09 Boolean programming
Full Text: DOI EuDML