Pivot and Complement--A Heuristic for 0-1 Programming

Egon Balas and Clarence H. Martin
Additional contact information
Clarence H. Martin: Ohio State University

Management Science, 1980, vol. 26, issue 1, 86-96

Abstract: Pivot and Complement is a heuristic for finding approximate solutions to 0-1 programming problems. It uses the fact that a 0-1 program is equivalent to the associated linear program with the added requirement that all slack variables, other than those in the upper bounding constraints, be basic. The procedure starts by solving the linear program; then performs a sequence of pivots aimed at putting all slacks into the basis at a minimal cost; finally, it attempts to improve the 0-1 solution obtained in this way by a local search based on complementing certain sets of 0-1 variables. The computational effort involved in the procedure is bounded by a polynomial in the number of constraints and variables. For the 92 test problems with 5 to 200 constraints and 20 to 900 variables on which the procedure was run, the time used to solve the linear program on the average considerably exceeded the time used for everything else. As to the quality of the solutions obtained, in 45 cases, or 49% of the total, the procedure found an optimal solution; for the capital budgeting problems (positive coefficients everywhere), the solution found was on the average within 0.15% of the optimum; for 81 of the 92 problems, it was within 1% of the optimum; and only in 1 case did the procedure not find a feasible solution.

Keywords: programming: integer algorithms; heuristic (search for similar items in EconPapers)
Date: 1980
References: Add references at CitEc
Citations: View citations in EconPapers (28)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.26.1.86 (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:ormnsc:v:26:y:1980:i:1:p:86-96

Access Statistics for this article

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