Accession Number:

AD0767067

Title:

Computational Experience with an Enumerative Algorithm for the Set Covering Problem with Base Constraints.

Descriptive Note:

Technical memo.,

Corporate Author:

CASE WESTERN RESERVE UNIV CLEVELAND OHIO DEPT OF OPERATIONS RESEARCH

Personal Author(s):

• Salkin,Harvey M.
• Lin,Chien H.

Report Date:

1973-07-01

Pagination or Media Count:

19.0

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 or B, x sub j 0 or 1 j 1,...,n, and Bx or 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. Author

Descriptors:

• (*LINEAR PROGRAMMING
• ALGORITHMS)
• SCHEDULING
• SET THEORY
• SIMPLEX METHOD
• OPTIMIZATION

Subject Categories:

• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE