Research Reports from the Department of Operations
Document Type
Report
Publication Date
7-1-1973
Abstract
An algorithm for the classical set-covering problem with additional "base" constraints is presented. The "base" constrained set covering problem is: Minimize cx, subject to Ex ≥ e, xj = 0 or 1 (j = 1,...,n), and Bx ≤ d. Here E is an m by n matrix of zeros and ones, e is an m column of ones, c and d are nonnegative vectors, and B is a nonnegative array having row diagonal structure. The algorithm is basically a zero-one single branch enumeration with linear programming and other feasibility criteria. A "heuristic" is used which sometimes finds an initial solution to the base constrained set-covering problem. Computational results are given.
Keywords
Operations research, Algorithms, Linear programming, Combinatorial optimization, Mathematical optimization, Heuristic algorithms
Publication Title
Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 313
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Salkin, Harvey M. and Lin, Chien-Hua, "Computational Experience with an Enumerative Algorithm for the Set Covering Problem with Base Constraints" (1973). Research Reports from the Department of Operations. 86.
https://commons.case.edu/wsom-ops-reports/86