Computational advances in the solution of large-scale covering and set partitioning problems
Bausch, Dan O.
Brown, Gerald G.
McBride, Richard D.
MetadataShow full item record
The Set Covering Problem (SCP) and the Set Partitioning Problem (SPP) represent an important class of all-binary (0-1) Integer Linear Programs (ILP). A review of the literature reveals extensive application of the SPP/SCP model to a wide set of practical problems. The basic model is explained, and then many of the actual applications of this powerful model discovered in the literature review are discussed. The problems derived from these applications are difficult to solve with any method, and are particularly difficult to solve with optimal or exact algorithms. Various solution techniques are investigated within the framework of the classical simplex method with branch and bound enumeration. Several reformulations of the SPP/SCP as Integer Generalized Networks are examined Extensive computational results are reported for several "real world" large-scale problems, and a convenient, compact format for data input is proposed as a standard for this problem class.
Showing items related by title, author, creator and subject.
Brown, Gerald G.; Geoffrion, Arthur M.; Bradley, Gordon H. (1981);The focus of this paper is multiperiod production and sales planning when there is a single dominant production operation for which tooling (dies, molds, etc.) can be shared among parts and is limited in availability. Our ...
Agrawal, B.N. (1993);This paper presents a boundary-layer model to predict dynamic characteristics of liquid motion in partially filled tanks of a spinning spacecraft. The solution is obtained by solving three boundary-value problems: an ...
French, Dana Page Jr. (Monterey, California. Naval Postgraduate School, 1975-06);This thesis provides initial groundwork in condensing and extracting from the literature of management and the broad social sciences those concepts that are deemed pertinent to Navy managers in the fleet in helping to solve ...