On the Set-Covering Problem: II. An Algorithm for Set Partitioning

Egon Balas and Manfred Padberg
Additional contact information
Manfred Padberg: International Institute of Management, Berlin, West Germany

Operations Research, 1975, vol. 23, issue 1, 74-90

Abstract: In an earlier paper [ Opns. Res. 20 1153–1161 (1972)] we proved that any feasible integer solution to the linear program associated with the equality-constrained set-covering problem can be obtained from any other feasible integer solution by a sequence of less than m pivots (where m is the number of equations), such that each solution generated in the sequence is integer. However, degeneracy makes it difficult to find a sequence of pivots leading to an integer optimum. In this paper we give a constructive characterization of adjacency relations between integer vertices of the feasible set that enables us to generate edges (all, if necessary) connecting a given integer vertex to adjacent integer vertices. This helps overcome the difficulties caused by degeneracy and leads to a class of algorithms, of which we discuss two.

Date: 1975
References: Add references at CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.23.1.74 (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:23:y:1975:i:1:p:74-90

Access Statistics for this article

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