Decomposition methods for quadratic zero-one programming

The quadratic 0-1 programming with linear constraints (QP) is a general class of optimization problems that includes many combinatorial optimization problems. The Quadratic Assignment Problem (QAP), Quadratic Traveling Salesman Problem (QTSP), Graph Partitioning, Quadratic Knapsack Problem (QKP) and Quadratic Minimum Spanning Tree Problem (QMSTP) are among the well-known particular cases of the QP which arise in a variety of real-world applications. Since in general the QP is an NP-hard non-linear optimization problem, usually a problem reformulation is considered so that a computationally inexpensive bound on the optimal objective function value is obtained. In the first part of this thesis the most important solution methods for the QP are studied. These solution methods are divided into two main groups: Reformulation-Relaxation approaches (RR), and Reformulation-Decomposition approaches (RD). It is discussed how one can reformulate and solve the problem taking into account the problem structure. In the second part of the thesis, different RR and RD approaches are developed to four classical combinatorial optimization problems including QAP, QTSP, QMSTP, and Quadratic Shortest Path problem (QSP). As for the QAP, new compact reformulations are presented for the general case, and different decomposition strategies are developed for two special cases of the problem. The QTSP is another special case of QPs that is studied and analyzed in the spirit of the reformulation-decomposition. More precisely an extended Linear Programming formulation that contains a variable for each cycle in the graph is presented. Since the number of cycles is exponential in the graph size, the new formulation is solved via Column Generation approach. In the context of QMSTP, new bounding procedures based on a novel reformulation scheme and some new mixed 0-1 linear formulations are proposed. The efficiency of the proposed bounds is comprehensively discussed and some efficient dual-ascent algorithms to derive the new bounds are developed. Finally, quadratic shortest path problem is introduced as a novel QP. The NP-hardness of the problem is proved, and some bounding techniques for the problem are presented.

La programmazione quadratica 0-1 (QP) con vincoli lineari è una classe generale di problemi che comprende molti problemi di ottimizzazione combinatoria. L'assegnamento quadratico (QAP), il problema del TSP quadratico (QTSP), la partizione di grafi, il problema di zaino quadratico (QKP) e il problema dell'albero di copertura quadratico (QMSTP) sono alcuni casi particolari di QP tra i più noti che sorgono in molti settori applicativi. Dato che in generale QP è un problema NP-hard, spesso si ricorre a riformulazioni lineari per ottenere stime del valore della soluzione (bound) a costi computazionali ragionevoli. Nella prima parte della tesi vengono presentati e analizzati i più importanti metodi di soluzione dei problemi QP. Questi metodi sono suddivisi in due gruppi: approcci di riformulazione e rilassamento (RR) e metodi di Riformulazione e Decomposizione (RD). Si discuter di come è possibile riformulare e risolvere i problemi sfruttando la loro struttura. Nella seconda parte della tesi, verranno sviluppati diversi approcci RR e RD per quattro problemi classici di QP come QAP, QTSP, QMSTP e cammini minimi quadratici (QSP). Per quel che riguarda il QAP, verranno presentate delle nuove riformulazioni più compatte rispetto a quelle presenti nella letteratura, e sviluppati strategie di decomposizione per un paio di casi speciali. Il QTSP è un altro caso particolare di QP che viene affrontato con tecniche di riformulazione-decomposizione. In particolare verrà presentata una nuova tecnica di formulazione lineare estesa contenente una variabile per ogni ciclo del grafo. Dato che il numero di cicli è esponenziale nel numero dei nodi del grafo, la nuova formulazione è risolta con un approccio di Generazione di Colonne. Per quel che riguarda il QMSTP, vengono presentati nuovi metodi per ottenere stime del valore della soluzione ottima e nuovi schemi di riformulazione. Viene inoltre analizzata l'efficienza dei nuovi bound e vengono sviluppati alcuni metodi duali efficienti per ottenere nuovi bound. Infine viene introdotto un nuovo problema QP come il QSP. Ne viene dimostrata l'NP-completezza e vengono presentate alcune tecniche di stima del valore della soluzione.