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

InformationTop

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.

LecturersTop

Jean-Bernard Lasserre

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 post-doc visitor at the Electrical Engineering Dept. of the University of California at Berkeley with a fellowship from Inria (1978-79) and NSF (1985-86). Since 1980 he has been at LAAS-CNRS in Toulouse where he is currently "Directeur de Recherche". He is the co-author of the books "Markov Control Processes" and "Further Topics in Markov Control Processes" (Springer-Verlag, 1996 and 1999) and "Markov Chains and Invariant Probabilities" (Birkhauser-Verlag, 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., RAIRO-Operations 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 semi-algebraic 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 so-called "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
Jean-Bernard Lasserre

Dimitris Bertsimas

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 co-authored 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 (1991-1996).

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
Dimitris Bertsimas

Yurii Nesterov

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, polynomial-time interior-point methods, smoothing technique for structural optimization). However, other developments are also well known (SDP-relaxations 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.

Second-order methods with provable global complexity

In this talk we discuss the recent progress in the general second-order 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.

Yurii Nesterov

ScheduleTop

  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

PresentationsTop

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 non-cooperative 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 short-term 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 so-called 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, TRANSP-OR, 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 re-allocate 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, TRANSP-OR, EPFL
Route choice modeling based on network-free 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 network-free data (such as GPS data or partially reported itineraries) with a network based model without such manipulations.

Slides of Emma Frejinger
Leroy-Beaulieu 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 Leroy-Beaulieu
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 pre-existing 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 Real-Radical 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 zero-dimensional semi-algebraic 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 real-algebraic 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 f-vectors 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

RegistrationTop

Sorry, the deadline for registration is over.

Current number of registered participants: 40

  • Abdallah Farah, EPFL
  • Altinakar Sivan, EPFL-ROSE
  • Apparigliato Romain, EDF R&D
  • Bertsimas Dimitris, MIT
  • Bianchi Leonora, Dalle Molle Institute for Artificial Intelligence - IDSIA
  • Bierlaire Michel, TRANSP-OR, EPFL
  • Butcher Mark, LA-EPFL
  • Cruz Javier, TRANSP-OR, EPFL
  • de Werra Dominique, EPFL-ROSE
  • Eggenberg Niklaus, TRANSP-OR, EPFL
  • Ekim Tinaz, ROSE-EPFL
  • Epiney Lucien, EPFL - SMA
  • Frejinger Emma, TRANSP-OR, EPFL
  • Fukuda Komei, EPFL and ETHZ
  • Galdos Gorka, LA-EPFL
  • Haettenschwiler Pius, DIUF / SORS committee
  • Houshang Pour Kamran, EPFL
  • jost vincent, EPFL TRANSP-OR
  • Khatibi Hamid, LA-EPFL
  • Lasserre Jean-Bernard, LAAS-CNRS in Toulouse
  • Léauté Thomas, EPFL - IC - IIF - LIA
  • Leroy-Beaulieu Benjamin, ROSE, EPFL
  • Liebling Thomas, EPFL - ROSO
  • Lourenço Martins Telma, ROSE-EPFL
  • Nesterov Yurii, CORE UCL
  • Osorio Carolina, TRANSP-OR, EPFL
  • Patterson Zachary, TRANSP-OR, EPFL
  • Portabella David, EPFL
  • Prodon Alain, ROSO, EPFL
  • Ries Bernard, ROSE, EPFL
  • Robin Thomas, Transp-or
  • Rostalski Philipp, Automatic Control Lab., ETH Zurich
  • Salani Matteo, TRANSP-OR, EPFL
  • Thénié Julien, Logilab, university of Geneva
  • Vacca Ilaria, TRANSP-OR, EPFL
  • van Delft Christian, Groupe HEC
  • van Heusden Klaske, EPFL-LA
  • Vial Jean-Philippe, Université de Genève
  • Weibel Christophe, ROSO, EPFL
  • Widmer Marino, Université de Fribourg - DIUF