Research Reports from the Department of Operations
Document Type
Report
Publication Date
8-1-1971
Abstract
In an earlier work ("A Pseudo Dual All-Integer Algorithm for the Set Covering Problem", Department of Operations Research Tech. Memo. No. 204, CWRU, Nov. 1970) the authors developed a composite dual simplex-Gomory all integer algorithm for the (inequality or equality) set covering problem (i.e., minimize cx subject to Ex >= e or Ex = e, xj = 0 or 1; where E is an m by n zero-one matrix, e is a column of ones, and c is a nonnegative integral row). Essentially the algorithm performs dual simplex iterations whenever unit pivots are available and it adjoins Gomory all integer cuts when they are not. In this way dual feasible all integer tableaux are maintained; optimality exists when primal feasibility is reached. Although this algorithm performed rather well, it required a working tableau of order n + 1 by m + n + 1. This meant that problems of only modest size could be solved. To overcome the storage problem a revised simplex form of the composite algorithm was developed. The details and computational results are presented in this report.
Keywords
Operations research, Integer programming, Linear programming, Set theory, Algorithms, Computational complexity, Combinatorial optimization
Publication Title
Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 250
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Salkin, Harvey M. and Koncal, Ronald D., "A Dual All-Integer Algorithm (In Revised Simplex Form) for the Set Covering Problem" (1971). Research Reports from the Department of Operations. 157.
https://commons.case.edu/wsom-ops-reports/157