Set Covering with Cutting Planes from Conditional Bounds.
Abstract
A conditional lower bound on the minimand of an integer program is a number which would be a valid lower bound if the constraint set were amended by certain inequalities, also called conditional. If such a conditional lower bound exceeds some known upper bound, then every solution better than the one corresponding to the upper bound violates at least one of the conditional inequalities. This yields a valid disjunction, which can be used to partition the feasible set, or to derive a family of valid cutting planes. In the case of a set covering problem, these cutting planes are themselves of the set covering type. The family of valid inequalities derived from conditional bounds subsumes as a special case the Bellmore-Ratliff inequalities generated via involontery bases, but is richer than the latter class and contains considerably stronger members, where strength is measured by the number of positive coefficients. The paper discusses two algorithms based on cutting planes from conditional bounds. None of them uses the simplex method (though a variant based on the latter is also feasible). Some computational experience is presented. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1977
- Accession Number
- ADA037616
Entities
People
- Egon Balas
Organizations
- Carnegie Mellon University