Models and algorithms for decomposition problems
- PDF / 112,544 Bytes
- 2 Pages / 439.37 x 666.142 pts Page_size
- 2 Downloads / 195 Views
Models and algorithms for decomposition problems Paolo Paronuzzi © Springer-Verlag GmbH Germany, part of Springer Nature 2020
This is a summary of the author’s PhD thesis in Biomedical, Electrical, and Systems Engineering (curriculum Operations Research), supervised by Enrico Malaguti and defended on 31/03/2020 at the University of Bologna (Department of Electric, Electronic and Information Engineering “Guglielmo Marconi”—DEI). The thesis is written in English and is available from the author upon request at [email protected]. This work deals with different perspectives on decomposition, seen as an approach and as a problem, respectively. A decomposition approach can be very effective for mathematical problems that present a specific structure in which the associated matrix of coefficients is very sparse and, in particular, it is diagonalizable in blocks. If this kind of structure is not evident from the most natural formulation of the problem, the coefficient matrix may be preprocessed by solving a structure detection problem. In this sense, the decomposition can be faced as a problem itself. This thesis deals with two different problems that belong to the family of the critical node detection problems and that find relevant applications in matrix decomposition. The capacitated vertex separator problem asks to find a subset of vertices of minimum cardinality the deletion of which disconnects a graph in at most k shores, and the size of each shore is bounded by a given capacity u. This problem is of great importance for matrix decomposition algorithms; indeed, it can be viewed as the problem of assigning the rows of a given matrix A to k disjoint blocks, each one of size at most u. The k-vertex cut problem, instead, is the problem of finding the minimum subset of vertices whose removal disconnects a graph into at least k components, and it also models relevant applications in matrix decomposition for solving systems of equations by parallel computing. In both cases, we extrapolate a bilevel formulation, in which the leader removes vertices from the graph, and the follower solves a combinatorial optimization problem on the resulting graph. This approach allows us to develop computational frameworks based on integer programming formulations in the natural space of the variables, and to derive different families of strengthening inequalities. This thesis also addresses the solution of chance-constrained mathematical programs, that represent a significant example in which decomposition techniques can be successfully applied. Here, the decomposition is introduced with its most common acceptation, that is, as a very effective solution method. In this class of stochastic optimization problems, 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 large probability. Stochastic optimization problems are often formulated with mathematical models whose coefficient matrix reveals a blocks
123
P. Paron
Data Loading...
