
The 2009 Spring Seminar of the "3ème cycle romand de Recherche
Opérationnelle" will take place from Sunday January 18 to Thursday January 22 at hôtel de l'Europe, in
Zinal, VS (directions).
Organization: Michel Bierlaire
Registration deadline: November 30, 2008. Today is February 11, 2009. Sorry, the deadline for registration is over.

Eva Tardos is professor in the Department of Computer
Science, Cornell University. Her main research interest is algorithm
design and algorithmic game theory. Algorithmic game theory, an
emerging new area of designing systems and algorithms for selfish
users. Her research focuses on algorithms and games on graphs or
networks. She is mostly interested in designing algorithms and games
that provide provably closetooptimal results.

Games in Networks: the price of anarchy, stability, and learning.
Network games play a fundamental role in understanding behavior in many
domains, ranging from communication networks through markets to social
networks. Such networks are used, and also evolve due to selfish
hevaiour of the users and owners. In light of these competing forces,
it is surprising how efficient these networks are. It is an exciting
challenge to understand the operation and success of these networks in
game theoretic terms: what principles of interaction lead selfish
participants to form such efficient networks?
We will survey results on a couple simple games, and study the
degradation of quality of solution caused by the selfish behavior of
users. We compare the selfish outcome to a centrally designed optimum
both in terms of the quality of Nash equilibria and also the quality of
outcomes of learning behavior by the users.

Download here a copy of the slides




Berthold Vöcking is Professor for Algorithms and Complexity, Department of Computer Science
RWTH Aachen University.
His main research interests lie in theoretical computer science,
mostly in algorithms and networks. Topics of interest include
randomized algorithms, probabilistic analysis of algorithms, algorithms
for communication networks, and algorithmic game theory.

Coordination in Networks: Algorithms and Games
Part 1: Congestion Games
Congestion games model the allocation of resources by selfish players.
For example, the
players aims at allocating a shortest path in a network. The cost
(delay) of a resource (edge) is
a function of the congestion, i.e., the number of players allocating the
resource. We survey results
about the existence and complexity of Nash equilibria in different
variants of congestion games.
Towards this end, we draw a connection to the complexity of local search
and elaborate on
the complexity class PLS (Polynomial Local Search).
Part 2: Scheduling in Wireless Networks
Signals sent by different sources in multipoint radio networks need to
be coordinated in
order to avoid collisions. The Media Access Control (MAC) layer is
responsible for
this important task. We discuss algorithms for the scheduling problems
arising on the
MAC layer. Our theoretical analysis is based on the socalled physical
model that
takes into account interference by considering the Signal to
Interference plus Noise
Ratio (SINR).
Download here a copy of the slides





Alain Hertz is Professor at the Department of Mathematics and
Industrial engineering at Ecole Polytechnique, Montreal. He is also
member of the GERAD (Group for Research in Decision Analysis)
His main research interests lie in graph theory, combinatorial
optimization, and all algorithmic aspects related to these two research
areas. He is particularly interested in developing mathematical models
and efficient algorithms for the solution of scheduling problems in
logistics, workforce and production planning.

Solution methods for the inventory routing problem
We consider an inventory routing problem in discrete time where a
supplier has to serve a set of customers over a time horizon. At each
discrete time, a fixed quantity is produced at the supplier and a fixed
quantity is consumed at each customer. A capacity constraint for the
inventory is given for the supplier and each customer, and the service
cannot cause any stockout situation. Two different replenishment
policies are considered: when a customer is served, one can either
deliver any quantity that does not violate the capacity constraint, or
impose that the inventory level at the customer should reach its
maximal value. The transportation cost is proportional to the distance
traveled, whereas the inventory holding cost is proportional to the
level of the inventory at the customers and at the supplier. The
objective is the minimization of the sum of the inventory and
transportation costs. We describe exact and heuristic algorithms for
the solution of this complex problem.





Sunday 18

Monday 19

Tuesday 20

Wednesday 21

Thursday 22

08h30  09h00


Vöcking

Tardos

Vöcking

Tardos

09h00  09h30

09h30  10h00

10h00  10h30

break

break

break

break

10h30  11h00

Tardos

Vöcking

Tardos

Vöcking

11h00  11h30

11h30  12h00

12h00  17h00

Sport and discussions


17h00  17h30

Hertz

Robin

Svensson

17h30  18h00

Hähnle 
Weyland 
18h00  18h30

Welcome cocktail

Uldry 
Vacca 
18h30  19h00

Piskac 
Rumley 
Sorry, the deadline for registration is over. Current number of registered participants: 48
 Adjiashvili David, ETH Zurich, IFOR
 Alp Arda, Université de Neuchâtel (UNINE), Faculty of Economics, Institut de l'entreprise (IENE)
 Bierlaire Michel, TRANSPOR EPFL
 Bürgy Reinhard, University of Fribourg  DIUF
 Chen Jingmin, TRANSPOR, EPFL
 Cruz Javier, TRANSPOR EPFL
 de Werra Dominique, EPFL
 Eisenbrand Friedrich, EPFL
 Emery Sarah, EPFL
 Fetiarison Mamy, TRANSPOR EPFL
 Fichtinger Johannes, Université de Neuchâtel
 Flötteröd Gunnar, EPFL
 Foniok Jan, ETH Zürich
 Fukuda Komei, ETHZ
 Fulek Radoslav, EPFL
 Gläßer Dominik, Université de Neuchâtel
 Hassani Seyed Hamed , EPFL
 Hähnle Nicolai, EPFL
 Hättenschwiler Pius, University of Fribourg, DIUF
 Hertz Alain, Ecole Polytechnique Montréal
 Hurtubia Ricardo, TRANSPOR EPFL
 Hürlimann Tony, University of Fribourg
 Karrenbauer Andreas, DISOPT, EPFL, Lausanne
 Keszegh Balázs, Central European University and Alfréd Rényi Institute of Mathematics, Budapest
 Liebling Thomas, EPFL
 Newman Jeffrey, TRANSPOR EPFL
 Niemeier Martin, EPFL
 Palvolgyi Domotor, EPFL
 Petrov Tatjana, EPFL, Models and Theory of Computation
 Piskac Ruzica, LARA, EPFL
 Rabta Boualem, Université de Neuchâtel (UNINE), Faculty of Economics, Institut de l'entreprise (IENE)
 Reiner Gerald, Université de Neuchâtel
 Robin Thomas, TRANSPOR, EPFL
 Rosta Vera, Renyi Institute of Mathematics
 Rothvoss Thomas, DISOPT, EPFL
 Rumley Sébastien, EPFL  TCOM
 Schupbach Kaspar, ETH Zurich, IFOR
 Shmonin Gennady, EPFL
 Svensson Ola, IDSIA
 Tardos Eva, Cornell University
 Trautmann Norbert, University of Bern
 Uldry Marc, Université de Fribourg  DIUF
 Vacca Ilaria, TRANSPOR, EPFL
 van Delft Christian, Groupe HEC
 Venter Gyorgy, London School of Economics
 Vöcking Berthold, Aachen University
 Weyland Dennis, Dalle Molle Institute for Artificial Intelligence (IDSIA)
 Widmer Marino, Université de Fribourg  DIUF
Presentations by PhD students will be organized.
Current number of submitted abstracts: 8
 Hähnle Nicolai, EPFL DISOPT
 Combinatorial abstractions for the diameter of polyhedra
Given
a ddimensional polyhedron with n facets, what upper bounds can we give
for the diameter of its graph?
The presentation deals with combinatorial abstractions that have been
used in studying this question. We review previous abstractions and
introduce a generalization in which we can construct a family of
instances with superlinear diameter, thus showing limitations in the
techniques used to show the upper bounds on the diameter that are due
to Kalai & Kleitman and Larman.  Piskac Ruzica, LARA, EPFL
 Applying OR Results in Software Verification
We
investigate decision procedures for logical formulas involving
collections such as sets, multisets, and fuzzy sets, together with
cardinality constraints. Formulas that are expressible in this logic
naturally occur in many software verification problems. Our logic
supports standard operators such as union, intersection, difference, or
any operation defined pointwise
using mixed linear integerrational arithmetic.
We will show how the satisfiability problem of such formulas can be
reduced to reasoning in a logic that involves mixedinteger linear
arithmetic formulas enriched with a so called "star" operator. We will
also show how to obtain the optimal complexity for the satisfiability
problem by applying the theorem about Caratheodory bounds for integer
cones.
 Robin Thomas, TRANSPOR, EPFL
 Behavioural modeling of dynamic facial expression recognition
Dynamic
facial expression recognition is an emerging field potentially used in
many transportation applications. For example, it can be useful to
quantify the tiredness of drivers and determine their ability to drive
or not. We propose a new dynamic facial expression recognition
framework inspired on discrete choice theory and cooperative highways
lane changing models. The aim of the work is to model a person who has
to decide a face expression on a video sequence.  Rumley Sébastien, EPFL
 Optimisation in optical communication networks
Optical telecommunication networks, as communication networks, and in a
larger extend, as other transportation networks, are subject to various
classical optimisation problems: congestion minimisation, total throughput
maximisation, routing cost minimisation, etc. However they present specific
constraints which cause many of the methods valid for other networks to be
partly or totally ineffective. Moreover, additional specific optimisations
can be achieved in optical networks, as regeneration nodes minimization.
This presentation details the constraints and presents several optimisation
problems present in optical communications.  Svensson Ola, IDSIA
 On the hardness of approximating flow shops
We show that the current best approximation algorithm for the classical flow shop scheduling problem
is tight with respect to the used lower bound on the optimal makespan. Moreover, we show that it is hard
to improve the approximation guarantee for the general version of flow shops, where jobs are allowed to skip machines.
 Uldry Marc, Université de Fribourg  DIUF
 Cement deliveries in a multidepot problem
Different
kind of cement have to be delivered by trucks to several customers.
These deliveries are done either from a main depot (the factory) or
from local depots located in railways stations. Various simple or
complex constraints should be satisfied while solving this problem. For
example, trucks can only deliver some kind of cement and can be driven
by some drivers, drivers availability needs to be taken into account,
the loading and unloading times depend on the location and on the used
truck, the journey of each truck starts and ends at the factory. The
goal is to develop a vehicle routing which minimises the total duration
of the journeys. A simple structured algorithm for solving this problem
will be presented.  Vacca Ilaria, Transport and Mobility Laboratory, EPFL
 Models and Heuristics for the Tactical Berth Allocation Problem with QuayCrane Assignment and Transshipment Costs
In
this work, we focus on the integration of two problems arising in the
management of transshipment container terminals: the problem of
assigning and scheduling incoming ships to berthing positions (berth
allocation problem), and the problem of assigning quay cranes to
incoming ships (quay crane assignment problem). In particular,
motivated by the practice in the negotiation process between the
terminal management and the shipping liner, the model
is based on the concept of quaycrane assignment profile, i.e., the
sequence of the number of
cranes assigned to the ship along each operating work shift. Two mixed
integer formulations
are considered with a quadratic and a linearized objective function,
respectively. Both models
have been validated on instances based on real data. Computation
confirms that the problem
is hardly solvable via exact methods, hence we introduce heuristic
methods for finding good
feasible solutions in a reasonable amount of time and present
computational results obtained
on the same set of instances. Joint work with M. Salani, G.
Giallombardo and L. Moccia.  Weyland Dennis, IDSIA
 Samplingbased approaches for Stochastic Combinatorial Optimization Problems
In
Stochastic Combinatorial Optimization Problems (SCOP) the problem
instances contain some kind of uncertainty. Instead of using concrete
values, some parameters are only given by their probability
distributions. Usually this uncertainty makes a problem harder, but on
the other hand many real world problems can be described in a more
realistic scenario with SCOPs.
In this presentation SCOPs are introduced using the Probabilistic
Traveling Salesman Problem as an example. Then some solution strategies
are compared with focus on a very general MonteCarloSampling approach.
