Multiple-choice Vector Bin Packing: Arc-flow Formulation with Graph Compression
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.
Keywords: Multiple-choice Vector Bin Packing, Arc-flow Formulation, Integer Programming
Category 1: Integer Programming ((Mixed) Integer Linear Programming )
Citation: Brandão, F. and Pedroso, J. P. (2013). Multiple-choice Vector Bin Packing: Arc-flow Formulation with Graph Compression. Technical Report DCC-2013-13, DCC - FC, Universidade do Porto.
Entry Submitted: 12/13/2013
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|