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.
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?
- Abbaspourtorbati Farzaneh, EPFL
- Babonneau Frédéric, EPFL
- Baumann Philipp, University of Bern
- Bellocchi Leonardo, EPFL
- Bialecki Agnès, EDF R&D
- Bierlaire Michel, EPFL
- Binder Stefan, EPFL
- Bongiovanni Claudia, EPFL
- Cevallos Manzano Alfonso, EPFL
- Coindreau Marc-Antoine, University of Lausanne
- De Lapparent Matthieu, EPFL
- Fernández Antolín Anna, EPFL
- Forrer Salome, University of Bern
- Galby Esther, University of Fribourg
- Gallay Olivier, University of Lausanne
- Gendron Bernard, University of Montreal
- Gouvernet Cédric, EDF R&D
- Hanasusanto Grani Adiwena, EPFL
- Haurie Alain, University of Geneva
- Jaillet Patrick, MIT
- Karaskova Natalia, EPFL
- Kazagli Evanthia, EPFL
- Kirci Merve, EPFL
- Kocyigit Cagil, EPFL
- Kuhn Daniel, EPFL
- Lücker Florian, EPFL
- Maknoon Yousef, EPFL
- Markov Iliya, EPFL
- Mohajerin Esfahani Peyman, EPFL
- Moret Stefano, EPFL
- Nikolic Marija, EPFL
- Nguyen Viet Anh, EPFL
- Pacheco Paneque Meritxell, EPFL
- Ries Bernard, University of Fribourg
- Rihm Tom, University of Bern
- Robenek Tomas, EPFL
- Saeedmanesh Mohammadreza , EPFL
- Scarinci Riccardo, EPFL
- Shafieezadeh Abadeh Soroosh, EPFL
- Sharif Azadeh Shadi, EPFL
- Sirmatel Isik Ilber, EPFL
- Strub Oliver, University of Bern
- Timonina-Farkas Anna, EPFL
- Trautmann Norbert, University of Bern
- Valculescu Adrian-Claudiu, EPFL
- Van Delft Christian, HEC Paris
- Vial Jean-Philippe, University of Geneva
- Vié Marie-Sklaerder, University of Geneva
- Wehres Ulrich, EPFL
- Widmer Marino, University of Fribourg
- Zimmermann Adrian, University of Bern
Slides Bernard Gendron
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
Slides Patrick Jaillet
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)