Ricerca di strutture speciali in problemi di programmazione lineare intera

In general, Integer Linear Programming problems are computationally hard to solve. The design of efficient algorithms for them often takes advantage from the analysis of the problem underlying mathematical structure. Starting from the problem of finding the maximum embedded network submatrix of a matrix with entries in {0,−1, 1}, this work deals with the equivalent problem of finding the maximum balanced induced subgraph of a signed graph (mbs, Max Balanced Subgraph). In particular, a new heuristic for the mbs problem, the Cycle-Contraction Heuristic (CCH), has been proposed. The algoritm is based on a graph trans- formation rule that progressively reduces the lengths of cycles, preserving at the same time the feasibility of solutions for the mbs problem. CCH turns out to be more effective of the state-of-the-art heuristics. The efficiency and the effectiveness of CCH can be further improved by means of new rules of data reduction, i.e, by a procedure that simplifies instances and/or decrease their size while preserving the optimal solution of the problem. In the second part of the work, a new exact approach for the mbs prob- lem has been proposed. Such method is based on a polynomial complexity transformation rule that turns a signed graphs into a simple 2-layer graph. The transformation estabilishes a strong connection between mbs and the well- known maximun independent set problem (mis) and allows to resort to a broad spectrum of (exact or heuristic) solution methods proposed in the literature for mis. Finally, the generalized counterpart on signed graphs of some well-known combinatorial problems have been investigated. In particular it has been proven that the k-coloring problem on a signed graph - the generalization on signed graph of the balancing problem and the generalization on a simple graph of the bipartization problem - is equivalent to mis problem on a k-layer graph, i.e., a simple graph obtained by generalizing the 2-layer transformation.

I problemi di Programmazione Lineare Intera sono in generale notoriamente difficili da trattare sotto l’aspetto computazionale. La progettazione di algoritmi efficienti per problemi di tale natura, quindi, spesso trae grande vantaggio dallo studio della struttura matematica soggiacente. Prendendo come spunto il problema di determinare una sottomatrice massima di tipo network di una matrice a valori in {0,−1, 1}, nel lavoro di tesi si analizza il problema equivalente di bilanciamento di un grafo signed (mbs, Max Balanced Subgraph) e quindi si generalizzano alcuni dei risultati ottenuti a problemi combinatorici di più ampia portata. In particolare, lo studio ha portato all’ideazione e implementazione dell’euristica CCH (Cycle-Contraction Heuristic) per il problema mbs che è risultata più efficace delle euristiche esistenti in letteratura. L’algoritmo CCH è basato su una regola originale di trasformazione e semplificazione dei grafi che ne riduce progressivamente la lunghezza dei cicli senza per questo compromettere l’ammissibilità delle soluzioni determinate sul grafo modificato. Successivamente sono state ideate delle regole originali di data reduction che hanno lo scopo di semplificare le istanze e/o ridurne la dimensione, pur conservando su esse la soluzione ottima del problema. Con queste regole, le performance dell’euristica CCH sono migliorate sia in termini di efficienza che di efficacia. Nella tesi viene poi proposto un nuovo modello esatto per il problema mbs basato sulla trasformazione di un grafo signed in un grafo semplice detto 2- layer, stabilendo una stretta connessione tra il problema mbs e il più comune problema di massimo insieme stabile (mis). Il grafo 2-layer fornisce nuovi strumenti per progettare algoritmi per il problema mbs, basati sui numerosi metodi di soluzione (esatti o euristici) adottati per il problema mis. Infine, è stato affrontato il tema della generalizzazione di alcuni problemi combinatorici su grafi signed ed è stato esteso il modello 2-layer al modello k-layer. In particolare è stato provato che il problema di k-coloring di un grafo signed - che generalizza il problema di bilanciamento di un grafo signed e quello di bipartizione di un grafo semplice - equivale al problema mis sul grafo k-layer.