Solving robust bin-packing problems with a branch-and-price approach
Schepler, Xavier; Rossi, André; Gurevsky, Evgeny; Dolgui, Alexandre (2020), Solving robust bin-packing problems with a branch-and-price approach, European Journal of Operational Research, 297, 3, p. 831-843. 10.1016/j.ejor.2021.05.041
TypeArticle accepté pour publication ou publié
Journal nameEuropean Journal of Operational Research
MetadataShow full item record
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)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.
Subjects / KeywordsPacking; Robustness; Sensitivity analysis; Uncertainty; Stability radius; Relative resiliency; Dantzig-Wolfe decomposition; Column generation; Branch-and-price
Showing items related by title and author.
Robust balancing of transfer lines with blocks of uncertain parallel tasks under fixed cycle time and space restrictions Pirogov, Aleksandr; Gurevsky, Evgeny; Rossi, André; Dolgui, Alexandre (2019) Article accepté pour publication ou publié
Gurevsky, Evgeny; Rasamimanana, Andry; Pirogov, Aleksandr; Dolgui, Alexandre; Rossi, André (2022) Article accepté pour publication ou publié