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:

## Abstract

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).

Abstract

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

Autore

Parriani, Tiziano

Supervisore

Dottorato di ricerca

Scuola di dottorato

Scienze e ingegneria dell'informazione

Ciclo

26

Coordinatore

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

URN:NBN

DOI

10.6092/unibo/amsdottorato/6551

Data di discussione

3 Aprile 2014

URI

## Altri metadati

Tipologia del documento

Tesi di dottorato

Autore

Parriani, Tiziano

Supervisore

Dottorato di ricerca

Scuola di dottorato

Scienze e ingegneria dell'informazione

Ciclo

26

Coordinatore

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

URN:NBN

DOI

10.6092/unibo/amsdottorato/6551

Data di discussione

3 Aprile 2014

URI

## Statistica sui download

Gestione del documento: