17 DEZEMBRO / DOMINGO / 13:46
FCUP PT 
 EN
 
 
APRESENTAÇÃO
PESSOAS
ENSINO
INVESTIGAÇÃO
BIBLIOTECA
NOTÍCIAS
CONTACTOS

Technical Report: DCC-2013-09

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

Filipe Brandão, João Pedro Pedroso

DCC-FC & INESC Porto, Universidade do Porto
e-mail: {fdabrandao,jpp}@dcc.fc.up.pt
September 2013

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.

Keywords: Bin Packing, Cutting Stock, Strip Packing, Arc-flow Formulation


FCUP 2017