
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
View/ Open
Type
Article accepté pour publication ou publiéDate
2020Journal name
European Journal of Operational ResearchVolume
297Number
3Publisher
Elsevier
Pages
831-843
Publication identifier
Metadata
Show full item recordAuthor(s)
Schepler, XavierRossi, André
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Gurevsky, Evgeny
Dolgui, Alexandre
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 / Keywords
Packing; Robustness; Sensitivity analysis; Uncertainty; Stability radius; Relative resiliency; Dantzig-Wolfe decomposition; Column generation; Branch-and-priceRelated items
Showing items related by title and author.
-
Schepler, Xavier; Dolgui, Alexandre; Gurevsky, Evgeny; Rossi, André (2020) Communication / Conférence
-
Pirogov, Aleksandr; Gurevsky, Evgeny; Rossi, André; Dolgui, Alexandre (2019) Article accepté pour publication ou publié
-
Pirogov, Aleksandr; Rossi, André; Gurevsky, Evgeny; Dolgui, Alexandre (2021) Communication / Conférence
-
Gurevsky, Evgeny; Rasamimanana, Andry; Pirogov, Aleksandr; Dolgui, Alexandre; Rossi, André (2022) Article accepté pour publication ou publié
-
Dell’Amico, Mauro; Furini, Fabio; Iori, Manuel (2019) Article accepté pour publication ou publié