The multibin-packing constraint captures a fundamental substructure of many assignment problems, where a set of items, each with a fixed number of dimensions, must be assigned to a number of bins with limited capacities. In this work we propose a simple decomposition for multibin-packing that uses a bin-packing constraint for each dimension, a set of all-different constraints automatically derived from a conflict graph, plus two alternative symmetry breaking approaches. Despite its simplicity, the proposed decomposition is very effective on a number of instances recently proposed in the literature.
A Simple and Effective Decomposition for the Multidimensional Binpacking Constraint / Stefano Gualandi;Michele Lombardi. - STAMPA. - 8124:(2013), pp. 356-364. (Intervento presentato al convegno Eighteenth International Conference on Principles and Practice of Constraint Programming tenutosi a Uppsala, Sweden nel September 16th-20th, 2013) [10.1007/978-3-642-40627-0_29].
A Simple and Effective Decomposition for the Multidimensional Binpacking Constraint
LOMBARDI, MICHELE
2013
Abstract
The multibin-packing constraint captures a fundamental substructure of many assignment problems, where a set of items, each with a fixed number of dimensions, must be assigned to a number of bins with limited capacities. In this work we propose a simple decomposition for multibin-packing that uses a bin-packing constraint for each dimension, a set of all-different constraints automatically derived from a conflict graph, plus two alternative symmetry breaking approaches. Despite its simplicity, the proposed decomposition is very effective on a number of instances recently proposed in the literature.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.