
The 2007 Spring Seminar of the "3ème cycle romand de Recherche
Opérationnelle" will take place from Sunday March 4 to Thursday March 8 at
hôtel de l'Europe, in
Zinal, VS (directions).
Organization: Michel
Bierlaire
Registration deadline: January 31,
2007.
Today is March 15, 2007.
Sorry, the deadline for registration is over.

Dr. J.B. Lasserre graduated from "Ecole Nationale
Superieure d'Informatique et Mathematiques Appliquees"
(ENSIMAG) in Grenoble, France (1976). He then got his PhD
(1978) and "Doctorat d'Etat" (1984) degrees both from Paul
Sabatier University in Toulouse (France). He was a postdoc
visitor at the Electrical Engineering Dept. of the University
of California at Berkeley with a fellowship from Inria
(197879) and NSF (198586). Since 1980 he has been at
LAASCNRS in Toulouse where he is currently "Directeur de
Recherche". He is the coauthor of the books "Markov Control
Processes" and "Further Topics in Markov Control Processes"
(SpringerVerlag, 1996 and 1999) and "Markov Chains and
Invariant Probabilities" (BirkhauserVerlag, 2003). He is (or
has been) Associate Editor of the journals Automatica, Elect.
J. Math. Phys. Sci., IEEE Trans. Aut. Contr., Int. J. Prod.
Res., SIAM J. Contr. Optim., SIAM J. Optim., RAIROOperations
Research, Investigacion Operativa. His research interests
include Production Planning and Scheduling, Markov control
processes, Markov chains, Probability, global and discrete
optimization, and particularly, the links between
optimization, algebra and real algebraic geometry. 
Moments, sums of squares and semidefinite
programming
In this short course we briefly:
 review relatively recent results of real algebraic
geometry on the representation of polynomials, positive on a
compact semialgebraic set, and particularly, sums of
squares types of representations due to Schmudgen, Putinar
and Jacobi and Prestel.
 review their counterpart results in the dual theory of
moments.
 introduce the socalled "generalized problem of moments"
(GPM) and show how several important applications can be
seen as instances of the GPM. Examples of such applications
are found in many areas including algebra for solving
polynomial equations, global optimization, probability,
optimal control, and Mathematical finance (option pricing).
 present a relatively recent methodology to solve (or
approximate) the GPM. It consists of solving a sequence of
semidefinite programming (SDP) relaxations of the original
problem. As the size of these SDP relaxations increases, the
sequence of values converges to the desired value, and
sometimes in finitely many steps.
 investigate some algorithmic issues and propose
strategies for handling large scale problems with structured
sparsity.

Download
here a copy of the slides  


Dimitris Bertsimas is currently the codirector of the
Operations Research Center and the Boeing Professor of
Operations Research at the Sloan School of Management at the
Massachusetts Institute of Technology. He has received a BS in
Electrical Engineering and Computer Science at the National
Technical University of Athens, Greece in 1985, a MS in
Operations Research at MIT in 1987, and a Ph.D in Applied
Mathematics and Operations Research at MIT in 1988. Since
1988, he has been with MIT's Sloan School of Management.
His research interests include optimization, stochastic
systems, data mining and their application. He has published
widely and he is former area editor in Operations Research. He
has coauthored the following books: ``Introduction to Linear
Optimization'' (with J. Tsitsiklis, Athena Scientific, 1997),
``Data, models and decisions'' (with R. Freund, Dynamic Ideas,
2004) and ``Optimization over Integers'' (with R. Weismantel,
Dynamic Ideas, 2005).
He is a member of the United States National Academy of
Engineering, and he has received numerous research awards
including the Erlang prize (1996), the SIAM prize in
optimization (1996), the Bodossaki prize (1998) and the
Presidential Young Investigator award (19911996). 
Robust and adaptive optimization: A tractable
approach to optimization under uncertainty
For almost all its history, the predominant model in
Operations Research to describe uncertainty is probability
theory. Optimization under uncertainty, however, when the
primitive elements are probability distributions suffers from
the curse of dimensionality, and thus it does not have a
tractable theory.
In this short course, we show that when the primitive
elements to describe uncertainty are polyhedral or conic
uncertainty sets, the central models of optimization (linear,
mixed integer, conic) under uncertainty, models known as
robust optimization, can be reformulated as optimization
problems of the same structure and a mild increase in the
dimension, and thus are tractably solvable both practically
and theoretically. We also show how to construct uncertainty
sets from data and risk preferences.
We further describe adaptive optimization, a tractable
theory for optimization under uncertainty with recourse when
uncertainty is described via uncertainty sets.
We finally present applications of these methods to:
optimal control, inventory theory and multiperiod asset
allocation. 
Download
here a copy of the slides  


Yurii Nesterov is a professor of Center for Operations
Research and Econometrics (CORE) at Catholic University of
Louvain (UCL), Belgium. He has received master degree in 1977
at Moscow State University, and Ph.D. degree (Applied
Mathematics) in 1984 at Institute of Control Sciences, Moscow.
Since 1977 he worked at Central Economical and Mathematical
Institute, Acad. Sci. USSR. Starting from 1993 he works at
CORE.
His research interests are related to complexity issues and
efficient methods for solving various optimization problems.
The main results are obtained in Convex Optimization (optimal
methods for smooth problems, polynomialtime interiorpoint
methods, smoothing technique for structural optimization).
However, other developments are also well known
(SDPrelaxations for Boolean problems, representation of sums
of squares, cubic regularization of Newton method). He is an
author of 4 monographs and more than 70 refereed papers in the
leading optimization journals. In 2000, he won the triennial
Dantzig Prize awarded by SIAM and Mathematical Programming
Society for a research having a major impact on the field of
mathematical programming. 
Secondorder methods with provable global
complexity
In this talk we discuss the recent progress in the general
secondorder minimization schemes related to the cubic
regularization of the Newton's method. For convex case, we
present an accelerated multistep version of the method. We
consider the extensions of the new schemes onto constrained
problems. Preliminary computational results are also
discussed.  


Sunday 4 
Monday 5 
Tuesday 6 
Wednesday 7 
Thursday 8 
08h30  09h00 

Bertsimas 
Lasserre 
Bertsimas 
Lasserre 
09h00  09h30 
09h30  10h00 
10h00  10h30 
break 
break 
break 
break 
10h30  11h00 
Lasserre 
Bertsimas 
Lasserre 
Bertsimas 
11h00  11h30 
11h30  12h00 
12h00  17h00 
Sport and discussions 

17h00  17h30 
Nesterov 
PhD student 
PhD student 
17h30  18h00 
PhD student 
PhD student 
18h00  18h30 
Welcome cocktail 
PhD student 
PhD student 
18h30  19h00 


Presentations by PhD students will be organized. Please use the
following form to submit an abstract.
 Altinakar Sivan, EPFL  ROSE
 Cellular Operators in a Shared Spectrum
Due to the increasing number of radio technologies, the available
frequency spectrum becomes more and more utilized, hence its clever use
becomes a critical issue. Among many proposed solutions, the formulation
of the problem as the control of the power of the base stations, also
known as the Power Control problem, seems a promising idea. In the
present work, we propose to study this problem by rst den ing a
theoretical model. Then, we design a family of noncooperative games
that hopefully stop at a Nash equilibria close to the optimal so lution
for the network, as well as a few simple tabu search heuristics. We
nally developed a java library and a program, in order to experi
mentally study the behavior of the proposed games and heuristics.
 Slides
of Sivan Altinakar
 Apparigliato Romain, EDF R&D
 Weekly management of a hydraulic valley by robust
optimization
Optimization models for shortterm electricity production planning in
linked hydraulic system often leads to infeasible controls due to random
fluctuations of the water inflow. To immunize the solution against
uncertainty, we propose a robust optimization approach. Two kinds of
application of this method are tested and compared with a deterministic
with daily revisions approach: a robust approach with daily revisions
and a robust one wich uses linear decision rules. This formulation leads
to a linear programming problem, the socalled affinely adjustable
robust counterpart (AARC). We generate the weekly schedule for a small
but critical hydraulic system. Results show that it is possible to
achieve good cost performance while keeping the constraint violation to
almost nil.
 Slides of
Romain Apparigliato
 Eggenberg Niklaus, TRANSPOR, EPFL
 A Recovery Algorithm for a Disrupted Airline
Schedule
The airline scheduling is a very large and complex problem. Moreover,
it is common that only a minority of the initial schedules are carried
out as planned because of delays, airport closures or other unforeseen
events. Thus, given an actual state of the resources, a so called
"disruption" arises when a schedule becomes unrealizable. The problem
the scheduler is then faced with is to reallocate the resources in
order to get back to the initial schedule and to define what the
priorities are: minimize the recovery time or minimize a given cost
function. In this presentation, we will describe briefly a network model
and a recovery algorithm based on column generation that solves the
minimal cost recovery problem for a given maximal recovery time. We will
focus the attention on the recovery network used at the pricing problem
level. In particular we will describe some ideas that are useful to
speed up the whole algorithm.
 Slides
of Niklaus Eggenberg
 Frejinger Emma, TRANSPOR, EPFL
 Route choice modeling based on networkfree data
Route choice models play a crucial role in many transport
applications, for example traffic assignment and transport planning.
They are difficult to design and to estimate for various reasons, such
as the large size of the choice set and the complex correlation
structure. The concept of path, which is at the core of a route choice
model, is usually too complex for a reliable data collection process. In
general, it is therefore necessary to perform an extensive amount of
data processing in order to obtain coherent routes. We argue that the
data manipulation required by the underlying network model introduces
biases and errors, and should be avoided. We propose a general modeling
scheme that reconcile networkfree data (such as GPS data or partially
reported itineraries) with a network based model without such
manipulations.
 Slides
of Emma Frejinger
 LeroyBeaulieu Benjamin, EPFL  ROSE
 On the track assignment problem (bounded coloring)
We consider a depot consisting of a set of parallel tracks. Each
track can be approached from one side only and the number of trains per
track is limited. The departure times of the trains are fixed according
to a given time table. The problem is to assign a track to each train as
soon as it arrives to the depot and such that it can leave the depot on
time without being blocked by any other train. We show how to solve this
problem as an online bounded coloring problem on special graph classes.
We give the competitive ratio of this problem on those classes.
 Slides of
Benjamin LeroyBeaulieu
 Osorio Carolina, EPFL
 Analysis of finite capacity queuing networks
Queueing network models have been widely applied as tools allowing
the estimation of performance measures and the behavioural description
of systems such as communication, production and software architecture
networks. Queueing network models with finite capacity queues, where
blocking may arise, allow a more realistic description of the system
under study. In this talk we will present an approximation method
developed to analyze open finite capacity queueing networks with
blocking after service. The method decomposes the network into single
queues that are analysed using revised arrival and service rates. Unlike
preexisting methods it preserves both the network topology and its
configuration (number of queues and their capacity). It also explicitly
models the blocking phase. Its comparison with other methods will be
presented. Preliminary results concerning its application on a large
scale case study will also be discussed.
 Slides of
Carolina Osorio
 Rostalski Philipp, Automatic Control Lab., ETH Zurich
 Characterization and Computation of RealRadical Ideals
using Semidefinite Programming Techniques
In this talk I will discuss a method (joined work with M. Laurent and
J.B. Lasserre) for computing all real points on a zerodimensional
semialgebraic set described by polynomial equalities and inequalities
as well as some "nice" polynomial generators for the corresponding
vanishing ideal, namely border resp. Gröbner basis for the real radical
ideal. In contrast to exact computational algebraic methods, the method
we propose uses numerical linear algebra and semidefinite optimization
techniques to compute approximate solutions and generator polynomials.
The method is realalgebraic in nature and prevents the computation of
any complex solution. The proposed methods fits well in a relatively new
branch of mathematics called "Numerical Polynomial Algebra".
 Slides
of Philipp Rostalski
 Weibel Christophe, EPFL  ROSO
 A theorem about Minkowski sums of polytopes
The complexity and combinatorial aspects of Minkowski sums are not
yet well understood. This presentation introduces a new theorem on a
linear relation between the fvectors of polytopes in general position
and their Minkowski sum. This relation allowed us to find the maximum
number of facets in a Minkowski sum in terms of its summands.
 Slides of
Christophe Weibel
Sorry, the deadline for registration is over.
Current number of registered participants: 40
 Abdallah Farah, EPFL
 Altinakar Sivan, EPFLROSE
 Apparigliato Romain, EDF R&D
 Bertsimas Dimitris, MIT
 Bianchi Leonora, Dalle Molle Institute for Artificial Intelligence 
IDSIA
 Bierlaire Michel, TRANSPOR, EPFL
 Butcher Mark, LAEPFL
 Cruz Javier, TRANSPOR, EPFL
 de Werra Dominique, EPFLROSE
 Eggenberg Niklaus, TRANSPOR, EPFL
 Ekim Tinaz, ROSEEPFL
 Epiney Lucien, EPFL  SMA
 Frejinger Emma, TRANSPOR, EPFL
 Fukuda Komei, EPFL and ETHZ
 Galdos Gorka, LAEPFL
 Haettenschwiler Pius, DIUF / SORS committee
 Houshang Pour Kamran, EPFL
 jost vincent, EPFL TRANSPOR
 Khatibi Hamid, LAEPFL
 Lasserre JeanBernard, LAASCNRS in Toulouse
 Léauté Thomas, EPFL  IC  IIF  LIA
 LeroyBeaulieu Benjamin, ROSE, EPFL
 Liebling Thomas, EPFL  ROSO
 Lourenço Martins Telma, ROSEEPFL
 Nesterov Yurii, CORE UCL
 Osorio Carolina, TRANSPOR, EPFL
 Patterson Zachary, TRANSPOR, EPFL
 Portabella David, EPFL
 Prodon Alain, ROSO, EPFL
 Ries Bernard, ROSE, EPFL
 Robin Thomas, Transpor
 Rostalski Philipp, Automatic Control Lab., ETH Zurich
 Salani Matteo, TRANSPOR, EPFL
 Thénié Julien, Logilab, university of Geneva
 Vacca Ilaria, TRANSPOR, EPFL
 van Delft Christian, Groupe HEC
 van Heusden Klaske, EPFLLA
 Vial JeanPhilippe, Université de Genève
 Weibel Christophe, ROSO, EPFL
 Widmer Marino, Université de Fribourg  DIUF
