Workshop on Polyhedral Approaches for Combinatorial Optimization

(Celebrating A. Ridha Mahjoub 60th birthday)

December the 8th and 9th, 2016


Polyhedral approaches are powerfull mathematical techniques for Combinatorial Optimization problems to analyse their combinatorial structures and construct efficient algorithm to solve them. They consist in describing (completly or partially) the convex hull of set of feasible solutions with linear inequalities. If a complete description is known, the problem is equivalent to a linear programming having potentially an exponential number of inequalities. Such a linear program can be solved using a cutting planes based algorithm. which starts with a restricted number of inequalities and add dynamically violated new ones: searching for violated inequalities is known as the separation problem. A well known result states that if the separation problem can be solved in polynomial time, the cutting planes based algorithm is then also polynomial. If only a partial characterization is obtained, cutting plane algoritmhs can be used to get dual bounds on the optimal solution, and can be embedded in an enumeration scheme to solve exactly the problem.

Polyhedral approaches have then been used to produce either polynomiality proof of combinatorial problems, especially in Graph Theory, or to solve efficiently instances of NP-hard problems.

Ali Ridha Mahjoub is a distinguished full professor at the Department of Mathematics and Computer Science of the University Paris Dauphine. Its research fields concern polyhedral approaches and graph theory for solving combinatorial optimization problems. Its contributions go from theoretical results (polyhedral description theorems, graph (de)compositions, ...) to practical applications (in particular in network design, routing, or statistical physics).

After a Master Degree in Operations Research, A.R. Mahjoub got a PhD in the same field in 1981 at the Institute of Computer Science and Applid Mathematics (IMAG) in Grenoble under the supervision of Professor Michel Sakarovitch. Four years later, he got his habilitation thesis in Combinatorial Optimization and Operations Research in Grenoble under the supervision of Jean Fonlupt. From then, he got tenures in various universities and countries, from Saudi Arabia to Paris. Along these years, he published more than 80 papers and supervised more than 20 PhD thesis.

The aim of this workshop is to bring together researchers working on subjects related to Ridha's works in order to celebrate his scientific achievements. The purpose of this event is to present some of the classical important results of Combinatorial Optimization as well as recent results. We also hope that this workshop in a friendly context will be a place to generate discussions on open directions and new collaborations.

The organizers

Organizing committee

Mourad Baiou (LIMOS, Université Blaise Pascal, Clermont-Ferrand)
Francisco Barahona (IBM, New-York)
Fatiha Bendali (LIMOS, Université Blaise Pascal, Clermont-Ferrand)
Denis Cornaz (Lamsade, Université Paris Dauphine)
Ibrahima Diarrassouba (LMAH, Université du Havre)
Mohammed Didi Biha (Laboratoire Nicolas Oresme, Université de Caen)
Pierre Fouilhoux (LIP6, Université Paris 6)
Hervé Kerivin (LIMOS, Université Blaise Pascal, Clermont-Ferrand)
Sébastien Martin (LCOMS, Université de Lorraine, Metz)
Pierre Pesneau (IMB, Université de Bordeaux)


The workshop will take place in the Hermite Amphitheater of the Institut Henri Poincaré in Paris, France.