Decomposition Methods and Network Design Problems

Parriani, Tiziano (2014) Decomposition Methods and Network Design Problems, [Dissertation thesis], Alma Mater Studiorum Università di Bologna. Dottorato di ricerca in Automatica e ricerca operativa, 26 Ciclo. DOI 10.6092/unibo/amsdottorato/6551.
Documenti full-text disponibili:
Documento PDF (English) - Richiede un lettore di PDF come Xpdf o Adobe Acrobat Reader
Download (6MB) | Anteprima


Decomposition based approaches are recalled from primal and dual point of view. The possibility of building partially disaggregated reduced master problems is investigated. This extends the idea of aggregated-versus-disaggregated formulation to a gradual choice of alternative level of aggregation. Partial aggregation is applied to the linear multicommodity minimum cost flow problem. The possibility of having only partially aggregated bundles opens a wide range of alternatives with different trade-offs between the number of iterations and the required computation for solving it. This trade-off is explored for several sets of instances and the results are compared with the ones obtained by directly solving the natural node-arc formulation. An iterative solution process to the route assignment problem is proposed, based on the well-known Frank Wolfe algorithm. In order to provide a first feasible solution to the Frank Wolfe algorithm, a linear multicommodity min-cost flow problem is solved to optimality by using the decomposition techniques mentioned above. Solutions of this problem are useful for network orientation and design, especially in relation with public transportation systems as the Personal Rapid Transit. A single-commodity robust network design problem is addressed. In this, an undirected graph with edge costs is given together with a discrete set of balance matrices, representing different supply/demand scenarios. The goal is to determine the minimum cost installation of capacities on the edges such that the flow exchange is feasible for every scenario. A set of new instances that are computationally hard for the natural flow formulation are solved by means of a new heuristic algorithm. Finally, an efficient decomposition-based heuristic approach for a large scale stochastic unit commitment problem is presented. The addressed real-world stochastic problem employs at its core a deterministic unit commitment planning model developed by the California Independent System Operator (ISO).

Tipologia del documento
Tesi di dottorato
Parriani, Tiziano
Dottorato di ricerca
Scuola di dottorato
Scienze e ingegneria dell'informazione
Settore disciplinare
Settore concorsuale
Parole chiave
Combinatorial Optimization, Dantzig-Wolfe Decomposition, Frank-Wolfe Algorithm, Generalized Bundle Methods, Heuristic, Local Search, Multicommodity Network Flows, Progressive Hedging, Robust Network Design, Traffic Assignment, Two-stage Programming, Unit Commitment
Data di discussione
3 Aprile 2014

Altri metadati

Statistica sui download

Gestione del documento: Visualizza la tesi