The Set-Covering Problem: A New Implicit Enumeration Algorithm

Javier Etcheberry
Additional contact information
Javier Etcheberry: University of Chile, Santiago, Chile

Operations Research, 1977, vol. 25, issue 5, 760-772

Abstract: The set-covering problem is to minimize cx subject to A x ≧ e n over all binary n -vectors x . A is an m × n binary matrix and e n is an n -vector of 1's. We develop a new implicit enumeration strategy to solve this problem. The branching strategy is similar to the row partitioning strategy used by other authors in the partitioning problem. Simple and sharp bounds are obtained by relaxing the constraints of the associated linear program by attaching nonnegative multipliers to them. Good multipliers are obtained by using the subgradient optimization technique. Computational experience shows that these bounds are at least one order of magnitude more efficient than the ones obtained by solving the associated linear program with the simplex method. Computational results with this new implicit enumeration algorithm are encouraging. Problems with as many as 50 constraints and 100 variables were solved in the order of 100 seconds of CPU time on an IBM 360-67.

Date: 1977
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.25.5.760 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:25:y:1977:i:5:p:760-772

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().