Cutting Planes from Conditional Bounds for Generalized Set Covering Problems

Abstract

This paper reports on the development of special cutting planes for the generalized set covering problem, GSCP, which is a covering problem where the variables and the right-hand sides are allowed to have any positive integer value. Those inequalities are, actually, a generalization of the cutting planes derived from conditional bounds and originally presented by Balas (1980), for the set covering problem. More recently, Hall & Hochbaum (1985) have extended those results for the multicovering problem. The generalized inequalities that we derive for the GSCP arc proved to be of the covering type and, hence, keeping the structure of the problem constraints.