Optimization Online


Solving Bin Packing Related Problems Using an Arc Flow Formulation

Filipe Brandão (fdabrandao***at***dcc.fc.up.pt)
João Pedro Pedroso (jpp***at***fc.up.pt)

Abstract: We present a new method for solving bin packing problems, including two-constraint variants, based on an arc flow formulation with side constraints. Conventional formulations for bin packing problems are usually highly symmetric and provide very weak lower bounds. The arc flow formulation proposed provides a very strong lower bound, and is able to break symmetry completely. The proposed formulation is usable with various variants of this problem, such as bin packing, cutting stock, cardinality constrained bin packing, and 2D-vector bin packing. We report computational results obtained with standard benchmarks, all of them showing a large advantage of this formulation with respect to the traditional ones.

Keywords: bin packing, cutting stock, integer programming, arc flow formulation, cardinality constrained bin packing, 2D-vector bin packing

Category 1: Applications -- OR and Management Sciences (Production and Logistics )

Category 2: Applications -- OR and Management Sciences (Transportation )

Category 3: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Technical Report DCC-2012-03, DCC - FC, Universidade do Porto, April, 2012

Download: [PDF]

Entry Submitted: 04/13/2012
Entry Accepted: 04/13/2012
Entry Last Modified: 04/13/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society