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

TLDR

An algorithm is proposed for solving linear programs with variables constrained to take only one of the values 0 or 1. The algorithm begins with all variables set to zero and iteratively assigns ones to selected variables, exploring a small subset of the 2ⁿ combinations to find an optimal solution or prove infeasibility, using only additions and subtractions to avoid round‑off errors. Problems involving up to 15 variables can be solved with this algorithm by hand in not more than 3–4 hours.

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.