English only
INTER  >  TRANSP-OR > 3ième cycle romand de recherche opérationnelle




The 2010 Seminar of the "3ème cycle romand de Recherche Opérationnelle" will take place from Sunday January 17 to Thursday January 21 at hôtel de l'Europe, in Zinal, VS (directions).

Organization: Michel Bierlaire

Registration deadline: November 30, 2009.

Today is June 29, 2010.

Sorry, the deadline for registration is over.


Anupam Gupta

Anupam Gupta is associate professor at the Department of Computer Science, Carnegie Mellon University. His research interests are in Theoretical Computer Science, with an emphasis on Approximation Algorithms and Metric Embeddings.

Metric Embeddings and Algorithms

Over the past 15 years, the algorithmic study of metric spaces and metric embeddings has yielded a very useful set of tools for designing algorithms. In these lectures, I will cover some of the fundamental algorithmic results in this area, along with directions for further research: the lectures will loosely be on: (a) approximating metric spaces by trees, (b) approximating them by Euclidean and other normed spaces, (c) dimensionality reduction, and (d) other classical and new results in the algorithmic study of metric spaces.

Download here a copy of the slides
Anupam Gupta

Maria Grazia Speranza

Grazia Speranza is full professor at the Department of Quantitative Methods at the University of Brescia, Italy. Her research activities are focused on optimization in logistics, mixed integer programming models and solution algorithms for the joint min-imization of transportation and inventory costs, vehicle routing models and algorithms, combinatorial optimization models and algorithms, worst-case analysis, competitive analysis of on-line algorithms for scheduling problems; optimization models for portfolio optimization.

New classes of vehicle routing problems

In this series of seminars I will present and discuss new classes of vehicle routing problems (VRP). The Travelling Salesman Problem is the basic problem of the VRP class. In most of the traditional VRP, all customers are assumed to be known in advance, all require service, all have to be served the same day and each customer must be visited by exactly one vehicle. The goal is to minimize the distance travelled. I will present some less traditional classes of problems, on which the literature available is still limited and on which it is interesting to advance research:

  • the split delivery vehicle routing problem, where a customer may be visited by more than one vehicle;
  • vehicle routing problems with profits, where a subset of the potential customers has to be identified to maximize the profit collected;
  • inventory routing problems, where the service day has to be decided for each customer and inventory costs or inventory capacity are taken into account;
  • on-line routing problems, where the information on the customers is revealed over time.
I will introduce the problems and discuss mathematical programming formulations, complexity results, properties, exact and heuristic solution approaches, theoretical analysis of algorithms.

Download here a copy of the slides
M. Grazia Speranza

Tentative scheduleTop

  Sunday 17 Monday 18 Tuesday 19 Wednesday 20 Thursday 21
08h30 - 09h00   Speranza Gupta Speranza Gupta
09h00 - 09h30
09h30 - 10h00
10h00 - 10h30 break break break break
10h30 - 11h00 Gupta Speranza Gupta Speranza
11h00 - 11h30
11h30 - 12h00
12h00 - 17h00
Sport and discussions  
17h00 - 17h30 Vacca Klaus Lorini
17h30 - 18h00 Uldry Rumley Zorgati
18h00 - 18h30 Welcome cocktail Pritchard
18h30 - 19h00


Sorry, the deadline for registration is over.

Current number of registered participants: 46

  • Mr Adjiashvili David, ETH Zurich
  • Mr Alipour Masoud, EPFL
  • Mr Alp Arda, Institut de l'entreprise, Université de Neuchâtel
  • Ms ALVIM Adriana, UNIRIO / HEIG-VD
  • Mrs Atasoy Bilge, TRANSP-OR, EPFL
  • Mr Baumann Philipp, Department of Business Administration, University of Bern
  • Mr Bierlaire Michel, TRANSP-OR, EPFL
  • Mr Bürgy Reinhard, Université de Fribourg - DIUF
  • Mr CHEN Jingmin, TRANSP-OR, EPFL
  • Mr Danalet Antonin, Transport and Mobility Laboratory, EPFL
  • Ms Dunkel Juliane, Massachusetts Institute of Technology
  • Mr Eggenberg Niklaus, Transport and Mobility Laboratory, EPFL
  • Mr Eisenbrand Fritz, EPFL
  • Mr Fetiarison Mamy, Transport and Mobility Laboratory, EPFL
  • Mr Flötteröd Gunnar, Transport and Mobility Laboratory, EPFL
  • Mr Foniok Jan, ETH Zürich
  • Mr Fulek Radoslav, EPFL
  • Mr Gupta Anupam, Carnegie Mellon University
  • Mr Hurtubia Ricardo, TRANSP-OR, EPFL
  • Mr Karrenbauer Andreas, EPFL
  • Mrs Karrenbauer Mrs, (spouse)
  • Mr Keszegh Balázs, DCG, EPFL
  • Mr Klaus Lorenz, ETH Zurich
  • Mr Lorini Sandro, University of Geneva
  • Mr Moric Filip, DCG, EPFL
  • Mr Mutsanas Nikolaus, IDSIA
  • Mr Niemeier Martin, DISOPT - EPFL
  • Mr Pach Janos, EPFL
  • Mr Palvolgyi Domotor, DCG, EPFL
  • Mr Pritchard David, DISOPT, EPFL
  • Mr Rabta Boualem, Entreprise Institute, University of Neuchâtel
  • Mr Reiner Gerald, Université Neuchatel
  • Mr Robin Thomas, TRANSP-OR, EPFL
  • Mrs Salas Francisca, (spouse)
  • Mrs Speranza Grazia, University of Brescia, Italy
  • Mr Speranza Mr, (spouse)
  • Mr Stamoulis Georgios, IDSIA
  • Mr Taillard Eric, HEIG-Vd /HES-SO
  • Mr Trautmann Norbert, Université de Berne
  • Mr Uldry Marc, Université de Fribourg - DIUF
  • Ms Vacca Ilaria, Transport and Mobility Laboratory, EPFL
  • Mr Weyland Dennis, IDSIA
  • Mr Widmer Marino, Université de Fribourg - DIUF
  • Mr Zenklusen Rico, EPFL
  • Mr Zorgati Riadh, EDF
  • Mr Zufferey Nicolas, University of Geneva


Presentations by PhD students will be organized.

Klaus Lorenz, ETH - Institute for Operations Research
Combinatorial Proof for fast Pivoting in K-matrix Linear Complementarity

We use a purely combinatorial argument to show that simple principal pivot methods applied to linear complementarity problems with K-matrices converge very quickly. The proof is conducted in the setting of oriented matroids. Joint work with Jan Foniok and Komei Fukuda.

Lorini Sandro, University of Geneva
Online Vehicle Routing and Scheduling with Dynamic Travel Times

The huge development of communication facilities leads us to consider the vehicle routing and scheduling problem in a real-time fashion, where customer’s requests can be inserted to the currently planned routes as soon as they appear. We propose a heuristic solution method to manage the routes of a given vehicle fleet, while considering dynamic travel times. In such a context, the notion of diversion is a crucial issue.

Pritchard David, EPFL
Algorithms & LPs for k-Edge-Connecting Networks

We study the k-edge-connected spanning subgraph problem in network design, e.g. connecting all vertices in a way that is resilient against k-1 edge failures. Gabow, Goemans, Tardos & Williamson gave an elegant and simple LP-based algorithm for this problem with approximation ratio 1+2/k for unit costs. We show that the case of arbitrary costs behaves differently: for some fixed C > 1, and every k > 1, it is NP-hard to approximate the problem better than C. For the multi-subgraph version -- where edges can be purchased arbitrarily many times -- we conjecture a 1+constant/k approximation based on LPs. The natural LP coincides (up to scaling) with the Held-Karp TSP relaxation, and for this LP we give a new intricate extreme point family with exponentially small values and maximum degree |V|/2.

Slides of David Pritchard
Rumley Sébastien, EPFL - Laboratoire de télécommunications
Interactive Environment for Teaching and Training the Algorithmic Graph Theory

Based on the paradigm “learning by doing” the environment, ATAG (Apprentissage de la théorie algorithmique des graphes) is intended to facilitate the teaching and training of the algorithmic graph theory. ATAG provides a user-friendly interface allowing editing, storing and retrieving of graphs together with the execution of various algorithms written in the script language “groovy”. Thus, ATAG contains several main tools such as: graph editing interface, script launcher, script debugger and command console. By simplifying the editing and handling of graphs, ATAG allows students to focus on the programming and the testing of algorithms. Moreover, the graphical facilities of ATAG are of great help for teaching and illustrating the behavior of various algorithms of the graph theory. The capabilities of ATAG are demonstrated by several relevant examples concerning some classic algorithms.

Uldry Marc, Université de Fribourg - DIUF
A non classical VRP with a non usual objective function

Different kinds of products have to be delivered by silo trucks to several customers. Due to the trucks capacity, each order is split into one or more deliveries, which are supplied from a main depot (the factory) or sometimes from local depots located in railways stations. In order to solve this problem, various simple and complex constraints have to be satisfied. For example, drivers’ capabilities and availability need to be taken into account, trucks can only deliver some customers and can eventually be preloaded the previous day, the journey of each truck starts and ends at the factory, only trucks with filter can be fulfilled in railways stations. To reach the objective imposed by the company, which is to define a vehicle routing such that the number of different trucks supplying each individual customer is minimized, the problem is decomposed into three sub-problems: 1) allocation of customers to a specific depot, 2) allocation of deliveries to trucks, 3) sequencing the deliveries per truck. These sub-problems, modeled and solved with help of mixed integer linear programming, will be presented.

Vacca Ilaria, Transport and Mobility Laboratory, EPFL
The Vehicle Routing Problem with Discrete Split Delivery and Time Windows

The Discrete Split Delivery Vehicle Routing Problem with Time Windows (DSDVRPTW) consists of designing the optimal set of routes to serve, at least cost, a given set of customers while respecting constraints on vehicles’ capacity and customer time windows. The delivery request of a customer consists of several discrete items which cannot be split further. The problem belongs to the class of split delivery problems since each customer’s demand can be split in orders, i.e. feasible combinations of items, and each customer can be visited by more than one vehicle. In this work, we model the DSDVRPTW as a mixed integer linear program, assuming that all feasible orders are known in advance and that each vehicle can serve at most one order per customer. Remarkably, service time at customer’s location depends on the serviced combination of items, which is a modeling feature rarely found in literature. We present a branch-and-price algorithm, analyzing the implications of the classical Dantzig-Wolfe reformulation. Computational results on instances based on Solomon’s data set are discussed.

Energy Management : Probabilistic Models and Conic Approximations

Our concern is to obtain conic approximate tractable solutions of the global cost optimization problem in the electrical industry. Our aim is to take its combinatorial and/or stochastic nature into account. Two applications are investigated. The first is a hydro short term problem with numerous binary and quadratic constraints. It is reformulated using semi-definite programming. The second application is a mid term power system facing uncertainties. For this problem, an approximate conic programming setting is obtained, when using a probability measure on the offer-demand equilibrium at each time step. Solutions of such conic quadratic and semi-definite problems are solved using interior point methods. Typical results obtained with these approaches are reported.