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

Abstract

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.