Further evidence for the analysis of algorithms for the zero-one programming problem

ABSTRACT

The purpose of this note is to report computational experience additional to that recently summarized by Gue et al., with two algorithms for the zero-one linear programming problem. An error in Gue's paper is corrected. The utility of one of the algorithms as a suboptimizer is indicated.

REFERENCES

• 1: Ronald L. Gue , Kenneth C. Cain , John C. Liggett, Analysis of algorithms for the zero-one programming problem, Communications of the ACM, v.11 n.12, p.837-844, Dec. 1968 [doi>10.1145/364175.364209]
• 2: LEMKE, C. E., AND SPIELBERG, K. Direct search algorithms for zero-one and mixed-integer programming. Oper. Res. 15, 5 (Sept.-Oct. 1967), 892-914.
• 3: LAWLER, E. L., AND BELL, M.D. A method for solving discrete optimization problems. Oper. Res. I4, 6 (Nov.-Dec. 1966), 1098-1112.
• 4: Joseph L. Balintfy, Menu planning by computer, Communications of the ACM, v.7 n.4, p.255-259, April 1964 [doi>10.1145/364005.364087]
• 5: GLOVER, F. A" multi-phase-dual algorithm for the zero-one integer programming problem. Oper. Res. 13, 6 (Nov.-Dee. 1965), 879-919.
• 6: GEOFFFRION, A. M. Integer programming by implicit enumeration and Balas' method. SIAM ReG. 9, 2 (Apr. 1967), 178-190.
• 7: J. L. Byrne , L. G. Proll, Algorithms: Algorithm 341: solution of linear programs in 0-1 variables by implicit enumeration, Communications of the ACM, v.11 n.11, p.782, Nov. 68 [doi>10.1145/364139.364171]
• 8: BYRNE, J. L. An assessment of recent algorithms for the zeroone programming problem. M. Se. Diss., U. Southampton, Sept. 1967.
• 9: BALAS, E. An additive algorithm for solving linear programs with zero-one variables. Oper. Res. 13, 4 (July-Aug. 1965), 517-546.
• 10: BYRNE, J. L., AND PROLL, L. G. Initialising Geoffrion's implicit enumeration algorithm for the zero-one linear programming problem. Comput. J. 15, 4 (Nov. 1969), 381-384.
• 11: GLOVER, F., AND ZIONTS, S. A note on the additive algorithm of Balas. Oper. Res. 13, 4 (July-Aug. 1965), 546-549.
• 12: LIGGETT, J. C. A general multiple choice formulation of an algorithm by Balintfy. Tech. Rep. No. CP-68004, Comput. Sci. Center, Southern Methodist U., Dallas, Texas, Mar. 1968.

INDEX TERMS

Keywords:
algorithms, integer programming, operations research, zero-one variables