2013/12/13 by Filipe Brandão, Brandão, Filipe, João Pedro Pedroso +1
Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #cs.DS #math.OC
paper · pdf · doi:10.48550/arxiv.1312.3836
arXiv admin note: text overlap with arXiv:1310.6887 by other authors
arxiv created 2013/12/13 · arxiv updated 2013/12/16
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.