A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations. (English) Zbl 0644.90061

Minoux, M.

RAIRO, Rech. Opér. 21, 105-136 (1987).

This paper exhibits and studies a large class of combinatorial optimization problems which can be formulated as very large size set covering/set partitioning problems whose linear relaxations are shown to be solved in polynomial time via generalized linear programming techniques. The class contains well-known problems such as simple plant location problems, partitioning the edges of a graph into forests, graph partitioning problem, the chromatic index problem and clustering problems arising in such contexts as locating public service stations, and new problems such as a k-center-sum problem, minimum weighted partitioning of a matroid with bases or independent subsets, minimum weighted partitioning with subsets belonging to the intersection of two matroids and packing the edge set or arc set of graph into cutsets.
All the problems listed here are NP-complete. Thus the generalized linear programming technique for their relaxation problems provides an efficient practical way of getting good lower bounds to them which are useful for exact solution methods like branch and bound algorithms. This paper also discusses two practical applications relating to this class: an optimization problem arising in satellite communications and crew scheduling problems in air line companies.

Reviewer: H.Kise

MSC:

90C10	Integer programming
90C27	Combinatorial optimization
90C06	Large-scale problems in mathematical programming
65K05	Numerical mathematical programming methods
90C05	Linear programming
90C90	Applications of mathematical programming
90B35	Deterministic scheduling theory in operations research
90B05	Inventory, storage, reservoirs
68Q25	Analysis of algorithms and problem complexity

Keywords:

column generation; very large size set covering; set partitioning; linear relaxations; generalized linear programming; plant location; forests; graph partitioning; chromatic index problem; clustering; k-center-sum; minimum weighted partitioning of a matroid; NP-complete; lower bounds; satellite communications; crew scheduling