Abstract : Dans ce tutoriel, nous commençons par rappeler les principaux résultats liés aux problèmes de bin packing, ses principales variantes et les algorithmes utilisés pour les résoudre, en se concentrant sur les techniques de programmation linéaire en nombres entiers. Nous présentons aussi les enjeux plus récents liés aux problèmes de bin packing, notamment l'intégration de contraintes pratiques, l'insertion dans des problèmes complexes, et la gestion de l'incertitude.

Abstract : Je présenterai mes travaux de stage de fin d'études centrés essentiellement sur le problème de bin packing en 3 dimensions appliqué au transport aérien de marchandises. J'évoquerai plusieurs outils de modélisation des problèmes de bin packing (en particulier les différentes façons de regrouper les colis transportés), ainsi que des avancées récentes sur ces questions. Je mentionnerai également plusieurs problèmes de packing importants de dimensions moindre, en effet ils offrent des simplifications non négligeables pour la résolution.

Abstract : 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 talk 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.

Abstract : The Submodular Bin Packing (SMBP) problem asks for packing unsplittable items into a minimal number of bins for which the capacity utilization function is submodular. SMBP is equivalent to chance-constrained and robust bin packing problems under various conditions. SMBP is a hard binary 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 to 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.

Abstract : La programmation non-linéaire fait partie des principaux outils du praticien de la recherche opérationnelle. Dans cette exposé, nous présenterons et illustrerons d’abord le fonctionnement des méthodes de programmation non-linéaire à travers leurs applications aux problèmes de packing de formes irrégulières, à l’aide des solveurs FICO Xpress et Artelys Knitro. Nous mettrons en particulier l’accent sur les différences entre les approches locales et globales. Puis nous verrons comment ces méthodes sont effectivement utilisées dans la littérature pour obtenir des résultats à l’état de l’art sur ces problèmes.

Abstract : Bin packing is a classic optimization problem with a wide range of applications, from load balancing to supply chain management. In this work, we study the online variant of the problem, in which a sequence of items of various sizes must be placed into a minimum number of bins of uniform capacity. The online algorithm is enhanced with a (potentially erroneous) prediction concerning the frequency of item sizes in the sequence. We design and analyze online algorithms with efficient tradeoffs between the consistency (i.e., the competitive ratio assuming no prediction error) and the robustness (i.e., the competitive ratio under adversarial error), and whose performance degrades near-optimally as a function of the prediction error. This is the first theoretical and experimental study of online bin packing under competitive analysis, in the realistic setting of learnable predictions. Previous work addressed only extreme cases with respect to the prediction error, and relied on overly powerful and error-free oracles.