Computational advances in the solution of large-scale covering and set partitioning problems

Download
Author
Bausch, Dan O.
Date
1982-10Advisor
Brown, Gerald G.
Second Reader
McBride, Richard D.
Metadata
Show full item recordAbstract
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.
Collections
Related items
Showing items related by title, author, creator and subject.
-
Production and Sales Planning with Limited Shared Tooling at the Key Operation
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 ... -
Dynamic Characteristics of Liquid Motion in Partially Filled Tanks of a Spinning Spacecraft
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 ... -
Toward a handbook for naval managers.
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 ...