Arc-flow Formulation for 0-1 CSP

Brandão, F. and Pedroso, J. P. (2013). Cutting Stock with Binary Patterns: Arc-flow Formulation with Graph Compression.
Technical Report DCC-2013-09, Faculdade de Ciências da Universidade do Porto, Universidade do Porto, Portugal.

Technical Report (PDF) (also available at arXiv:1502.02899)

Abstract

The cutting stock problem with binary patterns (0-1 CSP) is a variant of CSP that usually appears as a relaxation of 2D and 3D packing problems. We present an exact method, based on an arc-flow formulation with side constraints, for solving 0-1 CSP by simply representing all the patterns in a very compact graph.

Gilmore-Gomory's column generation approach is usually used to compute strong lower bounds for 0-1 CSP. We report a computational comparison between the arc-flow approach and the Gilmore-Gomory's approach.

BibTeX

@TechReport{01CSPArcFlow,
    author = {Brand~ao, Filipe and Pedroso, J. P.},
    title = {{Cutting Stock with Binary Patterns: Arc-flow Formulation with Graph Compression}},
    type = {Technical Report},
    number = {DCC-2013-09},
    institution = {Faculdade de Ci\^encias da Universidade do Porto},
    address = {Portugal},
    year = {2013},
}

Abstract

BibTeX

See also