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

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


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
Full Text: DOI EuDML