Groupe de travail Polyèdres et Optimisation Combinatoire

Inscrits SPOC 8

fouilhoux — 2012-01-19T16:30:06Z

Inscrits au Séminaire POC "Formulations étendues"

Hanane ALLAOUA	LIPN, Université Paris-Nord
Zacharie ALES	Insa, Rouen
Claudia d'AMBROSIO	LIX - Ecole Polytechnique
Mourad BAIOU	LIMOS, Université Blaise Pascal
Walid BENAMEUR	It-Sudparis
Amal BENHAMICHE	LAMSADE, Université Paris-Dauphine
Pascale BENDOTTI	EDF, Paris
Nicolas BONIFA	LIX - Ecole Polytechnique
Sylvie BORNE	LIPN, Université Paris-Nord
Denis CORNAZ	LAMSADE, Paris
Alberto COSTA	LIX - Ecole Polytechnique
Ibrahima DIARRASSOUBA	Université du havre
Mohamed DIDI BIHA	Université de Caen
Eric DUCHENNE	LAMIH, Université de Valenciennes
Nicolas DUPIN	Université Bordeaux1
Samuel FIORINI	Université Libre de Bruxelles
Pierre FOUILHOUX	LIP6, Université Pierre et Marie Curie
Paolo GIANESSI	LIPN, Université Paris-Nord
David GRAVOT	Rostudel
Makhlouf HADJI	It-Sudparis
Aissi HASSAN	LAMSADE, Université Paris-Dauphine
Hassan HIJAZI	LIX - Ecole Polytechnique
Cédric JONCOUR	Université du Havre
Volker KAIBEL	Otto-von-Guericke-University Magdeburg
Arnaud KNIPPEL	Insa, Rouen
Leo LIBERTI	LIX - Ecole Polytechnique
Claire LIZON	Dép. de mathématiques de l'IFP Energies nouvelles
A. Ridha MAHJOUB	LAMSADE, Université Paris-Dauphine
Sébastien MARTIN	LAMSADE, Université Paris-Dauphine
M.A. MOHAMED SIDI	It-Sudparis
Viet Hung NGUYEN	LIP6, Université Pierre et Marie Curie
Nancy PERROT	OrangeLabs
Pierre PESNEAU	IMB, Bordeaux
Daniel PORUMBEL	LGI2A, Université d'Artois
Lionel POURNIN	EFREI
Aurélien QUESTEL	LIP6, , Université Pierre et Marie Curie
Christophe RAPINE	Université de Lorraine
Gautier STAUFFER	Université de Bordeaux
Raouia TAKTAK	LAMSADE, Université Paris-Dauphine
Sophie TOULOUSE	LIPN, Université Paris-Nord
Sonia VANIER	Université Paris 1
Mathieu VanVYVE	CORE, Louvain-La-Neuve

SPOC 8 : 2/03/12

fouilhoux — 2012-01-19T15:35:11Z

journee.html

8ème Séminaire POC

Le VENDREDI 2 MARS 2012

Au laboratoire LIP6 de l'Université Pierre et Marie Curie - Paris 6
4 place Jussieu Paris 6 CEDEX 05

Tour 26 - Premier étage - Couloir 25-26 - Salle 105

Accès

Sur le thème

"Formulations étendues"

Pour s'incrire : envoyer un mail à gdt.poc at gmail.com

INSCRITS à la journée JSPOC8

9h30-9h45	Accueil des participants
10h00-12h00	Extended Formulations in Combinatorial Optimization Volker KAIBEL (Otto-von-Guericke Universität Magdeburg) The polytopes that seem to be associated naturally with combinatorial optimization problems tend to have rather complicated linear descriptions. However, in some cases there are very simple, nice, and easy to handle extended formulations for such polytopes, i.e., linear descriptions of higher dimensional polyhedra that can be projected linearly to the polytopes of interest. In this lecture, we discuss some aspects of this approach that has attracted quite some attention recently. Besides introducing the concept, we present some selected examples of extended formulations in particular meant to overview some techniques for their construction, and we discuss fundamental limitations of the approach, where we mainly concentrate on combinatorial obstructions that sometimes prevent the existance of small extended formulations.
12h00-13h30	REPAS
13h30-14h15	Using extended formulations to solve MIPs in practice Mathieu VanVYVE (CORE, Louvain-La-Neuve) We consider the following practical setting. The MIP that you want to solve is hard in the sense that the LP relaxation is weak, and the built-in cutting planes of your favourite solver are not very effective. Moreover, you know how to reformulate part of the problem using an extended formulation, yielding much sharper bounds. Unfortunately the resulting LP relaxation is too large to be used in a branch-and-bound framework. We describe several practical approaches to leverage the knowledge of the extended formulation. The first one is to use an approximate extended formulation, that is ideally nearly as strong but more compact than the original one. The second one is to solve the LP relaxation of the extended formulation, and then heuristically fix some variables and solve this restricted MIP, generating a heuristic solution, but with a guarantee of quality. The third one is to use the extended formulation to quickly generate strong valid inequalities in the original variable space. We illustrate these three approaches on practical examples.
14h15-15h00	Linear vs. Semidefinite Extended Formulations : Exponential Separation and Strong Lower Bounds Samuel FIORINI (Université de Bruxelles) We solve a 20-year old problem posed by M. Yannakakis and prove that there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the maximum cut problem and the stable set problem. These results follow from a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs. This is a joint work with Serge Massar (ULB), Sebastian Pokutta (Erlangen), Hans Raj Tiwary (ULB), Ronald de Wolf (CWI).
15h00-15h15	Questions ouvertes
15h15-15h30	PAUSE
15h30-16h15	Extended formulations for the design of approximation algorithms : an example in inventory control Gautier STAUFFER (Université de Bordeaux) Linear programming plays a central role in the design of efficient approximation algorithms. In particular, many approximation algorithms builds on the 'natural' linear programming formulation of the problem and apply some rounding techniques and/or primal-dual schemes. In this talk, we show how extended formulations can help in the design of approximation algorithms. We illustrate those findings on the one- warehouse multi-retailer problem, a standard in inventory control.
16h15-17h00	Extended Formulations for the Survivable Network Design Problem with Hop Constraint Ibrahima DIARRASSOUBA (Université du Havre) Survivability problems are one of the key issues when designing telecommunication networks. In these problems, one look for a network which is still functionning in case of failure of a given number of equipments of that network. One may also combine survivability issues with some routing constraints such as length bound on the routing paths (hop constraint). In this talk, we consider the survivable network design problem with hop-constraint in undirected networks. We present extended formulations for the problem in the case where the length of the routing paths is bounded by 3. We compare these formulations in terms of linear relaxation and compare them with the so-called natural formulation (formulation based on the design variables). We also discuss some computational results on the problem.
17h00	Clôture de la journée

Cours 6-8/06/11

fouilhoux — 2011-05-08T14:45:57Z

Mini-cours doctoral 2011

Ce cours s'adresse aux chercheurs voulant découvrir et échanger sur l'optimisation de la chaîne logistique globale, au travers notamment d'applications en transport. Ce cours nécessite des connaissances en programmation linéaire et algorithmique. Le cours aborde aussi bien des méthodes approchées (heuristiques, méta-heuristiques, méthodes hybrides, métaheuristiques, …) s'adaptant à cesproblèmes que des algorithmes exacts (branch-and-cut, branch-and-price) s'appuyant sur les modélisations mathématiques et les études polyédrales des problèmes concernés.

Ces cours sont gratuits. Ils offrent la possibilité de faire éventuellement valider un module d'école doctorale. La demande devra pour cela être faite auprès de l'école doctorale de votre université.

Intervenants

Dominique Feillet : Professeur à l'Ecole des Mines de Saint-Etienne

Nenad Mladenovic : Reader in the School of Mathematics, Brunel University,

Frédéric Semet : Professeur à l'Ecole Centrale de Lille

Paolo Toth : Professor in the University of Bologna, Italia

Dates

Accueil : lundi 6 juin de 11h30 à 12h puis de 13H30 à 14h dans le hall du bâtiment ISTV 2 du campus du Mont Houy.

Lundi 6 juin	14h00 - 18h00	Nenad Mladenovic	Résumé
Mardi 7 juin	8h00 - 12h00	Frédéric Semet	Résumé
	14h00 - 18h00	Dominique Feillet	Transparents
Mercredi 8 juin	8h00 - 12h00	Paolo Toth	Résumé

Lieu

Amphi 200, batiment ISTV2, Campus du Mont Houy, Université de Valenciennes et du Hainaut-Cambrésis

Inscription

Les inscriptions se font en même temps que l'inscription aux JPOC7.

Inscrits JSPOC 7

fouilhoux — 2010-11-04T14:21:40Z

Inscrits à la journée de travail JSPOC "Partitionnement de graphes et problèmes connexes"

Pascale BENDOTTI		EDF, Paris
Amal BENHAMICHE		LAMSADE, Paris
Bruno BODIN		LIP6, Paris
Sylvie BORNE		LIPN, Paris
Denis CORNAZ		LAMSADE, Paris
Julien DARLAY		G-SCOP, Grenoble
Mohamed DIDI BIHA		Caen
Eric DUCHENNE		LAMIH, Valenciennes
Pierre FOUILHOUX		LIP6, Paris
Makhlouf HADJI		Telecom Sud Paris, Evry
A. Ridha MAHJOUB		LAMSADE, Paris
Karima MOUHOUBI		LIPN, Paris
Moustafa NAKECHBANDI		Le Havre
Hacène OUZIA		LIP6, Paris
François PELLEGRINI		LaBRI, Bordeaux
Pierre PESNEAU		IMB, Bordeaux
Jean-Mathieu SEGURA		LIP6, Paris
Raouia TAKTAK		LAMSADE, Paris
Xin TANG		Polytech, Tours
Sophie TOULOUSE		LIPN, Paris
Lilia ZAOURAR		LIP6, Paris

SPOC 7 : 7/12/10

fouilhoux — 2010-11-04T14:18:21Z

journee.html

7ème Séminaire POC

Le MARDI 7 DECEMBRE 2010

A l'Institut Henri Poincaré de l'Université Paris 6
11 rue Pierre et Marie Curie 75231 Paris CEDEX 05

Salle 201

Accès

Sur le thème

"Partitionnement de graphes et problèmes connexes"

Pour s'incrire : envoyer un mail à gdt.poc at gmail.com

INSCRITS à la journée JSPOC7

Programme prévisionnel*

9h30-9h45	Accueil des participants
9h45-10h00	Introduction à la journée
10h00-11h00	Défis actuels pour le partitionnement parallèle de très grands graphes François Pellegrini
11h00-12h00	Etude polyédrale pour quelques problèmes de partitionnement dans les graphes Mohamed Didi-Biha
12h00-12h30	Questions ouvertes
12h30-14h00	REPAS
14h00-14h30	A cutting plane based integer formulation for graph coloring Pierre Fouilhoux
14h30-15h00	Matrices Jacobiennes et Partitionnement de Graphes Sébastien Martin
15h30-16h00	Questions ouvertes
16h00-16h30	PAUSE
16h30-17h00	The Location-Dispatching Problem : polyhedral results and Content Delivery Network Design Jean-Mathieu Ségura
17h00-17h45	Réunion comité d'animation POC
17h45	Clôture de la journée

* Toute correspondance avec le programme réel ne serait que le fruit d'une coïncidence fortuite

Cours 22-24/03/10

fouilhoux — 2010-10-05T12:59:34Z

Mini-cours doctoral 2010

Cutting plane methods for integer and combinatorial optimization

Ce cours est donné dans le cadre de la conférence internationale ISCO 2010.

Il s'adresse aux chercheurs voulant découvrir les aspects théoriques et pratiques des approches polyédrales pour résoudre des problèmes d'optimisation combinatoire. Ce cours nécessite des connaissances en programmation linéaire et algorithmique.

Page web du mini-cours

ISCO spring school

SPOC 6 : 27/11/09

fouilhoux — 2009-11-09T15:26:10Z

journee.html

6ème Séminaire POC

Le VENDREDI 27 NOVEMBRE 2009

Au laboratoire d'informatique de Paris 6 (LIP6), Site Passy-Kennedy
104 Avenue du président Kennedy 75016 Paris

Salle 549

Accès LIP6

Sur le thème

"Multi-coupes, stable,..."

Pour s'incrire : envoyer un mail à poc at lamsade.dauphine.fr

INSCRITS à la journée JSPOC6

Programme prévisionnel*

9h30-9h45	Accueil des participants
9h45-10h00	Introduction à la journée
10h00-11h00	Etude polyédrale pour quelques problèmes de partitionnement dans les graphes Mohamed Didi-Biha
11h00-11h30	An extended characterization of the stable set polytope of claw-free graphs Gautier Stauffer
11h30-12h00	Questions ouvertes
12h00-13h45	REPAS
13h45-14h15	Multicoupe maximum et perte minimum de multiflot Denis Cornaz
14h15-14h45	Résolution du problème de ramassage et livraison mono-véhicule préemptif asymétrique unitaire Mathieu Lacroix
14h45-15h10	Questions ouvertes
15h10-15h30	PAUSE
15h30-16h00	Une méthode de décomposition de Benders pour le problème d'optimisation des feux de carrefour Viet Hung NGuyen
16h00-16h45	Réunion POC
16h45	Clôture de la journée

* Toute correspondance avec le programme réel ne serait qu'une coïncidence fortuite

Inscrits JSPOC 6

fouilhoux — 2009-11-09T15:26:02Z

Inscrits à la journée de travail JSPOC "Multi-coupes, Stables, ..."

Walid BEN AMEUR		INT, Paris
Sylvie BORNE		LIPN, Paris
Hilaire CHEVREAU		LCT, Paris
Denis CORNAZ		LAMSADE, Paris
Mohamed DIDI BIHA		Caen
Pierre FOUILHOUX		LIP6, Paris
Eric GOURDIN		Orange Labs, Paris
Mathieu LACROIX		LAMSADE, Paris
A. Ridha MAHJOUB		LAMSADE, Paris
Sébastien MARTIN		LAMSADE, Paris
Viet Hung NGUYEN		LIP6, Paris
Pierre PESNEAU		IMB, Bordeaux
Gérard PLATEAU		LIPN, Paris
Aurélien QUESTEL		LIP6, Paris
Gautier STAUFFER		IMB, Bordeaux

Cours 8-10/06/09

fouilhoux — 2009-04-20T08:51:50Z

Mini-cours doctoral 2009

Autour des méthodes de décomposition en optimisation combinatoire

Ce cours s'adresse aux chercheurs voulant découvrir les aspects théoriques et pratiques des approches polyédrales pour résoudre des problèmes d'optimisation combinatoire. Ce cours nécessite des connaissances en programmation linéaire et algorithmique.

Le cours traite des méthodes de décomposition (Dantzig-Wolfe, Benders, ...) pour résoudre des problèmes d'optimisation combinatoire souvent de grande taille et ayant des sous-problèmes faciles à résoudre.

Intervenants

François Vanderbeck

Anass Nagih

Philippe Meurdesoif

Sophie Michel

Dates

Lundi 8 juin
14h00 - 16h00, 16h15 - 18h15	François Vanderbeck	Salle 1

Mardi 9 juin
8h15 - 19h15, 10h30 - 12h30	Sophie Michel	Salle 2

14h00 - 16h00, 16h15 - 18h00	Philippe Meurdesoif	Salle 2

Mercredi 10 juin
8h15 - 19h15, 10h30 - 12h30	Anass Nagih	Salle 2

Lieu

Salle 1 de l'Institut de Mathématiques de Bordeaux.

Inscription

Les inscriptions se font en même temps que l'inscription aux JPOC6.

Jack Edmonds

fouilhoux — 2009-03-24T09:49:30Z

Jack Edmonds

Printable version (pdf)

Some quotes from Lex Schrijver's 2000 page, 3 volume, slip-cased or CD, 87 euro book, “Combinatorial Optimization : Polyhedra and Efficiency”, Springer, 2003 :

“Pioneered by the work of Jack Edmonds, polyhedral combinatorics has proved to be a most powerful, coherent, and unifying tool throughout combinatorial optimization. Not only has it led to efficient (that is, polynomial-time) algorithms, but also, conversely, efficient algorithms often imply polyhedral characterizations and related min-max relations. It makes the two sides closely intertwined.”

“In the 1960s, Edmonds advocated calling an algorithm efficient [or “good”] if its running time is bounded by a polynomial in the size of its representation. Since then, this criterion has won broad acceptance, also because Edmonds found polynomial-time algorithms for several important combinatorial optimization problems.”

“Edmonds conjectured that there is no polynomial-time algorithm for the travelling salesman problem. In language that was developed later, this is equivalent to NP≠P.”

In the paper, “Minimum Partition of a Matroid into Independent Sets”, 1965, Edmonds introduced the concept of NP (that is, existential polytime) and good characterizations (NP ∩ coNP) by using a parable of the absolute supervisor. The paper also introduced the concept of using black-box recognition of independence as an algorithmic oracle.

In published lectures (on ‘Polyhedral Combinatorics') at the Calgary International Conference on Combinatorial Structures, Calgary, Alberta, 1969, he laid out main theorems about submodular functions, including a good characterization of the minimum of a submodular function, and the theorems which have been used many times since then in various algorithms for minimizing a submodular function.

Also in those lectures he presented with Dick Karp the first polynomial-time algorithms for network flows, and asked for strongly polynomial algorithms (i.e., which do not depend on bit-length of costs and capacities), achieved by Eva Tardos in 1985.

Also in those lectures he presented, with Ellis Johnson and Scott Lockhart, the software, ‘Blossom I', which algorithmically unifies network flow problems and matching problems, using bidirected graphs, and provides the linear programming equivalent.

In 1964, Edmonds had already given the first polynomial-time version of Gaussian elimination for rational matrices (so that the bit-length stays non-exponential), and had posed the problem of determining the rank of a matrix of rational multivariate polynomials (in general still deterministically open, and sometimes called Edmonds' matrix problem).

Around that time, helping Alfred Lehman with a project for Walter Reed Hospital, he introduced the graph isomorphism problem and solved it for trees. His write-up appeared, with an advocacy of polynomial time, in a graph theory book by Busacker and Saaty.

In the late 1970s with Arnaldo Mandel and Komei Fukuda, he derived the piecewise linear sphere-system representation of oriented-matroids, and used it to show non-degenerate cycling of Bland's objective-based OM generalizations of the simplex method, and to describe some new non-cycling algorithms.

In the late 1970s with Kathie Cameron, and with Julian Araoz and others, he solved some combinatorial optimization problems by ‘extended formulations'.

Between 1975 and 1983, he had 15 successful PhD supervisions, more than the rest of his 120-professor math faculty. In the decade following he was isolated and constructively dismissed. He then devoted two years to collecting the support of a majority of the university's regular faculty and to contesting successfully the dismissal. Sociology books have been based on this ‘Edmonds affair'.

Edmonds has never obtained a PhD for himself, except a 2006 honorary doctorate at the University of Southern Denmark in Odense where he chatted with the Queen.

In a Master's degree essay he did do his ‘rotation-theorem' which has become a well-known foundation of the field of graphs in surfaces. However while a PhD student in 1961 he dropped out of academia, not much approving of it.

In 1985, Edmonds was awarded the John Von Neumann Theory Prize by INFORMS.

Some quotes from the citation :

“Jack Edmonds is one of the creators of the fields of combinatorial optimization and polyhedral combinatorics.

His 1965 paper “Paths, Trees and Flowers” was one of the first papers to suggest the possibility of establishing a mathematical theory of efficient combinatorial algorithms. […]

Edmonds gave remarkable polynomial-time algorithms for the construction of maximum matchings. Even more importantly, these papers showed how a good characterization of the polyhedron associated with a combinatorial optimization problem could lead, via the duality theory of linear programming, to the construction of an efficient algorithm for the solution of that problem. […]

His beautiful theory of matroid partition and intersection remains one of the deepest results in the area. This work further illustrates the deep interconnections between combinatorial min-max theorems, polyhedral structure, duality theory and efficient algorithms. […]

in collaboration with his many outstanding students, he continued to explore combinatorial optimization problems and the associated polyhedra. ... His work revolved around the theories of submodular functions, total dual integrality and oriented matroids. […]

Edmonds has expended immeasurable time and effort assisting young researchers. Through his influence many outstanding young mathematicians have been drawn to the field of theoretical operations research.”

An ‘Existentially Polytime (EP) theorem' is one which, like ‘good characterization', asserts the existence of something any instance of which is easy to recognize relative to the size of the hypothesis-instance. Most of the structural existence theorems regarded by combinatorists as pretty are EP. In recent times, Edmonds has continued working to advocate studying algorithms which find an instance of what an EP theorem says exists –

For example, a direct algorithm for the theorem that :

In any graph, there exists either a Berge obstruction or a clique and coloring the same size.

Or for the theorem that :

For any closed surface triangulation, and any subset of its triangles which partitions its vertices, there exists another different subset of its triangles which partitions its vertices.

Or for the theorem that :

For any Hamiltonian path P in a graph G such that G minus the edges of P is connected, there exists another different Hamiltonian path in G with the same ends as P.