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

Minoux, M.; Pinson, E.

RAIRO, Rech. Opér. 21, 349-364 (1987).

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

MSC:

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

Keywords:

exact solution; graph partitioning; branch-and-bound; sharp bounds; large-scale set partitioning; large-scale Boolean linear programming; continuous relaxation; column generation subproblem; quadratic pseudo- Boolean minimization; max-flow; polynomial solvability