Branch and Price for Sub-modular Bin Packing

Liding Xu (1, 2) , Claudia d'Ambrosio (1, 2, 3) , Sonia Vanier (1, 2, 4) , Emiliano Traversi (5)

1 OptimiX - Optimization at LIX
2 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
3 CNRS - Centre National de la Recherche Scientifique
4 UP1 UFR27 - Université Paris 1 Panthéon-Sorbonne - UFR Mathématiques & Informatique
5 LIPN - Laboratoire d'Informatique de Paris-Nord

The submodular bin packing (SMBP) problem aims to pack items into a minimal number of bins for which the capacity utilization function is submodular. The SMBP is equivalent to the random-constrained and robust bin packing problem under various conditions. However, due to the combinatorial and nonlinear nature of the underlying optimization problem, it is difficult to solve the SMBP. In this paper, we propose a branch-and-price algorithm to solve this problem. The resulting price subproblems are submodular Knapsack problems, and we propose a tailored exact branch-and-cut algorithm based on piecewise linear relaxation to solve them. To speed up column generation, we develop a hybrid pricing strategy that can replace the exact pricing algorithm with a fast heuristic pricing algorithm. We test our algorithms on instances from the literature. The computational results show the efficiency of our branch-and-price algorithm and the proposed pricing techniques. .

Domaines: Informatique [cs]; Mathématiques [math]

Liding Xu, Claudia d'Ambrosio, Sonia Vanier, Emiliano Traversi. Branch and Price for Sub-modular Bin Packing. 2022. ⟨hal-03646468⟩