Solving robust bin-packing problems with a branch-and-price approach

One-dimensional bin-packing is a well-known combinatorial optimization problem which is strongly NP hard. It consists of allocating a given set of items of different sizes into bins of the same capacity to minimize the number of bins used. The capacity of each bin cannot be exceeded. This paper deals with some variants of this problem to take into account the cases when there are items with uncertain sizes. The goal is to obtain robust solutions taking into account possible variations of item sizes around their nominal values. First, two robust approaches are considered which are based on a stability radius calculation, to ensure that the stability radius , measured either with the Manhattan or Chebyshev norm, is not below a given threshold. Then, a complementary robust approach is applied which is based on a relative resiliency calculation. To solve to optimality these robust variants of the bin-packing problem, a compact 0-1 linear programming formulation, which is also valid for the standard bin-packing problem, is introduced. Then, a Dantzig-Wolfe decomposition is suggested in order to provide a set-cover reformulation with a stronger linear relaxation, but an exponential number of columns. Finally, to obtain integer optimal solutions, a branch-and-price algorithm is developed, whose linear relaxation of the set-cover formulation is solved by a dynamic column generation. Numerical experiments are conducted on adapted benchmark sets from the literature. The performance of the branch-and-price algorithm allows us to investigate what protection against uncertainty is offered by each approach, and at which cost of robustness. (c) 2021 Elsevier B.V. All rights reserved.

Automated summary

One-dimensional bin-packing is a combinatorial optimization problem, and this paper investigates variants of the problem to address uncertain item sizes. Robust solutions are proposed using stability radius and relative resiliency calculations, with a 0-1 linear programming formulation and branch-and-price algorithm developed for optimal solutions. Experimental results on benchmark sets explore the protection against uncertainty offered by each approach and the cost of robustness.