Publication | Closed Access
Set Covering and Involutory Bases
64
Citations
0
References
1971
Year
Mathematical ProgrammingEngineeringComputational ComplexityDiscrete OptimizationOperations ResearchCovering ProblemsSet CoveringCutting PlanesDiscrete MathematicsCombinatorial OptimizationComputational GeometryInteger OptimizationNew PropertiesCombinatorial ProblemExtremal Set TheoryComputer ScienceNew AlgorithmInteger ProgrammingMixed Integer OptimizationSet-theoretic TopologyPartially Ordered SetLinear Programming
The study develops a new algorithm for weighted set covering that employs strong cutting planes. The algorithm uses cutting planes that exclude both integer and noninteger solutions. New properties of weighted set covering problems are derived, including the existence of an optimal involutory basis, and computational results demonstrate the algorithm’s effectiveness.
Some new properties associated with the special class of integer programs known as weighted set covering problems are derived. While it is well known that an optimal integer solution to the set covering problem is a basic feasible solution to the corresponding linear program, we show that there exists an optimal basis which is involutory (i.e., B = B −1 ). This property and others are used to develop a new algorithm which uses strong cutting planes. The cutting planes are strong in the sense that they exclude both integer and noninteger solutions. Computational experience is presented.