Master's Thesis

Brandão, F. (2012). Bin Packing and Related Problems: Pattern-Based Approaches. Master’s thesis, Faculdade de Ciências da Universidade do Porto, Portugal.

Download (PDF)

The research derived from this thesis resulted in the following papers:

Abstract

We present novel exact and approximate methods for solving bin packing and related problems, which show a large advantage in practice when compared with traditional methods. For cutting stock problems, we present pattern-based heuristics, which do not depend on the number of pieces; this allows the algorithms to find solutions for extremely large cutting stock instances, with billions of items, in a very short amount of time. For bin packing, cutting stock, cardinality constrained bin packing and two-constraint bin packing, we present a very simple and powerful method that allows solving exactly many thousands of benchmark instances in a few seconds, on average.

The conventional assignment-based first/best fit decreasing algorithms (FFD/BFD) are not polynomial in the cutting stock input size in its most common format. Therefore, even for small instances with large demands, it is difficult to compute FFD/BFD solutions. Our pattern-based methods overcome the main problems of conventional heuristics in cutting stock problems by representing the solution in a much more compact format. An off-line variant of the sum-of-squares heuristics is also studied and compared with the FFD/BFD heuristics.

The proposed exact method, based on an arc flow formulation with side constraints, solves bin packing problems including multi-constraint variants by simply representing all the patterns in a very compact graph. Conventional formulations for bin packing problems are usually highly symmetric and provide very weak lower bounds. The proposed arc flow formulation provides a very strong lower bound, and it is able to break symmetry completely. However, it appears that with this model symmetry is not the main problem. We present a graph compression algorithm that usually reduces the underlying graph substantially without weakening the bounds. We report computational results obtained with many benchmark test sets, all of them showing a large advantage of this formulation with respect to traditional ones.

BibTeX

@MastersThesis{MThesisBrandao,
    author = {Brand\~ao, Filipe},
    title = {{Bin Packing and Related Problems: Pattern-Based Approaches}},
    school = {Faculdade de Ci\^encias da Universidade do Porto},
    address = {Portugal},
    year = {2012},
}

Results

Arc Flow Formulation (w/ Graph Compression) Results

See also

Bin Packing and Related Problems: General Arc-flow Formulation with Graph Compression

Multiple-choice Vector Bin Packing: Arc-flow Formulation with Graph Compression

Cutting Stock with Binary Patterns: Arc-flow Formulation with Graph Compression

Fast Pattern-based Algorithms for Cutting Stock

VPSolver Online Demo