Branch and Price for Submodular Bin Packing

DOI10.1016/J.EJCO.2023.100074MaRDI QIDQ6395389zbMATH OpenFDO

Authors Claudia D'Ambrosio, Emiliano Traversi

Publication date 1 April 2022

Full work available at URL https://doi.org/10.1016/J.EJCO.2023.100074

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Abstract: 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 chance-constrained and robust bin packing problems under various conditions. The SMBP is a hard mixed-integer nonlinear programming optimization problem. 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 a piece-wise 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 pricing heuristic. We test our algorithms on instances generated as suggested in the literature. The computational results show the efficiency of our branch-and-price algorithm and the proposed pricing techniques.

Recommendations

• Branch and Price for Chance-Constrained Bin Packing
• Solving robust bin-packing problems with a branch-and-price approach
• Branch-and-price algorithms for the dual bin packing and maximum cardinality bin packing problem
• Solving bin packing problems using VRPSolver models
• Algorithms for the bin packing problem with scenarios

Cited in

(1)

• A branch-and-price algorithm for the hyper-rectangular clustering problem with axis-parallel clusters and outliers

This page was built for publication: Branch and Price for Submodular Bin Packing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6395389)