PhD graduated
Team : RO
Departure date : 03/16/2021

Supervision : Pierre FOUILHOUX

Co-supervision : BENDOTTI Pascale, CHRÉTIENNE Philippe

Anchored solutions in robust combinatorial optimization

If the instance of an optimization problem changes, an initial solution may become suboptimal or infeasible. It is then necessary to compute a new solution, but it is also desirable to keep some decisions from the initial solution unchanged. In this thesis we propose the anchoring criterion to favor unchanged decisions between solutions. In a reoptimization setting, the goal is to find a new solution while keeping a maximum number of decisions from the initial solution. In a robust 2-stage optimization setting, we propose the anchor-robust approach to compute in advance a baseline solution, along with a subset of so-called anchored decisions. For any realization in the considered uncertainty set, it is possible to repair the baseline solution into a new solution without changing anchored decisions. The anchor-robust approach allows for a trade-off between the cost of a solution and guaranteed decisions. Anchoring problems are formally defined and studied on two problem classes. The first one is the class of integer programs in binary variables, including classical polynomial problems such as spanning trees. The second one is project scheduling, where jobs must be scheduled under precedence only, or precedence and resource constraints. The complexity of anchoring problems is analyzed. Combinatorial properties of anchored solutions are exhibited, and dedicated algorithmic and polyhedral approaches are devised. Mixed-integer programming techniques are investigated, that highlight the practical implementability of anchoring problems.

Defence : 03/16/2021 - 14h -

Jury members :

DE WERRA Dominique (Professeur honoraire, Ecole Polytechnique Fédérale de Lausanne) [Rapporteur]
WOEGINGER Gerhard (Professeur, RWTH Aachen) [Rapporteur]
ESCOFFIER Bruno (Professeur, Sorbonne Université/ LIP6)
MEUNIER Frédéric (Professeur, Ecole Nationale des Ponts et Chaussées, CERMICS)
POSS Michael (Directeur de Recherche, CNRS, LIRMM)
BENDOTTI Pascale (Ingénieur-chercheur HDR, EDF R&D)
CHRÉTIENNE Philippe (Professeur émérite, Sorbonne Université/ LIP6)
FOUILHOUX Pierre (Professeur, Univ. Sorbonne Paris Nord, LIPN)

2018-2022 Publications