Models and algorithms for decomposition problems

Paronuzzi, Paolo (2020) Models and algorithms for decomposition problems, [Dissertation thesis], Alma Mater Studiorum Università di Bologna. Dottorato di ricerca in Ingegneria biomedica, elettrica e dei sistemi, 32 Ciclo. DOI 10.6092/unibo/amsdottorato/9330.
Documenti full-text disponibili:
[img] Documento PDF (English) - Richiede un lettore di PDF come Xpdf o Adobe Acrobat Reader
Disponibile con Licenza: Salvo eventuali più ampie autorizzazioni dell'autore, la tesi può essere liberamente consultata e può essere effettuato il salvataggio e la stampa di una copia per fini strettamente personali di studio, di ricerca e di insegnamento, con espresso divieto di qualunque utilizzo direttamente o indirettamente commerciale. Ogni altro diritto sul materiale è riservato.
Download (1MB)

Abstract

This thesis deals with the decomposition both as a solution method and as a problem itself. A decomposition approach can be very effective for mathematical problems presenting a specific structure in which the associated matrix of coefficients is sparse and it is diagonalizable in blocks. But, this kind of structure may not be evident from the most natural formulation of the problem. Thus, its coefficient matrix may be preprocessed by solving a structure detection problem in order to understand if a decomposition method can successfully be applied. So, this thesis deals with the k-Vertex Cut problem, that is the problem of finding the minimum subset of nodes whose removal disconnects a graph into at least k components, and it models relevant applications in matrix decomposition for solving systems of equations by parallel computing. The capacitated k-Vertex Separator problem, instead, asks to find a subset of vertices of minimum cardinality the deletion of which disconnects a given graph in at most k shores and the size of each shore must not be larger than a given capacity value. Also this problem is of great importance for matrix decomposition algorithms. This thesis also addresses the Chance-Constrained Mathematical Program that represents a significant example in which decomposition techniques can be successfully applied. This is a class of stochastic optimization problems in which the feasible region depends on the realization of a random variable and the solution must optimize a given objective function while belonging to the feasible region with a probability that must be above a given value. In this thesis, a decomposition approach for this problem is introduced. The thesis also addresses the Fractional Knapsack Problem with Penalties, a variant of the knapsack problem in which items can be split at the expense of a penalty depending on the fractional quantity.

Abstract
Tipologia del documento
Tesi di dottorato
Autore
Paronuzzi, Paolo
Supervisore
Dottorato di ricerca
Ciclo
32
Coordinatore
Settore disciplinare
Settore concorsuale
Parole chiave
Combinatorial Optimization, Decomposition Techniques, k-Vertex Cut problem, capacitated k-Vertex Separator problem, Chance-Constrained Mathematical Program, Fractional Knapsack Problem with Penalties
URN:NBN
DOI
10.6092/unibo/amsdottorato/9330
Data di discussione
31 Marzo 2020
URI

Altri metadati

Statistica sui download

Gestione del documento: Visualizza la tesi

^