Computational experience with a modification of an algorithm by Hammer and Rudeanu for 0-1 linear programming

ABSTRACT

The acceleration algorithm by Hammer and Rudeanu (1) for linear zero-one programming problem was tested with several problems of small and medium size involving up to 300 variables on an IBM 360/67. The problems were chosen at random. Several modifications of the algorithm are discussed and computational experience is collected. The results shown indicate that the algorithm is computationally competitive with the other known algorithms using implicit enumeration. For all problems solved the first feasible solution is optimal. This supports the conjecture that the algorithm can be used as a procedure for finding a near optimal solution.

REFERENCES

• 1: Hammer, P. L. and Rudeanu, S., Boolean Methods in Operations Research and Related Areas, 1968, Springer Verlag, New York
• 2: 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]
• 3: Glover, F., "A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem", Opns. Res., 13, 879-919, 1965
• 4: František Fiala, Algorithm 449: solution of linear programming problems in 0-1 variables, Communications of the ACM, v.16 n.7, p.445-447, July 1973 [doi>10.1145/362280.362304]
• 5: Fleischman, B., "Computational Experience with the Algorithm of Balas" Opns Res., 15, 153-155, 1967
• 6: Freeman, R. J., "Computational Experience with a 'Balasian' Integer Programming Algorithm", Opns. Res., 14, 935-941, 1966
• 7: Peterson, C. C., "Computational Experience with Variants of the Balas Algorithm Applied to the Selection of R and D Projects", Mgmt. Sci., 13, 735-750, 1967
• 8: Rao, A., "Balas' and Glover's Algorithm: a Comparison", Paper, 23rd Nat. Meeting. Operations Research Soc. of Amer., Chicago, Nov. 1967
• 9: Balinski, M. L. and Spielberg, K., "Methods for Integer Programming: Algebraic, Combinatorial, and Enumerative", Progress in Operations Research, Vol. III, 195-292, 1969, John Wiley &Sons, Inc., New York

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms

General Terms:
Algorithms, Theory

Keywords:
Algorithms, Boolean techniques, Branch-and-bound techniques, Computational experience, Implicit enumeration, Linear programming, Operations research, Optimization theory, Zero-one variables