graphs/graph_enac_l.gif
English only
INTER  >  TRANSP-OR > 3ième cycle romand de recherche opérationnelle
Logo TRANSP-OR

Zinal

Partners
Content
Links

InformationTop

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.


LecturersTop

Eva Tardos

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 close-to-optimal 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
Eva Tardos

Berthold Vöcking

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 so-called physical model that takes into account interference by considering the Signal to Interference plus Noise Ratio (SINR).

Download here a copy of the slides

Berthold Voeking

Alain Hertz

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 stock-out 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.

Alain Hertz

Tentative scheduleTop

  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

RegistrationTop

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, TRANSP-OR EPFL
  • Bürgy Reinhard, University of Fribourg - DIUF
  • Chen Jingmin, TRANSP-OR, EPFL
  • Cruz Javier, TRANSP-OR EPFL
  • de Werra Dominique, EPFL
  • Eisenbrand Friedrich, EPFL
  • Emery Sarah, EPFL
  • Fetiarison Mamy, TRANSP-OR 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, TRANSP-OR 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, TRANSP-OR 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, TRANSP-OR, 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, TRANSP-OR, 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

PresentationsTop

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 d-dimensional 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 point-wise using mixed linear integer-rational arithmetic. We will show how the satisfiability problem of such formulas can be reduced to reasoning in a logic that involves mixed-integer 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, TRANSP-OR, 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 multi-depot 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 Quay-Crane 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 quay-crane 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
Sampling-based 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 Monte-Carlo-Sampling approach.