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 : JUL 1973

Pagination or Media Count : 19

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