Set Covering by an All Integer Algorithm: Computational Experience

ABSTRACT

Computational experience with a modified linear programming method for the inequality or equality set covering problem (i.e. minimize cx subject to Ex ≥ e or Ex = e, xi = 0 or 1, where E is a zero-one matrix, e is a column of ones, and c is a nonnegative integral row) is presented. The zero-one composition of the constraint matrix and the right-hand side of ones suggested an algorithm in which dual simplex iterations are performed whenever unit pivots are available and Gomory all integer cuts are adjoined when they are not. Applications to enumerative and heuristic schemes are also discussed.

REFERENCES

• 1: ANDREW, G , HOFFMAN, T., AND KRBEK, C. On the generalized set covering problem ORSA/TIMS Conf., May 1968.
• 2: BALAS, E., AND PADBERG, M. On the set covering problem Manag. Sci. Res. Rep 197, Carnegie-Mellon U , Pittsburgh, Pa., Feb 1970; rev. June 1971; also Oper Res. (to appear).
• 3: BXLINSKI, M. L. Integer programming: methods, uses, computation. Manag. Sci. 12, 3 (Nov. 1965), 253-313.
• 4: GARFINKEL, R. S,, AND NEMHAUSER, G. L. The set-partitioning problem: set covering with equahty constraints. Oper. Res. 17 (1969), 848-856.
• 5: GOMORY, R.E. All-integer integer programming algorithm IBM Res Ctr Rep. RC-189, Jan. 1960; also in Industrial Scheduling, J. F. Muth and E L. Thompson, Eds., Prentice- Hall, Englewood Cliffs, N J., 1963, pp. 193-206.
• 6: LEMKFE, C., SALKIN, H., AND SPIELBERG, K. Set covering by single branch enumeration wit linear programming subproblems. IBM N. Y. ScI. Ctr. Rep. 320-2979, Oct. 1969; also in Oper. Res. 19 (1971), 998-1022
• 7: Rums, J. A technique for the solution of massive set covering problems, with application to airline crew scheduling. IBM Philadelphia Sci. Ctr. Rep. 320-3004, Sept. 1971
• 8: SALKIN, H. M, AND KONCAL, R. A Dual all-integer algorithm (in revised simplex form) for the set covering problem. Dep. of Oper. Res. Tech. Memo 250, Case Western Reserve U., Cleveland, Ohio, Aug. 1971.
• 9: SALKIN, H. M., AND KONCAL, R. A pseudo dual all-integer algorithm for the set covering problem. Dep. of Oper. Res. Tech. Mere. 204, Case Western Reserve U., Cleveland, Ohio, Nov. 1970.

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.6 Optimization
          Subjects: Integer programming

General Terms:
Algorithms, Measurement, Performance, Theory