Séminaire Optimisation Mathématique Modèle Aléatoire et Statistique

The transportation problem has recently gained renewed interest due to its applications in machine learning and artificial intelligence, particularly in measuring distances between images.

To address the associated computational challenges, we propose a novel algorithm, Iterated Inside Out, for the exact resolution of the well-known transportation problem.

The core of our algorithm requires an initial basic feasible solution and consists of two iteratively repeated phases until an optimal basic feasible solution is obtained.

In the "inside" phase, the algorithm progressively improves the current solution by increasing the value of non-basic variables with negative reduced costs, typically yielding a feasible solution that is non-basic and interior to the constraint set polytope.

In the "outside" phase, the algorithm improves the current solution by iteratively setting variables to zero until a new improved basic feasible solution is reached.

Building on this core algorithm, we develop a specialized variant tailored for image processing.

Extensive computational experiments demonstrate that our approach significantly outperforms commercial solvers such as CPLEX and Gurobi, as well as other exact algorithms in the literature.

We demonstrate its superiority on both randomly generated instances and the DOTmark benchmark, a standard dataset for image processing and large-scale transportation problems.

Bilevel optimization is a rather young but very active sub-field of mathematical optimization. The main reason is that bilevel optimization problems can serve as a powerful tool for modeling hierarchical decision-making processes, which arise in various real-world applications such as in critical infrastructure defense, transportation, or energy. However, the nested structure of bilevel problems makes them intrinsically hard to solve—even if all parameters of the problem are exactly known. Further challenges arise if problems under uncertainty are considered.

In this talk, we begin with a brief introduction to the key concepts of bilevel optimization, covering the structure, characteristics, and commonly used reformulations of these problems. We then explore how techniques from robust optimization can be used to tackle bilevel problems under uncertainty. In particular, we highlight that the sources of uncertainty in bilevel optimization are much richer compared to classic, i.e., single-level, problems since not only the problem data but also the (observation of the) decisions of the two players can be subject to uncertainty.

Finally, we discuss recent algorithmic advances for solving mixed-integer linear bilevel problems with a binary lower level and a Gamma-robust treatment of lower-level objective uncertainty. To solve these Gamma-robust bilevel problems, we present an exact and problem-tailored branch-and-cut approach as well as a heuristic framework. The latter relies on solving a linear number of deterministic bilevel problems so that no problem-specific tailoring is required.