Winter seminar

Please press Ctrl+F5 to load the most recent version of this page...

This seminar is part of the CUSO Doctoral Programme in Operations Research. For details, please refer to the invitation sent by e-mail.

Dates: January 17-21, 2016
Venue: Hotel Europe, Zinal (VS)

Organization: Norbert Trautmann (University of Bern), Michel Bierlaire (EPFL), Dominique de Werra (EPFL), Nadine Zumsteg (University of Bern)

Keynote speakers:

Bernard Gendron (University of Montreal)

Title: Decomposition for Network Design

This lecture series will focus on network design problems arising in transportation and logistics. We will classify network design problems and some of their most important features, including the interplay between investment and operational costs, the multicommodity aspect, and the presence of capacity constraints. We will study mathematical programming approaches and present methods designed to solve large-scale network design instances: cutting-plane and column generation methods, as well as Benders decomposition and Lagrangian relaxation approaches.

Lecture 1: Basic notions of mixed-integer programming

We review the basic notions of linear and mixed-integer programming, including polyhedral theory. This is necessary material to understand the decomposition methods covered in the lecture series. The lesson ends with the study of modeling alternatives for a simple network design problem, the two-level uncapacitated facility location problem.

Lecture 2: Introduction to network design and decomposition

Following a short description of network design problems, we study classical decomposition methods: cutting-plane and column generation, as well as the celebrated Benders decomposition and Lagrangian relaxation approaches.

Lecture 3: Multicommodity capacitated fixed-charge network design

We focus on a difficult network design problem, the multicommodity capacitated fixed-charge network design, and study the application of the decomposition methods seen in Lecture 2.

Lecture 4: Multicommodity capacitated network design

We study a problem similar to that of Lecture 3, where instead of a fixed cost for using an arc, a cost for installing capacity units on an arc has to be paid. This problem is generally modeled with general integer variables. We show how to reformulate the problem with binary variables, provide a Lagrangian-based interpretation of this reformulation, and show how to solve it with a column-and-row generation method.

Patrick Jaillet (MIT)

Title: Online Learning and Optimization under Uncertainty

There are many situations in which present actions must be made and resources allocated with incomplete knowledge of the future. The difficulty in these situations is that we may have to make decisions based only on the past and on the current task we have to perform. It is not even clear how to measure the quality of a proposed decision strategy, unless we make some additional assumptions about what we mean by uncertainty.

In the so-called adversarial setting, a proposed “online” strategy which operates with no knowledge of the future is compared with the performance of an optimal offline strategy that has complete knowledge of the future (and can adversarially choose that future to make the proposed online strategy the worst possible). This worst-case situation provides a baseline for what more one can achieve under additional information.

If the future can be described with a probabilistic model, and that model is precisely known to the decision maker/strategy designer, one could hope to find strategies which may perform better “on average”.

If the future does come from an underlying probabilistic structure, but that structure is not known a priori to the decision-maker, or may be known only approximately, but could potentially be learned along the way, strategies involving both learning and optimization may be the right approach.

In this series of lecture we will provide an overview of the state of the art associated with several relevant frameworks (online optimization, online learning, data-driven optimization) for tackling such questions. Motivated by important practical applications,  we will specifically concentrate on online variants of two classical optimization problems in operations research, (i) bipartite matching and (ii) linear programming.

Lecture 1: Introduction - Main concepts and frameworks

Lecture 2: Online bipartite matching problems and variants

Lecture 3: Online linear programing problems and variants

Lecture 4: What about data-driven optimization?

Tentative Program

  1. Abbaspourtorbati Farzaneh, EPFL
  2. Babonneau Frédéric, EPFL
  3. Baumann Philipp, University of Bern
  4. Bellocchi Leonardo, EPFL
  5. Bialecki Agnès, EDF R&D
  6. Bierlaire Michel, EPFL
  7. Binder Stefan, EPFL
  8. Bongiovanni Claudia, EPFL
  9. Cevallos Manzano Alfonso, EPFL
  10. Coindreau Marc-Antoine, University of Lausanne
  11. De Lapparent Matthieu, EPFL
  12. Fernández Antolín Anna, EPFL
  13. Forrer Salome, University of Bern
  14. Galby Esther, University of Fribourg
  15. Gallay Olivier, University of Lausanne
  16. Gendron Bernard, University of Montreal
  17. Gouvernet Cédric, EDF R&D
  18. Hanasusanto Grani Adiwena, EPFL
  19. Haurie Alain, University of Geneva
  20. Jaillet Patrick, MIT
  21. Karaskova Natalia, EPFL
  22. Kazagli Evanthia, EPFL
  23. Kirci Merve, EPFL
  24. Kocyigit Cagil, EPFL
  25. Kuhn Daniel, EPFL
  26. Lücker Florian, EPFL
  27. Maknoon Yousef, EPFL
  28. Markov Iliya, EPFL
  29. Mohajerin Esfahani Peyman, EPFL
  30. Moret Stefano, EPFL
  31. Nikolic Marija, EPFL
  32. Nguyen Viet Anh, EPFL
  33. Pacheco Paneque Meritxell, EPFL
  34. Ries Bernard, University of Fribourg
  35. Rihm Tom, University of Bern
  36. Robenek Tomas, EPFL
  37. Saeedmanesh Mohammadreza , EPFL
  38. Scarinci Riccardo, EPFL
  39. Shafieezadeh Abadeh Soroosh, EPFL
  40. Sharif Azadeh Shadi, EPFL
  41. Sirmatel Isik Ilber, EPFL
  42. Strub Oliver, University of Bern
  43. Timonina-Farkas Anna, EPFL
  44. Trautmann Norbert, University of Bern
  45. Valculescu Adrian-Claudiu, EPFL
  46. Van Delft Christian, HEC Paris
  47. Vial Jean-Philippe, University of Geneva
  48. Vié Marie-Sklaerder, University of Geneva
  49. Wehres Ulrich, EPFL
  50. Widmer Marino, University of Fribourg
  51. Zimmermann Adrian, University of Bern

Papers Bernard Gendron

Cordeau, J.; Costa, A. M.; Gendron, B. (2009): Benders, metric and cutset inequalities for multicommodity capacitated network design. Computational Optimization and Applications 42, 371–392

Crainica, T. G.; Frangionic, A.; Gendron, B. (2001): Bundle-based relaxation methods for multicommodity capacitated fixed charge network design. Discrete Applied Mathematics 112, 73–99

Gendron, B.; Larose, M. (2014): Branch-and-price-and-cut for large-scale multicommodity capacitated fixed-charge network design. EURO Journal on Computational Optimization 2, 55-75

Chouman, M.; Crainic, T. G.; Gendron, B. (2015): Commodity Representations and Cutset-Based Inequalities for Multicommodity Capacitated Fixed-Charge Network Design. Transportation Science, to appear - appendix

Papers Patrick Jaillet

Jaillet, P.; Wagner, M. (2010): Online Optimization – An Introduction. TutORials in Operations Research INFORMS 2010, 142-152

Jaillet, P.; Wagner, M. (2008): Generalized Online Routing: New Competitive Ratios, Resource Augmentation and Asymptotic Analyses. Operations Research 56, 745-757

Jaillet, P.; Lu, X. (2014): Online Traveling Salesman Problems with Rejection Options. Networks 64, 84-95

Jaillet, P.; Lu, X. (2014): Online Stochastic Matching: New Algorithms with Better Bounds. Mathematics of Operations Research 39, 624-646

Jaillet, P.; Sim, M.; Qi, J. (2015): Routing Optimization under Uncertainty. Operations Research, to appear (PDF, 573KB)