Mathematical Programming and Discrete Structures (Mathis)

Project of  Pôle 2 Combinatorial Optimization, algorithms

The goal of the project is to develop effective methods for formulating, analyzing and solving large sized NP-hard practical and paradigmatic problems. In particular, we consider polyhedral approaches for hard combinatorial optimization problems. These techniques have shown to be powerful in solving this type of problems. Based on linear programming and integer programming, the polyhedral approaches consist in transforming the problem into a linear program whose constraints describe the convex hull of its feasible solutions. This would permit to develop polynomial algorithms and to obtain min-max relations between combinatorial structures. An important part of the research developed in this project is related to these methods and their applications.

In this project, we are also interested in cases where the data of an optimization problem are not known with certainty, and it is therefore necessary to integrate this uncertainty in the model to be optimized. In this context, the goal is to determine which are called robust solutions, that is to say "good" for the different plausible values ​​of the uncertain data. Our research here concerns robust optimization in the context of linear programming.

  • Keywords : Polyhedral approach, Network design, Graph Theory, Probabilistic method, Robustness, Semi-definite positive programming, TDI (box-) system, Large problems, column generation, cutting plane algorithms