Abstract:

This thesis focuses on mixed-integer nonlinear programming (MINLP), a class of mathematical optimization problems, and the associated algorithms to solve them. The core algorithm utilized in many global optimization solvers for MINLP problems is the branch-and-bound algorithm. Key to the success of the branch-and-bound approach is the use of relaxations of optimization problems, which are vital in obtaining efficient and tight dual bounds. However, constructing effective relaxations depends on the specific structures of optimization problems. In the first part of this thesis, we present a comprehensive overview of structural relaxation tools tailored for structured MINLP problems across different disciplines. These tools encompass relaxations from extended formulations, relaxations via submodularity, relaxations using piece- wise linear approximation, and relaxation tightening via intersection cuts. Then, we develop novel advanced theoretical results based on these tools. In the second part, we employ these relaxation techniques to address various optimization problems. We explore cutting planes for signomial programming. Then, we propose intersection cuts for enhancing linear programming relaxations of submodular optimization problems. Next, we investigate the Dantzig-Wolfe relaxations for a mixed-integer linear programming problem in wireless network routing and a MINLP problem in submodular binpacking. Finally, we study the big-M relaxation technique as applied to piece-wise linear functions in the continuous covering problem on a network. By combining these comprehensive studies on various relaxation techniques and their applications in different optimization contexts, this thesis contributes to the advancement of MINLP and related optimization methods, offering valuable insights for both theoretical understanding and computational implementation.

Thesis jury:

M. Leo LIBERTI, Directeur de thèse - Directeur de Recherche, LIX CNRS, École polytechnique
Mme Sonia HADDAD VANIER, Co-Encadrant de thèse - Maître de Conférence HDR, Université Panthéon-Sorbonne & LIX
M. François CLAUTIAUX, Professeur, Institut de Mathématiques de Bordeaux, Université de Bordeaux & Inria Bordeaux
Mme Ruth MISENER, Professeur, Department of Computing, Imperial College London
M. Michaël POSS, Directeur de Recherche, LIRMM CNRS, Université de Montpellier
M. Roberto WOLFLER-CALVO, Directeur de Recherche, LIPN CNRS, Université de Paris-Nord