Dottorato in AUTOMATICA, BIOINGEGNERIA E RICERCA OPERATIVA -
ABRO

Titolo della tesi: Methods for non-linear optimisation problems on graphs

Combinatorial optimization is the domain that is concerned with, given a problem with discrete variables (combinatorics), finding among a given set of possible configuration of the variables (feasible set) the best solution, in terms of minimizing or maximizing a function in the feasible set (optimization). Most combinatorial optimization problems are defined on graphs. This type of problems tend to be hard to solve (usually being NP-hard) and therefore different approaches need to be used in order to solve them. Two problems are studied in this thesis. The Maximum Cut problem (Max-Cut) for which a heuristic based on the subgraph sampling method is used to improve the state-of-the-art over a large testbed including instances coming from different types of graphs. And the Direct Current Optimal Transmission Switching, for which a separation procedure based on the cycles of a power network is proposed. The state-of-the-art regarding this separation problem was constrained to a fixed subset of the cycles of the graph. In this work is presented a general approach that does not consider a fixed set.