2013/10/25 by Filipe Brandão, Brandão, Filipe, João Pedro Pedroso +1
Engineering · Materials Science · Business, Management and Accounting · #Optimization and Packing Problems #biodegradable polymer synthesis and properties #Product Development and Customization
paper · pdf · doi:10.48550/arxiv.1310.6887
We present an exact method, based on an arc-flow formulation with side\nconstraints, for solving bin packing and cutting stock problems --- including\nmulti-constraint variants --- by simply representing all the patterns in a very\ncompact graph. Our method includes a graph compression algorithm that usually\nreduces the size of the underlying graph substantially without weakening the\nmodel. As opposed to our method, which provides strong models, conventional\nmodels are usually highly symmetric and provide very weak lower bounds.\n Our formulation is equivalent to Gilmore and Gomory's, thus providing a very\nstrong linear relaxation. However, instead of using column-generation in an\niterative process, the method constructs a graph, where paths from the source\nto the target node represent every valid packing pattern.\n The same method, without any problem-specific parameterization, was used to\nsolve a large variety of instances from several different cutting and packing\nproblems. In this paper, we deal with vector packing, graph coloring, bin\npacking, cutting stock, cardinality constrained bin packing, cutting stock with\ncutting knife limitation, cutting stock with binary patterns, bin packing with\nconflicts, and cutting stock with binary patterns and forbidden pairs. We\nreport computational results obtained with many benchmark test data sets, all\nof them showing a large advantage of this formulation with respect to the\ntraditional ones.\n