A dominance criterion for packing problems
Résumé
We present an algorithm which we use to identify easy subproblems for packing problems. The algorithm is polynomial in the number of bins and item types and is based on a flow computation in a bipartite compat- ibility graph. It outputs the largest subproblem satisfying the dominance criterion and a feasible solution to this subproblem. The algorithm is well suited to be integrated in a branch-and-bound solver for packing problems and can be adapted to work on many problems, including single or multi-dimensionnal bin packing, vector packing, cutting stock, packing with conflicts, etc.