A Reduction Algorithm for Packing Problems

Michaël Gabay (1) , Hadrien Cambazard (1) , Yohann Benchetrit (2)

1 G-SCOP_ROSP - Recherche Opérationnelle pour les Systèmes de Production
2 G-SCOP_OC - Optimisation Combinatoire

We present a reduction algorithm for packing problems. This reduction is very generic and can be applied to almost any packing problem such as bin packing, multi-dimensional bin packing, vector bin packing (with or without heterogeneous bins), etc. It is based on a dominance applied in the compatibility graph of a partial solution and can be computed in polynomial time in the input size and the number of bins, even on instances with high-multiplicity encoding of the input.

Mots clés: Packing; Reduction algorithm; Multi-dimensional Packing; Vector Packing; Bin Packing; High-Multiplicity

Domaines: Recherche opérationnelle [math.OC]

Michaël Gabay, Hadrien Cambazard, Yohann Benchetrit. A Reduction Algorithm for Packing Problems. 2014. ⟨hal-01024270⟩