Cutting Planes from Conditional Bounds: A New Approach to Set Covering.

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 involutory bases, but is richer than the latter class and contains considerably stronger members, where strength is measured by the number of positive coefficients.