Nos tutelles

CNRS Dauphine PSL *


Accueil > Projets

Project « Mathematical Programming and Discrete Structures (Mathis) »

publié le , mis à jour le

The aim of this project is to develop new efficient methods for formulating, analysing and solving large practical problems as well as paradigmatic NP-hard problems. In particular, we study polyhedral approaches for combinatorial optimization problems. These have shown to be powerful for solving to optimality large and hard combinatorial optimization problems. These methods, which are based on linear and integer programming, consist in reducing the problem to a linear programming problem by describing the convex hull of its solutions by a system of linear inequalities. These methods, also permit to design polynomial time algorithms and establish combinatorial min-max relations. An important part of the activities in this project is related to these methods and their applications.

In this project, we are also interested in problems whose data are not known with certainty. Thus, it would be necessary to take this into account when analysing the problem. The objective here is to determine robust solutions for the problem, that is “good” solutions for all the different values of the uncertain data. Our aim here is to devise robust efficient algorithms for linear programming problems.

Four topics are related to the project Mathis :

  • Polyhedral approaches,
  • Network design,
  • Algebro-differential systems and combinatorial optimization
  • Robustness in linear programming.

Members of the project :

  • Permanent members : Denis Cornaz, Fabio Furini, Virginie Gabrel, A. Ridha Mahjoub, Cécile Murat, Bernard Ries.
  • ATER, PhD students : A. Benhamiche, M. Labidi, Y. Magnouche, M. Mahjoub, L. Mbodji, M. Ould Cheikh.