##
**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.

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 |