Set Covering, Packing and Partitioning Problems

George Mason University

New York University

We consider the class of problems having the following structure:

max cx

Ax ³ e^T

x_j = 0 or 1 for j=1,…,n

where A is a mxn matrix of zeroes and ones, e^T = (1,…,1) is a vector of m ones and c is a vector of n (arbitrary) rational components. This pure 0-1 linear programming problem is called the set covering problem. When the inequalities are replaced by equations the problem is called the set partitioning problem, and when all of the ³ constraints are replaced by £ constraints, the problem is called the set packing problem.

Applicability of the Problem: Many applications arise having the packing, partitioning and covering structure. Delivery and routing problems, scheduling problems and location problems often take on a set covering structure whereby one wishes to assure that every customer is served by some location, vehicle or person. Other applications include switching theory, the testing of VLSI circuits, and line balancing. Similarly, scheduling problems whereby one wishes to satisfy as much demand as possible, without creating conflicts often requires the set packing format. Finally, when every customer must be served by exactly one server, the problem takes on the set partitioning format. Commonly cited problems having this structure include the crew-scheduling problem where every flight leg of an airline must be scheduled by exactly one cockpit crew; another is the political districting problem whereby regions must be divided into voting districts such that every citizen is assigned to exactly one district. See the survey by Balas and Padberg [1976] that contains a bibliography on applications.

Recently, reformulating them as either set-covering problems or set-partitioning problems having an extraordinary number of variables has solved a variety of difficult problems. Because, for even small instances of the problem, the problem size cannot be explicitly solved, techniques known as column-generation, which began with the seminal work of Gilmore and Gomory [1961] on the cutting stock problem, are employed. An overview of such transformation methods can be found in Barnhart, et al [1994]. For specific implementations to the vehicle routing problem, see Desrochers et al. [1989], for the bandwidth packing problem, see Parker and Ryan [1994], for the generalized assignment problem see Salevsbergh [1998] and for alternative column-generation strategies for solving the cutting stock problems, see Vance [1998].

Bramel and Simchi-Levi [1997] have shown that the set partitioning formulation for the vehicle routing problem with time windows is a tight formulation, i.e. the relative gap between the fractional linear programming solution and the global integer solution are close. Similar results are obtained for the bin-packing problem (Chan, Simchi-Levi and Bramel, 1998) and for machine scheduling (Chan, Muriel and Simchi-Levi, 1998).

Solution Approaches: Once the problem has been formulated as a set-covering, set-packing or set-partitioning problem, the search for an optimal (or near-optimal) solution to this NP-hard 0-1 linear programming problem remains. Most solution approaches start by considering the linear programming (LP) relaxation of the respective problem. If the matrix A is a perfect zero-one matrix, see Padberg [1974], then the LP relaxation of both the set packing and the set partitioning problem have zero-one optimal solution for all choices of the objective function. Likewise, if the matrix A is an ideal matrix, see Padberg [1993], then the same holds true for the set covering and the set-partitioning problem. Problems arising in practice need not, however, have perfect or idea matrices. Nevertheless, it has been observed in computational practice that as long as the problems to be solved are relatively small, linear programming (or linear programming coupled with branch-and-bound) is likely to provide integer solutions quickly. However, as the sub-problem size increases, the non-integrality of the linear programming solution increases dramatically as does the length and size of the branching tree. It is for these larger instances of the problem that approximation techniques, reformulation and exact procedures have been developed that exploit the underlying structure of the problem.

Reformulation of the linear description of the problem: The natural structure of packing, covering and partitioning approaches provides opportunities to automatically remove any unnecessary rows or columns, and to remove any variables that cannot exist in any optimal solution. Checks for inconsistencies among the constraints are also performed. Reformulation procedures for the set covering problem have been well known for a long time [see Garfinkel and Nemhauser, 1972] but had not been implemented into a special-purpose code for solving very large-scale problems until 1993 (Hoffman and Padberg).

Heuristics for the set partitioning and covering problems: Virtually every heuristic approach for solving general integer programming problems has been applied to the set-covering, packing and partitioning problems. The set covering and packing formulations naturally lends themselves to greedy starts (i.e. an approach that at every iteration myopically chooses the next best step without regard for its implications on future moves), see e.g. Fisher and Wolsey(1982). Interchange approaches have also been applied—here; a swap of one or more columns is taken whenever such a swap improves the objective function value. Newer heuristic approaches such as genetic algorithms (Levine, 1992), probabilistic search (Feo, et al, 1989), simulated annealing (Johnson, et al., 1989), and neural networks (Aourid and Kaminska, 1994) have each been tried. Unfortunately, there has not been a comparative testing across such methods to determine under what circumstances a specific method might perform best. Beasley (1990) maintains an extensive test set of problem instances for these important problems.

In addition, one can embed heuristics within exact algorithms so that one iteratively tightens the upper bound at the same time that one is attempting to get a tight approximation to the lower bound for the problem. Hoffman and Padberg (1993) describe a linear-programming based heuristic for the set-partitioning problem with side constraints, while Balas and Carrera (1996) provide heuristics based on using Lagrangian relaxation embedded within branch-and-bound to solve the set covering problem.

Exact Solution Approaches to the Set Covering, Packing and Partitioning Problems: Exact approaches to solving set partitioning, covering and packing problems require algorithms that generate both good lower and upper bounds on the true minimum value of the problem instance. One can use any of the heuristics mentioned above to obtain a good upper bound to these problems. One should note, however, that the set covering and packing problems are easier problems for heuristic search because for these problems, it is, in general, easy to find feasible solutions. The set-partitioning problem may create unique concerns for some of these algorithms specifically because each row must be covered exactly once.

In general, the lower bound on the optimal solution value is obtained by solving a relaxation of the optimization problem. That is, one solves another optimization problem whose set of feasible solutions properly contains all feasible solutions of the original problem and whose objective function value is less than or equal to the true objective function value for points feasible to the original problem. Thus, we replace the "true" problem by one with a larger feasible region that is more easily solved. There are two standard relaxations for covering, packing and partitioning problems: Lagrangean relaxation (where the feasible set is usually required to maintain 0-1 feasibility, but many if not all of the constraints are moved to the objective function with a penalty term) and the linear programming relaxation (where only the integrality constraints are relaxed – the objective function remains the original function). For the set-covering problem, Etcheberry (1977) considered using a Lagrangean formulation and subgradient optimization. Balas and Ho (1980) tested various Lagrangean relaxations including some that incorporated cuts within the formulation and kept a disjoint set of the original linear constraints unrelaxed. In Balas and Carrera (1996), dual and primal heuristics, recursive variable fixing and subgradient optimization are embedded within a branch and bound tree search.

An alternative approach to solving set partitioning, packing and set covering problems is branch and cut. This method begins by solving the linear programming relaxation to the problem and then tightening the formulation by adding new linear inequalities to the constraint set.

Specifically, it requires finding linear inequalities that are violated by a given relaxation but are satisfied by all feasible zero-one points. The most successful cutting plane approaches are based on polyhedral theory, that is they replace the constraint set of an integer programming problem by a convexification of the feasible zero-one points and extreme rays of the problem. Some of the polyhedral cuts useful for set-partitioning problems are clique inequalities, odd cycles, and the complements of odd cycles in the intersection graph associated with the matrix A. For a complete description of how such cuts are embedded into a tree search structure that also uses heuristics, and reformulation and variable fixing techniques, see Hoffman and Padberg (1993).

For details on polyhedral structure see Padberg (1973, 1975 and 1979), Cornuejols and Sassaso (1989) and Sassano (1989). Currently, the polyhedral description of these problems is incomplete. As our understanding of the mathematical structure of the set partitioning, packing and covering polytopes improves, and with the continuing advancement in computer technology, it is likely that many difficult and important problems will be solved by being able to solve larger and larger set partitioning problems to proven optimality.

The Future: The recent interest in reformulating hard, important scheduling problems into set partitioning problems via column generation has reinvigorated research into both linear and integer programming solution techniques. The linear programming relaxation of these very large set partitioning problems yield highly degenerate problems for the primal simplex method to solve. This degeneracy resulted in the revisiting of both primal and dual steepest-edge methods, see Goldfarb and Reid(1977). The fact that the column generation approaches require the solution to many set-partitioning problems requires that we better understand the structure of these problems. More research into polyhedral structure, time-staged network optimization (for the sub-problem solutions), and careful attention to computer implementation details are likely to yield successes to problems (such as machine-shop scheduling) that up until now have not allowed exact solution approaches.

[1] M. Aourid and B. Kaminska, "Neural Networks for the Set Covering Problem: An Application to the Test Vector Compaction", IEEE International Conference on Neural Networks Conference Proceedings, 7, 4645-4649, 1994.

[2] E. Balas and M.C. Carrera "A Dynamic Subgradient-based Branch-and-Bound Procedure for Set Covering", Operations Research, 44, 875-890, 1996.

[3] E. Balas and Ho "Set Covering Algorithms Using Cutting Planes, Heuristics, and Subgradient Optimization: A Computational Study. Mathematical Programming, 12, 37-60, 1980.

[4] E. Balas and M.W. Padberg, "Set Partitioning: A Survey", SIAM Review, 18, 710-760, 1976.

[5] C. Barnhart, E.D. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh and P.H. Vance "Branch and Price Column Generation for Solving Hugh Integer Programs" Operations Research, 46, 316-329, 1998.

[6] J.E. Beasley, "A Lagrangian Heuristic for Set-Covering Problems", Naval Research Logistics, 37, 151-164, 1990.

[7] J. Bramel and D. Simchi-Levi, "On the Effectiveness of set covering formulations for the vehicle routing problem with time windows", Technical Report, Dept of Industrial Engineering and Management Science, Northwestern University, 1998.

[8] L.M.A. Chan, A. Muriel, and D. Simchi-Levi "Parallel Machine Scheduling, Linear Programming, and Parameter List Scheduling Heuristics", Technical Report, Dept of Industrial Engineering and Management Science, Northwestern University, 1998.

[9] L.M.A. Chan, D. Simchi-Levi, and J. Bramel, "Worst-case Analysis, Linear Programming and the Bin-packing problem", Technical Report, Dept of Industrial Engineering and Management Science, Northwestern University, 1998.

[10] G. Cornuejols and A. Sassano "On the 0-1 Facets of the Set Covering Polytope", Mathematical Programming, 43, 45-56, 1989

[11] M. Desrochers and F. Soumis "A Column Generation Approach to the Urban Transit Crew Scheduling Problem" Transportation Science, 23, p 1-13, 1989.

[12] J. Etcheberry "The Set Covering Problem: A New Implicit Enumeration Algorithm", Operations Research, 25, 760-772, 1977.

[13] A. Feo and G.C. Mauricio and A. Resende, "A Probabilistic Heuristic for a Computationally Difficult Set Covering Problem", Operations Research Letters, 8, 67-71, 1989.

[14] M. Fisher and L. Wolsey "On the Greedy Heuristic for Covering and Packing Problems", SIAM Journal on Algebraic and Discrete Methods, 3, 584-591, 1982.

[15] R. Garfinkel and G.L. Nemhauser, Integer Programming, John Wiley and Sons, pp302-305, 1972.

[16] P.C. Gilmore and R.E. Gomory, "A Linear Programming Approach to the Cutting Stock Problem", Operations Research, 9, 849-859. 1961.

[17] D. Goldfarb and J.K. Reid "A Practicable Steepest-edge Algorithm", Mathematical Programming, 12, 361-371, 1977.

[18] N. Hall and D. Hochbaum "A fast approximation algorithm for the multicovering problem" Discrete Applied Mathematics 15 35-40, 1989.

[19] W.C. Huang, C.Y. Kao, and J.T. Hong "A genetic algorithm for set covering problems", IEEE International Conference on Genetic Algorithms: Proceedings. 569-574, 1994.

[20] K. Hoffman and M.W. Padberg, "Solving Airline Crew Scheduling Problems by Branch and Cut", Management Science 39, 657-682, 1993.

[21] L. Jacobs, and M. Brusco, "Note: A Local-Search Heuristic for Large Set-Covering Problems", Naval Research Logistics, .42, 1129-1140, 1995.

[22] M.W. Padberg, "On the facial structure of set packing polyhedra", Mathematical Programming, 5, 199-215, 1973.

[23] M.W. Padberg, "Perfect zero-one matrices" Mathematical Programming, 6, 180-196, 1974.

[24] M.W. Padberg "On the complexity of the set packing polyhedra" Annals of Discrete Mathematics 1, 421-434, 1975.

[25] M.W. Padberg, "Covering, Packing and Knapsack Problems" Annals of Discrete Mathematics, 4, 1979.

[26] M.W. Padberg, "Lehman’s forbidden minor characterization of ideal 0-1 matrices", Discrete Mathematics, 111, 409-410, 1993.

[27] M. Parker and J. Ryan "A column generation algorithm for bandwidth packing", Telecommunications Systems, 2, 185-196, 1994.

[28] A. Sassano, "On the Facial Structure of the Set Covering Polytope", Mathematical Programming, 44, 181-202, 1973.

[29] M.W.P. Savelsbergh "A Branch-and-Price Algorithm for the Generalized Assignment Problem", Operations Research, 45, 831-841,1997.