Integrality and cutting planes in semidefinite programming approaches for combinatorial optimization

Many real-life decision problems are discrete in nature. To solve such problems as mathematical optimization problems, integrality constraints are commonly incorporated in the model to reflect the choice of finitely many alternatives. At the same time, it is known that semidefinite programming is very suitable for obtaining strong relaxations of combinatorial optimization problems. In this dissertation, we study the interplay between semidefinite programming and integrality, where a special focus is put on the use of cutting-plane methods. Although the notions of integrality and cutting planes are well-studied in linear programming, integer semidefinite programs (ISDPs) are considered only recently. We show that manycombinatorial optimization problems can be modeled as ISDPs. Several theoretical concepts, such as the Chvátal-Gomory closure, total dual integrality and integer Lagrangian duality, are studied for the case of integer semidefinite programming. On the practical side, we introduce an improved branch-and-cut approach for ISDPs and a cutting-plane augmented Lagrangian method for solving semidefinite programs with a large number of cutting planes. Throughout the thesis, we apply our results to a wide range of combinatorial optimization problems, among which the quadratic cycle cover problem, the quadratic traveling salesman problem and the graph partition problem. Our approaches lead to novel, strong and efficient solution strategies for these problems, with the potential to be extended to other problem classes.

-

Semidefiniet programmeren is het deelgebied van wiskundige optimalisatie dat zich bezighoudt met de optimalisatie van een lineaire functie over de kegel van positief semidefiniete matrices onder de aanwezigheid van affiene randvoorwaarden. Omdat dit deelgebied ook lineaire programma’s omvat, kan semidefiniete optimalisatie worden gezien als een natuurlijke generalisering van lineaire wiskundige optimalisatie. In het bijzonder hebben semidefiniete programma’s (SDP’s) hun nut bewezen in het vermogen om sterke relaxaties te bieden voor complexe combinatorische optimaliseringsproblemen. Het succes van lineaire optimalisatie in veel praktische applicaties vormde de aanleiding voor het bestuderen van geheeltallige lineaire optimalisatie, waarmee beslissingsproblemen met e n eindig aantal oplossingen kunnen worden gemodelleerd. Een natuurlijke manier om deze problemen te benaderen wordt geboden via zogenaamde snijvlakmethoden, die een fundamenteel onderdeel zijn geworden in bijna alle moderne optimaliseringsalgoritmen. Voor semidefiniete programma’s zijn de theorie en het gebruik van geheeltalligheid en snijvlakken echter nog niet volledig onderzocht. Om semidefiniet programmeren geschikt te maken voor praktisch gebruik, is verder onderzoek en verkenning van deze conceptuele grondslagen noodzakelijk. Dit proefschrift draagt bij aan het begrip van deze concepten in het kader van semidefiniet programmeren, in de vorm van zes op zichzelf staande hoofdstukken. In het eerste deel van dit proefschrift concentreren we ons op de integratie van snijvlakken in continue semidefiniete programma’s. Het is bekend dat polyhedrale snijvlakken de semidefiniete relaxaties van combinatorische problemen aanzienlijk kunnen versterken. De huidige oplossingsalgoritmen voor semidefiniete programma’s in de literatuur hebben echter moeite met het omgaan met deze snijvlakken. Als alternatief introduceren we een op SDP gebaseerde snijvlakmethode die geschikt is voor de toevoeging van een groot aantal snijvlakken. Voortbouwend op een implementatie van de uitgebreide methode van Lagrange, worden snijvlakken toegevoegd middels een toepassing van het projectie-algoritme van Dykstra. Onze methode maakt gebruik van een warme-start strategie en kan (gedeeltelijk) worden geparallelliseerd door de verzameling snijvlakken te clusteren in deelverzamelingen van nietoverlappende snijvlakken. Deze ingredi¨enten maken een zeer efficiënte implementatie van het algoritme mogelijk. Omdat de belangrijkste componenten van onze methode generiek zijn, is ons algoritme geschikt voor het oplossen van algemene SDP’s met een groot aantal polyhedrale snijvlakken. We passen verschillende vormen van ons algoritme toe op diverse problemen in Hoofdstuk 3 en 4 van dit proefschrift. Numerieke resultaten laten substantiële verbeteringen zien in de sterkte van de berekende begrenzingen voor deze problemen, waarbij duizenden snijvlakken kunnen worden toegevoegd. Het tweede deel van het proefschrift richt zich op geheeltallige semidefiniete optimalisatie. Hoewel semidefiniete programma’s vaak worden gebruikt om sterke relaxaties voor discrete optimaliseringsproblemen te verkrijgen, is de integratie van geheeltalligheidsbeperkingen in de semidefiniete programma’s zelf pas zeer recentelijk in overweging genomen. We bestuderen diverse theoretische concepten gerelateerd aan semidefiniet programmeren met gehele getallen, welke voornamelijk generalisaties zijn van soortgelijke concepten uit geheeltallige Integrality and cutting planes in SDP approaches for CO lineaire programma’s. In het bijzonder bestuderen we de Chv´atal-Gomory afsluiting voor geheeltallig semidefiniet programmeren en de verbinding ervan met totale duale geheeltalligheid in Hoofdstuk 5. Dit leidt tot verschillende karakteriseringen en condities voor totale duale geheeltalligheid van een lineaire matrix ongelijkheid. In Hoofdstuk 6 breiden we de Lagrangiaanse dualiteitstheorie van geheeltallig lineair programmeren uit naar het geval van geheeltallig semidefiniet programmeren. Bovendien leidt een reeks resultaten met betrekking tot positief semidefiniete en geheeltallige matrices tot het modelleren van een breed scala aan combinatorische optimaliseringsproblemen als geheeltallige semidefiniete programma’s, waaronder verschillende binaire kwadratische problemen en problemen gerelateerd aan datawetenschap. Voor zover bij ons bekend, biedt dit proefschrift de eerste generieke benadering om de modelleringskracht van geheeltallig semidefiniet programmeren te demonstreren. Hoewel de bovengenoemde generalisaties van concepten uit geheeltallige lineaire optimalisatie op zichzelf interessant zijn, laten we ook zien hoe deze praktisch kunnen worden benut. Dit leidt tot de introductie van een op Chv´atal-Gomory gebaseerde snijvlakmethode en een geprojecteerde subgradi¨entmethode voor geheeltallig semidefiniet programmeren in respectievelijk Hoofdstuk 5 en 6. Numerieke resultaten laten de potentie van de geïntroduceerde aanpak voor verschillende probleemklassen zien, waarbij de verkregen algoritmen competitief en vaak zelfs krachtiger zijn dan de huidige oplossingsstrategie¨en voor deze problemen. In het proefschrift wordt bijzondere nadruk gelegd op de toepassing van onze methoden op problemen in combinatorische optimalisatie. Als terugkerende voorbeelden beschouwen we drie graafoptimaliseringsproblemen: het graafpartitie probleem (GPP), het kwadratisch cyclusdekkingsprobleem (QCCP) en het kwadratisch handelsreizigerprobleem (QTSP). De GPP en zijn varianten worden hoofdzakelijk behandeld in Hoofdstuk 4, waar we onze op SDP gebaseerde snijvlakmethode gebruiken om begrenzingen van grootschalige graafpartitie problemen te vinden. Dit zijn momenteel de sterkste GPP-begrenzingen in de literatuur. De QCCP en de QTSP zijn gerelateerde optimaliseringsproblemen die toepassingen hebben in onder meer bio-informatica, logistiek en energiedistributienetwerken. Ons onderzoek naar geheeltalligheid en snijvlakmethoden in SDP’s initieert nieuwe en efficiënte benaderingen voor het oplossen van beide problemen. Naast deze methoden verkennen we ook alternatieve oplossingsstrategie¨en. In Hoofdstuk 2 bestuderen we het linearisatieprobleem van de QCCP, waarbij de vraag wordt gesteld of een instantie van de QCCP kan worden opgelost als een equivalent lineair cyclusdekkingsprobleem. We bepalen diverse voorwaarden waaronder de kostmatrix van de QCCP lineairiseerbaar is en gebruiken deze voorwaarden om nieuwe begrenzingen te vinden die zowel sterk als effici¨ent berekenbaar zijn. Daarnaast introducerenwe verschillende nieuwe op LP en SDP gebaseerde bovengrenstechnieken voor de QCCP, zoals gerandomiseerde afrondingsmethoden en een reinforcement learning methode. In het laatste hoofdstuk van het proefschrift beschouwen we een ander combinatorisch optimaliseringsprobleem. Hoewel de voorgestelde oplossingsstrategie niet direct gerelateerd is met de andere onderdelen in het proefschrift, houdt het probleem zelf verband met een variant van de QTSP, namelijk het gegeneraliseerd handelsreizigersprobleem (GTSP). Een interessante toepassing van dit probleem is te vinden in de studie naar kwantumcircuits, waarbij het doel is om een toewijzing van qubits over een gegeven architectuur te vinden zodanig dat de totale overheadkosten voor het compileren van het circuit geminimaliseerd worden. Door de symmetrie¨en in het onderliggende probleem te bestuderen, kan het aantal variabelen en randvoorwaarden in het model aanzienlijk worden beperkt. Voor bepaalde speciale kwantumarchitecturen stelt deze reductie ons in staat om optimale qubit toewijzingen voor extreem grote kwantumcircuits te verkrijgen.