Content area
Full text
Several combinatorial optimization problems can be formulated as large set-covering problems. In this work, we use the set-covering formulation to obtain a general heuristic algorithm for this type of problem, and describe our implementation of the algorithm for solving two variants of the well-known (one-dimensional) bin-packing problem: the two-constraint bin-packing problem and the basic version of the two-dimensional bin-packing problem, where the objects cannot be rotated and no additional requirements are imposed. In our approach, both the "column-generation" and the "column-optimization" phases are heuristically performed. In particular, in the first phase, we do not generate the entire set of columns, but only a small subset of it, by using greedy procedures and fast constructive heuristic algorithms from the literature. In the second phase, we solve the associated set-covering instance by means of a Lagrangian-based heuristic algorithm. Extensive computational results on test instances from the literature show that, for the two considered problems, this approach is competitive, with respect to both the quality of the solution and the computing time, with the best heuristic and metaheuristic algorithms proposed so far.
Key words: two-constraint bin-packing; two-dimensional bin-packing; column-generation; set-covering; heuristics
History: Accepted by Michel Gendreau, Area Editor for Heuristic Search and Learning; received June 2003; revised March 2004; accepted March 2004.
1. Introduction
Several NP-hard combinatorial optimization problems can be formulated as large set-covering (or setpartitioning) problems; this happens for all problems in which one is required to partition a given set J = {1, 2, . . . , n} of items into subsets having special features and to minimize the sum of the costs associated with the subsets. For instance, in the (onedimensional) bin-packing problem (IBP), we are given a set of n objects (each having a positive weight) to be partitioned into the minimum number of subsets (bins) so that the sum of the weights in each subset does not exceed a given capacity. In the graphcoloring problem (GCP), we are given a graph G = (V, E), and the aim is to partition the n vertices of V into the minimum number of subsets (colors) such that no two vertices of the same subset are both endpoints of any edge in E. In the capacitated vehicle-routing problem (VRP), we are given...