Information

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 December 21, 2024.

Sorry, the deadline for registration is over.

Lecturers

David Simchi-Levi
David Simchi-Levi 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 multi-echelon systems. Focus on planning models for production/inventory/distribution strategies in general multi-echelon multi-item systems. Topics include stochastic and deterministic multi-echelon inventory systems, the bullwhip effect, inventory-pricing models, and integration problems arising in supply chain management. Applications to market-making in finance are also discussed. Download here a copy of the slides Download here relevant papers
Gábor Tardos
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 k-CNF) 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 k-CNF 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 N-fold 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 n-fold integer minimization problems that we explain how to solve in polynomial time.

Tentative schedule

Registration

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 TRANSP-OR
• Mr Pritchard David, EPFL DISOPT
• Mr Ray Saurabh, EPFL
• Mr Respen Jean, University of Geneva
• Ms Sanità Laura, DISOPT, EPFL
• Mr Simchi-Levi David, Massachusetts Institute of Technology
• Mr Spielmann Andrej, EPFL
• Mr Taillard Éric, HEIG-Vd HES-SO
• 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 Jean-Philippe, 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

Presentations by PhD students will be organized.

Current number of submitted abstracts: 10

Atasoy Bilge, TRANSP-OR, 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 well-studied 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 NP-hardness, 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 real-life instance.

Boyacý Burak, LUTS, EPFL

Computing Bounds for the Capacitated Multifacility Weber Problem by Branch and Price and Lagrangean Relaxation

The Capacitated Multi-facility 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 non-convex 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 branch-and-price 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 well-chosen 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 worst-case 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,1-eps]^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 lattice-free rational polyhedra: a proof of finiteness

A convex set with non-empty interior is maximal lattice-free if it is inclusion-maximal with respect to the property of not containing integer points in its interior. Maximal lattice-free 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 lattice-free 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 Semi-Definite 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.