A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations

The paper introduces and studies a whole class of combinatorial problems which can be formulated as very large size set covering/set partitioning problems whose linear relaxations are either solvable in polynomial time via the Ellipsoid Algorithm, or simply efficiently solvable by using generalized linear programming techniques. An extension to set packing problems is also considered. This class is shown to contain both already well-known combinatorial problems as well as a number of apparently new ones, stated here for the first time. Moreover it is shown that, for all these problems, proving they belong to this class automatically provides new attractive computational approaches. Two recent important practical applications of these methods are mentioned: one concerns an optimization problem arising in satellite communications; the other concerns crew scheduling problems in airline companies.