Operations Research Symposium

in the honour of

Thomas Liebling and Dominique de Werra

Registration deadline: May 31, 2008.

Today is November 21, 2009.

Sorry, the deadline for registration is over. If you want to participate, send an email to Bernard Ries.

• Lecturers
• Schedule
• Abstracts
• Registration
• Payment
• Accomodation
• Transportation

The event is generously sponsored by

The Institute of Mathematics at EPFL
The Faculty of Basic Sciences at EPFL
The Swiss Association of Operations Research

Lecturers

Click on the picture or the name to access the personnal home page

Schedule

Dinner

Cocktail and dinner will take place at the restaurant Casino de Montbenon, Allée E.-Ansermet, 3, Lausanne 1003

View Larger Map

Lectures

Armen Asratian

Interval edge colorings of graphs and related problems

An interval edge coloring of a graph G is a coloring of the edges of G with colors 1,2,3,... such that the edges incident with each vertex are assigned different consecutive colors. Some combinatorial and scheduling problems can be formulated in terms of interval edge colorings. For example, timetable problems with compactness requirement (i.e. the lectures of each teacher and each class have to be scheduled at consecutive periods) may be formulated as problems of interval edge colorings of bipartite graphs. We will survey available results on interval edge colorings and present some new results on this topic.

Jacek Blazewicz

From scheduling to DNA sequencing and backward

In the talk we will illustrate an interflow of ideas between two, at first glance unrelated areas, scheduling and DNA sequencing . The relation between the two fields is observed by modeling the two problems with the use of special classes of graphs. The impact on the assembling stage of genome reading is discussed.

Endre Boros

A strongly polynomial preprocessing for quadratic binary optimization

Building on several earlier results we propose a network flow based preprocessing algorithm aiming at simplifying and decomposing a quadratic unconstrained minimization problem in polynomial time. We can demonstrate on numerous applications, including MRI image processing that this method is in fact frequently finds an optimal solution. Joint work with Peter L. Hammer and Gabriel Tavares.

Michele Conforti

Simple mixed integer sets

An Integer Program is Mixed whenever some of the variables are continuous are allowed to be continuous. MIP's arise e.g. in Production Planning, when some some integer variables model decisions (in which period to produce) and some continuous variables model production levels. As in (pure) IP, it is important to represent the set of feasible solutions as vertices of a polyhedron, described by linear inequalities. However, in the mixed case, this seem to be quite challenging and some of the tools that have been used are different from the ones that have been so successful, for instance, in polyhedral combinatorics. We will survey some results in this area obtained jointly with M. DiSumma, F. Eisenbrand, B. Gerards, L. Wolsey and G. Zambelli.

Gérard Cornuéjols

On the Facets of Mixed Integer Programs with Two Integer Variables and Two Constraints

We consider an infinite relaxation of the mixed integer linear program with two variables and two constraints, and we give a complete characterization of its facets. We then derive an analogous characterization of the facets of the underlying finite integer program. This is joint work with Francois Margot.

Martin Charles Golumbic

Edge intersection graphs of single bend paths on a grid

We combine the known notion of the edge intersection graphs of paths in a tree with a VLSI grid layout model to introduce the edge intersection graphs of paths on a grid. Let P be a collection of nontrivial simple paths on a grid G. We define the edge intersection graph EPG(P) of P to have vertices which correspond to the members of P, such that two vertices are adjacent in EPG(P) if the corresponding paths in P share an edge in G. An undirected graph G is called an edge intersection graph of paths on a grid (EPG) if G = EPG(P) for some P and G, and PG is an EPG representation of G. We prove that every graph is an EPG graph. A turn of a path at a grid point is called a bend. We consider here EPG representations in which every path has at most a single bend, called B₁-EPG representations and the corresponding graphs are called B₁-EPG graphs. We prove that any tree is a B₁-EPG graph. Moreover, we give a structural property that enables to generate non B₁-EPG graphs. Furthermore, we characterize the representation of cliques and chordless 4-cycles in B₁-EPG graphs. We also prove that single bend paths on a grid have Strong Helly number 3. Joint work with Marina Lipshteyn and Michal Stern.

Martin Grötschel

Alcuin, Wilhelm Tell and multicriteria path finding

Persons who want to find a path do not always seek for the "shortest" one. Starting with historical examples, I will survey mulicriteria path finding problems and provide real-world instances of large scale, for which theory and software has been developed in my research group, where paths must be determined that have to satisfy various resource constraints.

Alain Hertz

Automated generation of conjectures on forbidden subgraph characterization

Given a class F of graphs, a forbidden subgraph characterization (FSC) is a set S of graphs such that a graph G belongs to F if and only if no graph of S is isomorphic to an induced subgraph of G. FSCs play a key role in graph theory, and are at the center of many important results obtained in that field. We present methods that automate the generation of conjectures on FSCs, or conditions to have an FSC. We also use these methods to reproduce some known results of graph theory, as well as to discover new ones. This is a joint work with Christian Desrosiers, Philippe Galinier and Pierre Hansen.

Jakob Krarup

Many happy returns!

Two of today's distinguished OR researchers were 15 years old when Regnecentralen (RC) completed the construction of the first digital computer in Denmark. The country's first OR division was established at RC shortly after. Embarking from a remote past, parts of the sub- sequent development are accounted for.

Vadim Lozin

Stability preserving transformations of graphs

A useful tool to simplify the maximum stable set problem or solve it efficiently for graphs in special classes is based on transforming a given graph G into a new graph G' in such a way that the difference between the stability number of G and that of G' is easy to compute. We survey available results on this topic and propose a unified approach for the description and systematic development of graph transformations for the maximum stable set problem. The approach is illustrated by a number of new examples.

Nelson Maculan

About the Kissing Number Problem

The kissing number is the maximum number of unit spheres that can be adjacent to a given unit sphere. This talk gives current results based on mathematical programming formulation based techniques for computing lower and upper bounds to the kissing number. This is a joint work with Leo Liberti.

François Margot

Testing Cut Generators for MILP

This talk describes recent work on the testing of cut generators for integer linear programming. The goal of this work is to build experiments that can be used for comparing slight variants of a cut generator. Cut generators should be compared along several dimensions, for example the precision (what is the likelihood of a feasible solution to be cut?), the strength (are the cuts obtained stronger or weaker?), the speed of the generator, and the speed of the reoptimization after cuts are added. While generator and reoptimization speeds are relatively easy to test, both precision and strength are more difficult to evaluate. Results for testing several variants of Gomory cut generators and several variants of reduce-and-split cut generators are presented. The approach followed is in the spirit of the empirical analysis of algorithms advocated by Hooker and McGeoch, among others. The object of empirical analysis of algorithms is to use experiments to suggest hypotheses about the behavior of algorithms. Hypotheses are then tested using controlled experiments, well-grounded in statistical analysis.

Leslie Trotter

Resolving linear inequalities by successive orthogonal approximation

We discuss several algorithms which use repeated orthogonal projection to determine a solution for a system of linear inequalities. Finite convergence results will be given and geometric relations to the classical Agmon-Motzkin-Schoenberg procedure will be discussed. Computational results will also be presented.

Registration

There is no registration fee, but there is a participation fee of 100 CHF (130 CHF for late registrations) covering the lunch and the Gala Dinner on Monday, as well as the coffee breaks.

Registration deadline: May 31, 2008.

Today is November 21, 2009.

Sorry, the deadline for registration is over. If you want to participate, send an email to Bernard Ries.

Current number of registered participants: 95

• Altinakar Sivan, EPFL-ROSE
• Amaldi Edoardo, DEI, Politecnico di Milano, Italy
• Asratian Armen, Linköping University, Sweden
• Aviolat Frédéric, ID Informatique
• BENTZ Cédric, LRI, Université Paris-Sud et CNRS
• Benzaken Claude, Grenoble
• Bierlaire Michel, EPFL
• Blanc Jocelyne, IMA
• Blazewicz Jacek, Poznan University of Technology
• Boros Endre, Rutgers University, USA
• Ceselli Alberto, DTI - University of Milan
• Cochand Maurice, D-Math, RTHZ
• Conforti Michele, Università degli Studi di Padova, Italy
• coray giovanni, epfl (prof. hon.)
• Cornuéjols Gérard, Carnegie Melon University, USA and Université de la Méditerranée, Marseille, France
• Correa José, EPFL - DISOPT
• Costa Marie-Christine, CEDRIC-CNAM-Paris
• Crittin Frank,
• Dalang Robert, EPFL
• de Werra Dominique, EPFL - ROSE
• Donzé Michael, A3 (EPFL alumni 2006)
• Eggenberg Niklaus, TRANSP-OR, EPFL
• Eisenbrand Friedrich, EPFL
• Ekim Tinaz, Bogazici University - Industrial Engineering Department
• Emery Sarah, epfl
• Ferrez Jean-Albert, IDIAP Research Institute
• Fonlupt Jean, Faculté de Mathématiques, Université Pierre et Marie Curie, Paris France.
• Frejinger Emma, TRANSP-OR, EPFL
• Fukuda Komei, ETH Zurich
• Golumbic Martin, University of Haifa
• Groeflin Heinz, Université de Fribourg
• Grötschel Martin, TU Berlin and Konrad-Zuse-Zentrum für Informationstechnik Berlin, Germany
• Hasler Martin, LANOS-I&C-EPFL
• HELBLING Jean-Marie, EPFL-SMA
• Herriger Hans, SVOR
• Hertz Alain, Ecole Polytechnique, Montréal, Canada
• Hêche Gérard, EPFL-ROSO
• Hêche Jean-François, EPFL-ROSO
• Jost Vincent, LIX, CNRS, Ecole Polytechnique, Palaiseau
• Klinkert Andreas, Institute of Data Analysis and Process Design IDP, Zurich University of Applied Sciences ZHAW
• Kobler Daniel, PrismInvest
• Krarup Jakob,
• Legradi Katalin, Germany
• Leroy-Beaulieu Benjamin, EPFL
• LEVEQUE Benjamin, EPFL
• Leyvraz Jean-Pierre, EPFL
• Liberti Leo, Ecole Polytechnique de Palaiseau
• Liebling Thomas M., EPFL - ROSO
• Liedermann Peter, FernUniversität in Hagen / University of Hagen
• Limouzy Vincent, Université de Paris Diderot
• Lozin Vadim, University Warwick, UK
• Maculan Nelson, Universidade Federal do Rio de Janeiro
• MAFFRAY Frédéric, CNRS, Laboratoire G-SCOP
• Margot François, Carnagie Mellon University
• Mittaz Michel, Institut de Recherches Robert Bosch SA
• Möhring Rolf, Technische Universität Berlin
• Musitelli Antoine, Università di Padova, Italy
• Naddef Denis, Laboratoire G_SCOP-INPG
• Naves Guyslain, G-SCOP, Grenoble
• Osorio Carolina, TRANSP-OR, EPFL
• Pach Janos, EPFL
• Picouleau Christophe, Cedric-CNAM
• Plateau Gérard, LIPN, UMR CNRS 7030, Université Paris 13
• Plumettaz Matthieu, EPFL
• Pournin Lionel, ROSO - EPFL
• Preissmann Myriam, CNRS, laboratoire G-SCOP, Grenoble
• Prodon Alain, EPFL
• Pusztaszeri Jean-François, ILOG, Inc.
• Rambau Jörg, LS Wirtschaftsmathematik, Universität Bayreuth
• Reiner Gerald, Université de Neuchâtel
• Ries Bernard, EPFL-ROSE
• Robin Thomas, Transp-or laboratory, EPFL
• Rosta Vera, Renyi Institute of Mathematics
• Rothvoss Thomas,
• Ruegg Marianne, ENAC INTER TRANSP-OR
• Salani Matteo, TRANSP-OR, EPFL
• Schindl David, -
• Shmonin Gennady, EPFL-DisOpt
• Shokrollahi Amin, EPFL
• SOLOT Philippe, AICOS Technologies AG, CH-4057 Basel
• Stagno Antonio, Xtenso
• Stähly Paul, University of St. Gallen
• Taillard Éric, HEIG-Vd
• Tardella Fabio, University of Rome "La Sapienza"
• Thémans Michaël, Nestlé Research Center
• Trautmann Norbert, University of Bern
• Trotter Leslie, Cornell University
• Troyon Michel, Bobst SA
• Tsukahara Michel, EPFL-ROSO
• Vacca Ilaria, TRANSP-OR, EPFL
• Varone Sacha, Haute Ecole de Gestion de Genève (Switzerland)
• Vial Jean-Philippe, ORDECSYS et Professeur honoraire, Université de Genève
• Widmer Marino, Université de Fribourg - DIUF
• Wilkes John, IUKB, Sion, VS
• Zenklusen Rico, ETH Zurich

Payment

Select your name in the list of registered participants. Than proceed to the secured online payment form.

Accomodation

EPFL-rates apply to the following hotels. The prices below are indicative and may not correspond to the actual price charged by each hotel. Please check directly with the hotel for detailed information.

You may also consider the International Education Support Scheme provided by Hotels Combined. Click here for more info

In Lausanne

Hôtel Elite

Avenue Ste-Luce 1
1003 Lausanne
tél: +41 21 320 23 61
fax: + 41 21 320 39 63
single: 120.00; double: 179.00

Hôtel Alagare

Minotel Suisse
Rue du Simplon 14
1006 Lausanne
tél: +41 21 617 92 52
fax: +41 21 617 92 55
single 114.00; double: 159.00

Hôtel Alpha-Palmiers

Fassbind Hotels
Rue du Petit.Chêne 34
1003 Lausanne
tél: +41 21 555 59 99
fax: +41 21 555 59 98
single: 190.00; double: 220.00

Swiss Youth Hotels

Bois-de-Vaux 36, 1007 Lausanne
tél: +41 21 626.02.22
fax: +41 21 626.02.26
adresse email: lausanne@youthhostel.ch
single: 78.00; double: 98.00

EPFL area

Hotel Pré-Fleuri***

Rue du Centre 1, 1025 St-Sulpice.
Email: prefleuri@bluewin.ch
Tél. 021 691 20 21
Fax 021 691 20 20

Motel des Pierrettes** St-Sulpice

10 minutes walk to EPFL
Route cantonale 19, 1025 St-Sulpice
Phone: +41 21 691 25 25.
It has no restaurant.
Single: 100.00; double: 140 (special price for EPFL hosts)

Hostellerie du Débarcadère

Chemin du Crêt 7, 1025 St-Sulpice,
It belongs to "Relais& Châteaux"
Web-site: www.debarcadere.ch
Single: 163.00; double: 250.00 (special price for EPFL hosts)

Novotel Lausanne Bussigny

35, Route de Condémines, 1030 Bussigny
(15 minutes by car, no bus possibilities)
Single: 168.00; double: 190.00 (special price for EPFL hosts)

Transportation

The easiest way to get to EPFL is to take the train from Geneva Airport to Renens. In Renens, take the light-rail (called M1) towards Lausanne. There is a stop at EPFL. The travel time is about 1 hour.

A map of the bus and metro network can be found here and time tables are available at the Lausanne Transport web page. Note that tickets must be bought before departure in machines only accepting coins. The price for a one-way ticket from the center of Lausanne to EPFL is 2.80 Fr. (two zones) and most machines do not give back change.

Check the Swiss Federal Railways website.

To navigate within EPFL, use map.epfl.ch.

Consult also this page