An Additive Algorithm for Solving Linear Programs with Zero-One Variables

Egon Balas

Operations Research, 1965, vol. 13, issue 4, 517-546

Abstract: An algorithm is proposed for solving linear programs with variables constrained to take only one of the values 0 or 1. It starts by setting all the n variables equal to 0, and consists of a systematic procedure of successively assigning to certain variables the value 1, in such a way that after trying a (small) part of all the 2 n possible combinations, one obtains either an optimal solution, or evidence of the fact that no feasible solution exists. The only operations required under the algorithm are additions and subtractions; thus round-off errors are excluded. Problems involving up to 15 variables can be solved with this algorithm by hand in not more than 3–4 hours. An extension of the algorithm to integer linear programming and to nonlinear programming is available, but not dealt with in this article.

Date: 1965
References: Add references at CitEc
Citations: View citations in EconPapers (34)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.13.4.517 (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:13:y:1965:i:4:p:517-546

Access Statistics for this article

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