Discrete Programming by the Filter Method
Egon Balas · Operations Research · 1967
In this paper (section 1) a two-phase procedure, the filter method or accelerated additive algorithm, is proposed for solving linear programs with zero-one variables. In Phase I an auxiliary problem is constructed that, in Phase II, is used to “filter” the solutions to which the tests of the additive algorithm are to be applied. The filter method is then extended (section 2) by J. F. Benders’ partitioning procedure to the mixed-integer zero-one case, as well as to general integer and mixed-integer programs. Finally, a specialized version of this method is used (section 3) to tackle a general machine-sequencing model, formulated as the problem of finding a minimaximal path in a disjunctive graph.
Cited by 149 works. doi:10.1287/opre.15.5.915
Authors
References
- Optimal two‐ and three‐stage production schedules with setup times included
- An Algorithm for the Traveling Salesman Problem
- Partitioning procedures for solving mixed-variables programming problems
- Branch-and-Bound Methods: A Survey
- An Additive Algorithm for Solving Linear Programs with Zero-One Variables
- Integer Programming: Methods, Uses, Computations
- A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
- On the Significance of Solving Linear Programming Problems with Some Integer Variables
- Integer Programming by Implicit Enumeration and Balas’ Method
- Algorithms for Solving Production-Scheduling Problems