Research Reports from the Department of Operations
Document Type
Report
Publication Date
11-1-1970
Abstract
A modified linear programming method for the inequality or equality set covering problem (i.e., minimize cx subject to Ex ≥ b or Ex = b, where E is a zero-one matrix, b is a column of ones, and c is a nonnegative integral row) is presented. The "almost unimodular" property of the (zero-one) constraint matrix suggested an algorithm in which one performs (dual) simplex interactions whenever unit pivots are available and adjoin Gomory all-integer cuts when they are not. Finiteness, time reducing criteria, the elimination of roundoff errors, and applications to enumerative schemes are discussed. Preliminary computational experience, being very encouraging, is presented.
Keywords
Operations research, Integer programming, Linear programming, Set theory, Algorithms, Computational complexity, Mathematical optimization, Combinatorial optimization
Publication Title
Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 204
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 Pseudo Dual All-Integer Algorithm for the Set Covering Problem" (1970). Research Reports from the Department of Operations. 451.
https://commons.case.edu/wsom-ops-reports/451