An Additive Algorithm for Solving Linear Programs with Zero-One Variables
Egon Balas · Operations Research · 1965
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 2n 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.
Cited by 702 works. doi:10.1287/opre.13.4.517
Authors
References
- Linear Programming and Extensions
- Outline of an algorithm for integer solutions to linear programs
- Discrete-Variable Extremum Problems
- On the Solution of Discrete Programming Problems
- An Algorithm for the Traveling Salesman Problem
- Management Models and Industrial Applications of Linear Programming
- A Linear Programming Approach to the Cutting-Stock Problem
- An Automatic Method for Solving Discrete Programming Problems
- A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
- AN ALL-INTEGER INTEGER PROGRAMMING ALGORITHM