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

David SimchiLevi is professor at the Department of Civil and Environmental Engineering and the Engineering Systems Division, Massachusetts Institute of Technology. His research interests include the development and implementation of robust and efficient techniques for manufacturing and logistics systems. In particular, areas such as supply chain, network design, inventory models, pricing and procurement strategies, as well as production scheduling.

Stochastic and Deterministic Problems in Supply Chain Management
Operations Research models and techniques developed for a variety of problems arising in logistical planning of multiechelon systems. Focus on planning models for production/inventory/distribution strategies in general multiechelon multiitem systems. Topics include stochastic and deterministic multiechelon inventory systems, the bullwhip effect, inventorypricing models, and integration problems arising in supply chain management. Applications to marketmaking in finance are also discussed.

Download here a copy of the slides

Download here relevant papers




Gábor Tardos is a Canada Research Chair at the School of Computing Science of Simon Fraser University, and a Senior Research Fellow at the Alfréd Rényi Institute of Mathematics at Hungarian Academy of Sciences.
His research interests include combinatorics, discrete and computational geometry, and complexity theory.

Satisfiability of small occurrence and random SAT instances
Satisfiability of CNF formulas (SAT) was subject of intense study ever
since Cook proved it was complete for NP. We will employ elementary
probabilistic theoretic and combinatorial techniques (including Lovasz
local lemma, second moment method and binary trees) to investigate a
kind of phase transition of these formulas in two settings. First
assume that all clauses of the formula has k distinct literal (a
kCNF) and all variables appear at most some l times. For what values
of k and l are these formulas always satisfiable. Second, consider a
random kCNF with n variables and rn clauses. What is the probability
that it is satisfiable?

Download here a copy of the slides



Robert Weismantel

Robert Weismantel is Professor at ETHZ. His research addresses
questions in the area of discrete mathematics and optimization. He is
particularly interested in topics from integer programming,
algorithmic discrete mathematics, and mixed integer and nonlinear
optimization. The second focus is on mathematics for studying
questions in cell biology, systems biology, chemical engineering, and
control theory.

Nonlinear Discrete Optimization and Nfold systems
This talk deals with the problem of optimizing nonlinear
functions over the lattice points in a polyhedral set.
We present families of polynomial time algorithms for special
cases of the general problem. Each such algorithm makes use of combinatorial, algebraic or geometric properties of the underlying problem.
A particular focus of the talk concerns convex nfold integer minimization
problems that we explain how to solve in polynomial time.





Sunday 16

Monday 17

Tuesday 18

Wednesday 19

Thursday 20

08h30  09h00


Tardos

SimchiLevi

SimchiLevi

Tardos

09h00  09h30

09h30  10h00

10h00  10h30

break

break

break

break

10h30  11h00

Tardos

Tardos

SimchiLevi

SimchiLevi

11h00  11h30

11h30  12h00

12h00  17h00

Sport and discussions


17h00  17h30

Weismantel

Atasoy

Bock

17h30  18h00

Boyacy 
Buergisser 
18h00  18h30

Welcome cocktail

Fuchsberger 
Uldry 
18h30  19h00

Niemeier 
Wagner 
Sorry, the deadline for registration is over. Current number of registered participants: 49
 Mrs Atasoy Bilge, Transport and Mobility Laboratory, EPFL
 Mr Baumann Philipp, University of Bern
 Mr Bierlaire Michel, Transport and Mobility Laboratory, EPFL
 Mr Billotte Denis, CUSO
 Mr Bock Adrian, DISOPT, EPFL
 Mr Bonifas Nicolas, DISOPT, EPFL
 Mr Boyacı Burak, Mr
 Mr Brandinu Gianluca, University of Bern
 Mr Bürgisser Michael, ETHZ
 Mr Bürgy Reinhard, University of Fribourg  DIUF
 Mr Chen Jingmin, EPFL
 Mr Di Summa Marco, DISOPT, EPFL
 Mr Farooq Bilal, Transport and Mobility Laboratory, EPFL
 Mr Fetiarison Mamy, Transport and Mobility Laboratory, EPFL
 Mr Frati Fabrizio, EPFL
 Mr Fuchsberger Martin, IFOR, ETHZ
 Mr Fulek Radoslav, EPFL
 Ms Glerum Aurélie, Transport and Mobility Laboratory, EPFL
 Mr Hurtubia Ricardo, Transport and Mobility Laboratory, EPFL
 Mr Lade Nicholas, EPFL
 Mr Morić Filip, EPFL
 Mr Mustafa Nabil, EPFL
 Mr Niemeier Martin, DISOPT, EPFL
 Mr Nonner Tim, IBM Research  Zurich
 Mr Pach Janos, EPFL
 Mr Piu Francesco, Transport and Mobility Laboratory TRANSPOR
 Mr Pritchard David, EPFL DISOPT
 Mr Ray Saurabh, EPFL
 Mr Respen Jean, University of Geneva
 Ms Sanità Laura, DISOPT, EPFL
 Mr SimchiLevi David, Massachusetts Institute of Technology
 Mr Spielmann Andrej, EPFL
 Mr Taillard Éric, HEIGVd HESSO
 Mr Tardos Gabor, Hungarian Academy of Sciences
 Mr Thevenin Simon, University of Geneva
 Mr Trautmann Norbert, Department of Business Administration, University of Bern
 Mr Uldry Marc, University of Fribourg  DIUF
 Mr Umang Nitish, EPFL
 Ms Vacca Ilaria, Transport and Mobility Laboratory, EPFL
 Mr Van Delft Christian, HEC Paris
 Mr Vial JeanPhilippe, Université de Genève
 Mr VISWANATHAN PREM KUMAR, EPFL
 Mr Wagner Christian, ETHZ
 Mr Weismantel Robert, ETH Zürich
 Mr Weyland Dennis, IDSIA
 Mr Widmer Marino, University of Fribourg  DIUF
 Mr Wörner Stefan, IBM Research  Zurich
 Mr ZORGATI Riadh, EDF R&D
 Mr Zufferey Nicolas, University of Geneva
Presentations by PhD students will be organized.
Current number of submitted abstracts: 10
 Atasoy Bilge, TRANSPOR, EPFL
 Integrated schedule planning with demand considerations
In the context of airline scheduling, integrated schedule design and fleet assignment model is studied in the literature with the purpose of increasing the revenue by determining the schedule simultaneously with fleet assignment. In this study we further integrate the demand modeling into the optimization problem where the spill effects are taken into account. Therefore the joint decision of pricing, fleet assignment and schedule design determines the actual number of passengers flying on each itinerary with the objective of maximizing the difference between revenue and operating costs. The demand modeling is done with linear, exponential, and piecewise linear functions where the explanatory variable is the fare of the itinerary.  Bock Adrian, DISOPT, EPFL
 The school bus routing problem (SBRP)
The SBRP is a variant of the wellstudied Vehicle Routing problem. Its objective is to minimize the number of vehicles used to carry a given set of children to school. The bus routes respect a uniform vehicle capacity and a bound on the maximum difference between the travel time of a child on the bus and a direct transport to school. Due to its inherited NPhardness, we look for an approximate solution in theory and practice. A constant factor approximation algorithm on trees is presented. In practice, the SBRP can be solved using a column generation approach. We will report results on a reallife instance.  Boyacý Burak, LUTS, EPFL
 Computing Bounds for the Capacitated Multifacility Weber Problem by Branch and Price and Lagrangean Relaxation
The Capacitated Multifacility Weber Problem is concerned with locating m facilities in the plane, and allocating their capacities to n customers at minimum total cost, which is a nonconvex optimization problem and difficult to solve. In this work we relax the capacity constraints and solve the uncapacitated Lagrangean subproblems every step of a subgradient algorithm. Their objectives have facility dependent distance functions, which is different than the usual multifacility Weber problem. We solve them by branchandprice using column generation with concave minimization pricing.  Bürgisser Michael, ETHZ
 Hedge Algorithm and Subgradient Methods
We show that the Hedge Algorithm, a method that is widely used in Machine Learning, can be interpreted as a particular subgradient algorithm for minimizing a wellchosen convex function, namely as a Mirror Descent Scheme. Using this reformulation, we establish three modifications and extensions of the Hedge Algorithm that are better or at least as good as the standard method with respect to worstcase guarantees. Numerical experiments show that the modified and extended methods that we suggest perform consistently better than the standard Hedge Algorithm.  Fuchsberger Martin, IFOR, ETHZ
 Algorithms for adaptive train control in main stations
A dispatching support system for the station area of Berne, Switzerland is presented. The model assigns to each train a path based on a variety of alternative track routes, station platforms, speed profiles and arrival or departure times. While respecting safety regulations based on detailed blocking time theory, the optimal assignment is minimizing a weighted combination of delay propagation and number of broken connections. The model is iteratively adapted to the current state situation and solved in a rolling time horizon framework to cope with the continuously changing online situation.  Niemeier Martin, DISOPT  EPFL
 Covering Cubes and the Closest Vector Problem
The closest lattice vector problem is one of the central computational problems in the geometry of numbers. Here one is given a rational lattice, i.e. set set of integer combinations of a basis A of the vector space Q^n and a vector t of Q^n. The task is to compute a vector of the lattice that is closest to t w.r.t. a given norm. We will present the currently fastest known randomized (1+eps)approximation algorithm
for the closest vector problem in infinity norm.
It is based on the following geometric problem: Cover the cube [1+eps,1eps]^n
with parallelepipeds such that each parallelepiped, if scaled by 2, is contained in the cube [1,1]^n. We present a covering scheme that allows to boost any constant factor approximation algorithm for the closest vector problem to a (1+eps) approximation algorithm, with a logarithmic dependence on 1/eps.
This yields a (1+eps) approximation algorithm with a running time of 2^(O(n))(log 1/eps)^(O(n)), improving on the previously fastest algorithm by Bloemer and Naewe with a running time of (2+1/eps)^(O(n)).  Uldry Marc, University of Fribourg  DIUF
 Solving a special split delivery vehicle routing problem in one phase
We consider a delivery problem with a heterogeneous fleet of vehicles and several depots. The demands of the customers are typically larger than the capacity of the vehicles which means that most customers are visited several times. This is a split delivery vehicle routing problem with additional constraints, which can be modeled as an integer linear programming problem, that simultaneously assigns deliveries to the vehicles and builds vehicle routes. Experiments on real life instances are presented.  Viswanathan Prem Kumar, EPFL
 Determining Optimal Facings on a Retail Shelf
Managing shelf space is critical for retailers to attract customers and to optimize profit. The decisions relating to the products to be stocked among a large number of competing products and the amount of shelf space to allocate to those products is a question central to retailing. Consumer behaviour studies show that more a product is displayed on the shelf, more could be its sale. However the amount of space on the shelf is limited and a retailer also needs to stock competing products even if one of the products is a leader in terms of volume sales. This problem is complicated by the fact that the relationship between volume sales of the product and its number of facings is not linear.  Wagner Christian, ETHZ
 Maximal latticefree rational polyhedra: a proof of finiteness
A convex set with nonempty interior is maximal latticefree if it is inclusionmaximal with respect to the property of not containing integer points in its interior. Maximal latticefree convex sets are known to be polyhedra.
Recently, it has been shown that, up to affine mappings preserving the integer lattice, the number of maximal latticefree rational polyhedra of a given precision is finite. In this talk, I will explain the key steps of the proof and the underlying geometry.  ZORGATI Riadh, EDF R&D OSIRIS
 Using Second Order Conic Programming and SemiDefinite Programming to solve Stochastic Nuclear Outages Problem
Scheduling nuclear plants outages for refuelling and maintenance is a challenging optimization problem with a stochastic demand to satisfy by using different production units affected by random failure process. The present work deals with a very simplified model of this problem leading to a huge combinatorial problem with uncertain data. Using a probabilistic approach and conic approximations, we deal with a mixed integer second order conic program. We will present different conic approaches for its resolution.
