- Try it online!
- Available at http://vpsolver.fdabrandao.pt
- GitHub: https://github.com/fdabrandao/vpsolver
Arc-flow Formulation for Multiple-choice Vector Bin Packing
Brandão, F. and Pedroso, J. P. (2013). Multiple-choice Vector Bin Packing: Arc-flow Formulation with Graph Compression.
Technical Report DCC-2013-13, Faculdade de Ciências da Universidade do Porto, Portugal.
Technical Report (PDF) (also available at arXiv:1312.3836)
Abstract
The vector bin packing problem (VBP) is a generalization of bin packing with multiple constraints. In this problem we are required to pack items, represented by p-dimensional vectors, into as few bins as possible. The multiple-choice vector bin packing (MVBP) is a variant of the VBP in which bins have several types and items have several incarnations. We present an exact method, based on an arc-flow formulation with graph compression, for solving MVBP by simply representing all the patterns in a very compact graph. As a proof of concept we report computational results on a variable-sized bin packing data set.
BibTeX
@TechReport{MultipleChoiceVBP,
author = {Brand\~ao, Filipe and Pedroso, J. P.},
title = {{Multiple-choice Vector Bin Packing: Arc-flow Formulation with Graph Compression}},
type = {Technical Report},
number = {DCC-2013-13},
institution = {Faculdade de Ci\^encias da Universidade do Porto},
address = {Portugal},
year = {2013},
}
See also
Cutting & Packing Problems: General Arc-flow Formulation with Graph Compression
Bin Packing and Related Problems: General Arc-flow Formulation with Graph Compression
Cutting Stock with Binary Patterns: Arc-flow Formulation with Graph Compression