PhD School Lecture, 09/02/2021, 09:00 - 13:00
Department of Computer Science
University of Pisa
Lecture 2
The long road to practical decomposition methods
Many large-scale practical problems have, either naturally or after proper reformulation, (possibly, multiple) structures corresponding to the fact that some decisions are "closely related to a few others but loosely related with the rest". This can be algorithmically exploited with the two well-known, half-a-century-old decomposition approaches: the dual/Lagrangian/Dantzig-Wolfe one, and the primal/resource/Benders' one. The lecture reviews their basic ideas, showing that, despite some relevant differences, both boil down to solving a large-scale, nondifferentiable optimization problem whose objective function is itself one or more (possibly, costly) optimization problems. This has (again, 50+ years old) simple solution algorithms, whose by-the-book implementation unfortunately are often not efficient enough.
The lecture then reviews a number of ideas (some oldish and some newish) to speed-up decomposition approaches, such as stabilization, dual-optimal cuts, (partial) disaggregation, easy components, structured decomposition, and approximate subproblem solution. However, applying them in practice is challenging due to a limited support from standard modelling and solution tools, especially if one wants to exploit multiple nested forms of heterogeneous structure. This often results in decomposition being far less used in practice than it could be. I will end up by rapidly presenting a new modelling framework that I have been developing over the years and that has the ambition to help finally making decomposition a first-class citized in practical optimization.
Lecture Frangioni - Decomposition methods - Part 1
Lecture Frangioni - Decomposition methods - Part 2
Video Lecture Frangioni - Part 1
Video Lecture Frangioni - Part 2
Biosketch
Antonio Frangioni had an incredibly boring career entirely spent at the Department of Computer Science of the univeristy of Pisa, from the degree in Computer Science (1992), to the Ph.D. (1996), throughout all the academic ranks up to full professorship in 2012.
His research interest is the analysis, development, implementation and testing of solution approaches for large-scale structured optimization problems at the interface between continuous and combinatorial optimization, with emphasis on (re)formulation techniques to expose and exploit valuable structural properties, and their real-life application in several fields (energy, transportation, telecommunications, ...) He is also interested in the numerical analysis, computer science, artificial intelligence and machine learning issues arising within these solution approaches and, vice-versa, in the use of mathematical programming techniques in these disciplines.