Folding Mixed-Integer Linear Programs and Reflection Symmetries

Dit paper breidt de bestaande DRCR-methode uit met reflectiesymmetrieën en toepassing op continue kolommen in gemengd-geheeltallige lineaire programmering, wat leidt tot aanzienlijke reducties in oplostijd en schaalbaarheid binnen de SCIP-oplosser.

De kern

De Kunst van het Opvouwen: Hoe Symmetrieën Wiskundige Puzzels Sneller Oplossen

Stel je voor dat je een enorme, ingewikkelde puzzel moet leggen. Maar er is een probleem: de puzzel heeft een rare eigenschap. Als je een stukje draait of spiegelt, ziet het er precies hetzelfde uit als de originele plek. In de wereld van wiskundige optimalisatie (het vinden van de beste oplossing voor een probleem) noemen we dit symmetrie.

Voor computers is dit een nachtmerrie. Een computer die een oplossing zoekt, denkt: "Oké, ik probeer deze optie." Maar omdat de puzzel symmetrisch is, probeert hij daarna per ongeluk exact dezelfde optie, maar dan een beetje gedraaid. Hij blijft maar rondcirkelen in dezelfde cirkels, tijd verspillend aan dingen die al zijn gedaan. Het is alsof je een doolhof loopt, maar elke keer als je een afslag neemt, kom je uit in een spiegelbeeld van de weg waar je net vandaan kwam.

Dit artikel, geschreven door Rolf van der Hulst, introduceert een slimme truc om deze symmetrieën te "opvouwen" en de puzzel kleiner en sneller oplosbaar te maken.

1. Het Oude Trucje: Kleuren en Groeperen

Eerder hadden wiskundigen al een manier bedacht om dit op te lossen voor simpele puzzels (lineaire programmering). Ze noemen dit DRCR (Dimension Reduction via Color Refinement).

Stel je voor dat je een groep mensen hebt die allemaal exact hetzelfde doen. In plaats van ze allemaal apart te tellen, zeg je: "Jullie zijn allemaal 'Groep A'." Je vervangt 100 individuen door één vertegenwoordiger. De computer hoeft dan niet meer 100 keer te rekenen, maar slechts één keer voor de hele groep. Dit werkt heel goed, maar alleen als de mensen echt identiek zijn (permutatiesymmetrie).

2. De Nieuwe Truc: Spiegels en "Opvouwen"

De auteur zegt: "Wacht, er is meer!" Sommige symmetrieën zijn niet alleen draaiingen, maar ook spiegelingen. Stel je voor dat een variabele (een getal in je puzzel) niet alleen kan worden verwisseld met een ander, maar ook kan worden omgekeerd (bijvoorbeeld: als 2 goed is, is 8 ook goed, omdat ze samen 10 zijn).

De auteur heeft de oude truc verbeterd door deze spiegelsymmetrieën ook te detecteren. Hij gebruikt een creatieve methode:

• Het Midden vinden: Hij schuift de puzzel zo dat het midden precies in het nulpunt ligt.
• Splijten: Hij neemt elke variabele en splitst hem in tweeën: een "positieve helft" en een "negatieve helft".
• Opvouwen: Door deze gesplitste versie te bekijken, ziet de computer de verborgen spiegelsymmetrieën die hij eerst niet zag. Vervolgens vouwt hij de puzzel weer op tot een veel kleinere versie.

De Analogie: Stel je voor dat je een grote, zware deken hebt die aan beide kanten identiek is. In plaats van de hele deken uit te spreiden om te kijken of er een vlek zit, vouw je hem dubbel. Nu is hij half zo groot, maar je kunt nog steeds zien of er een vlek is. Als je de oplossing voor de gevouwen deken hebt, kun je die makkelijk terugvertalen naar de volledige deken.

3. De Uitdaging: De "Integrale" Puzzelstukken

Het wordt nog spannender als je te maken hebt met Mixed-Integer Linear Programming (MILP). Dit zijn puzzels waar sommige stukjes moeten heel zijn (gehele getallen, zoals het aantal vrachtwagens), en andere stukjes kunnen breukdelen zijn (zoals de hoeveelheid brandstof).

De oude truc (DRCR) werkte niet goed voor deze gemengde puzzels, omdat het "opvouwen" soms de hele getallen-eigenschap verbrak. Je zou dan een oplossing krijgen voor de gevouwen puzzel die niet werkt voor de echte puzzel (bijvoorbeeld: 2,5 vrachtwagens).

De auteur lost dit op met een wiskundig concept dat Affine TU-decompositie heet. Klinkt ingewikkeld, maar het is eigenlijk een soort "garantie".

• Hij kijkt naar de structuur van de puzzel en zegt: "Als we deze specifieke groepen gehele getallen samenvoegen, blijft de puzzel 'netjes' genoeg om op te lossen."
• Hij gebruikt een speciale eigenschap van wiskundige netwerken (netwerkmatrices) om te bewijzen dat je de gehele getallen kunt samenvoegen zonder de oplossing te verpesten.
• Dit noemt hij "Exact Orbital Shrinking". Het is alsof je een groep vrachtwagens samenvoegt tot één "super-vrachtwagen" om de route te plannen, en later weet je zeker dat je die super-vrachtwagen weer perfect kunt verdelen in losse vrachtwagens zonder dat er iets misgaat.

4. Wat Leverde Dit Op?

De auteur heeft zijn nieuwe methoden getest op een enorme verzameling wiskundige problemen (MIPLIB 2017), die vaak worden gebruikt om echte wereldproblemen op te lossen, zoals logistiek, energieplanning en productie.

• Voor simpele puzzels: De nieuwe methode (met spiegels) was iets sneller dan de oude, vooral bij de moeilijkste problemen.
• Voor de gemengde puzzels (MILP): Dit was de grote winnaar. De nieuwe methode maakte de problemen soms twee keer zo snel oplosbaar voor de computer.
• Schaalbaarheid: De methode is snel genoeg om ook op gigantische problemen toegepast te worden zonder dat de computer vastloopt.

Conclusie

Kort samengevat: Rolf van der Hulst heeft een manier bedacht om wiskundige puzzels slimmer te "opvouwen". Door niet alleen te kijken naar verwisselbare stukjes, maar ook naar spiegels en door slimme garanties te gebruiken voor gehele getallen, kan de computer veel minder werk doen om de beste oplossing te vinden.

Het is alsof je in plaats van elke weg in een stad af te lopen, een kaart maakt waarop alle identieke straten als één lijn zijn getekend. Je vindt de route veel sneller, en als je die route terugkijkt, weet je precies welke straat je moet nemen. Dit maakt het oplossen van complexe wereldproblemen veel efficiënter.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Folding Mixed-Integer Linear Programs and Reflection Symmetries" van Rolf van der Hulst, geschreven in het Nederlands.

Probleemstelling

In de wiskundige optimalisatie, en specifiek bij gemengd-integer lineaire programmering (MILP) en lineaire programmering (LP), vormen symmetrieën een aanzienlijke uitdaging. Symmetrieën (zoals permutaties van variabelen of reflecties) kunnen leiden tot een enorme vermenigvuldiging van equivalente oplossingen in de zoekruimte van branch-and-bound algoritmen. Dit veroorzaakt een inefficiënte doorloop waarbij de solver dezelfde delen van de zoekruimte herhaaldelijk verkent, wat de prestaties sterk kan vertragen.

Bestaande methoden voor LP's, zoals het projecteren op de vaste ruimte van de symmetriegroep, zijn vaak te duur in berekening of vereisen het vinden van de volledige symmetriegroep (een NP-moeilijk probleem). Een efficiëntere aanpak is Dimension Reduction via Color Refinement (DRCR), ontwikkeld door Grohe et al. Deze methode gebruikt een snellere "color refinement" algoritme om variabelen te aggregeren op basis van hun structurele gelijkheid, waardoor de dimensie van het probleem wordt verkleind. Echter, de originele DRCR heeft twee beperkingen:

1. Het detecteert alleen permutatiesymmetrieën, maar negeert reflectiesymmetrieën (waarbij variabelen worden gespiegeld of omgekeerd, bijv. $x \to u-x$).
2. Het is niet direct toepasbaar op MILP's omdat het aggregeren van integer variabelen de integriteitsvoorwaarden kan schenden, wat leidt tot een relaxatie in plaats van een exacte oplossing.

Methodologie

De auteur breidt de DRCR-methode uit in twee hoofdrichtingen:

1. Uitbreiding naar Reflectiesymmetrieën (voor LP's)

Om reflectiesymmetrieën te detecteren, introduceert de auteur een transformatie van het lineaire programma:

• Affiene verschuiving: De oorsprong wordt verplaatst naar het midden van de domeinen van de variabelen ($x' = x - \delta$), zodat de onder- en bovengrenzen symmetrisch zijn rond nul.
• Split-reformulatie: Elke variabele $x'$ wordt opgesplitst in twee niet-negatieve variabelen: $x' = x^+ - x^-$. Hierbij vertegenwoordigt $x^+$ het positieve deel en $x^-$ het negatieve deel.
• Symmetrische Partities: Op deze gesplitste reformulatie wordt de color refinement toegepast. De auteur bewijst dat de verkregen "equitable partitions" (eerlijke partities) op de gesplitste matrix corresponderen met de beste mogelijke aggregering van het originele probleem, inclusief het omkeren van variabelen (complementatie) en het schalen van rijen.
• Resultaat: Dit leidt tot een Reflection Reduction, waarbij het oorspronkelijke LP wordt gereduceerd tot een kleiner LP dat equivalent is, zelfs bij aanwezigheid van reflecties.

2. Toepassing op Gemengd-Integer Lineaire Programmering (MILP)

Voor MILP's is het aggregeren van integer variabelen riskant omdat de som van integer variabelen niet per se integer is in de gereduceerde ruimte, of vice versa. De auteur lost dit op door:

• Exact Orbital Shrinking: In plaats van een relaxatie te maken, wordt gekeken naar wanneer de gereduceerde oplossing exact kan worden teruggevoerd naar een integer oplossing van het originele probleem.
• Affine Totally Unimodular (TU) Decompositie: De auteur gebruikt de theorie van affine TU-decomposities (gebaseerd op werk van Bader et al.) om te bepalen wanneer de "fibers" (de deelruimten die ontstaan door de gereduceerde variabelen vast te stellen) integraal zijn. Als de constraint matrix van het subprobleem een bepaalde structuur heeft (gerelateerd aan netwerkmatrices), dan garandeert dit dat integer oplossingen behouden blijven.
• Algoritme: Er wordt een algoritme ontwikkeld dat:
  1. De reflectie-reductie berekent.
  2. Controleert of de geaggregeerde integer variabelen voldoen aan de voorwaarden voor een affine TU-decompositie (door te kijken naar netwerkmatrices en getransponeerde netwerkmatrices).
  3. Indien nodig, de partitie verfijnt om de integriteitsvoorwaarden te waarborgen.

Kernbijdragen

1. Reflectie-uitbreiding van DRCR: Het paper toont aan dat DRCR kan worden uitgebreid naar reflectiesymmetrieën (gesigneerde permutaties) door middel van een split-reformulatie. Dit generaliseert de bestaande methode en pakt een bredere klasse van symmetrieën aan zonder de asymptotische complexiteit te verhogen ($O((n+m)\log n)$).
2. DRCR voor MILP: Het bewijst dat DRCR kan worden toegepast op de continue kolommen van MILP's (een bekend maar eerder niet gedocumenteerd "folklore"-resultaat) en, belangrijker, dat het kan worden uitgebreid naar integer variabelen via affine TU-decomposities.
3. Exacte Aggregatie: De methode garandeert dat de gereduceerde MILP een "perfecte formulering" is. Dit betekent dat elke integer oplossing van het gereduceerde probleem correspondeert met een integer oplossing van het originele probleem, zonder dat er een lastig subprobleem (zoals bij Orbital Shrinking) opgelost hoeft te worden via Constraint Programming.
4. Efficiënte Detectie: Het paper presenteert een implementatie die gebruikmaakt van snelle algoritmen voor het detecteren van netwerkmatrices, waardoor de methode schaalbaar is naar grote probleeminstanties.

Resultaten

De auteurs hebben hun methoden getest op de MIPLIB 2017 collectie (1065 instanties) met behulp van de SCIP 10 solver en SoPlex.

• Lineaire Programmering (LP Relaxaties):

  • De nieuwe methode met reflectiesymmetrieën (R-DRCR) presteert beter dan de originele DRCR.
  • Voor de 83 instanties waar R-DRCR extra reducties bood, was de gemiddelde rekentijd 27% lager.
  • Bij moeilijke instanties (>10 seconden) was de versnelling aanzienlijk (van 174s naar 58s gemiddeld).
  • In enkele gevallen werd het probleem gereduceerd tot één variabele en één rij.

• Gemengd-Integer Lineaire Programmering (MILP):

  • De methode is zeer effectief voor MILP's. Voor de instanties die door de methode werden beïnvloed, was de rekentijd gemiddeld meer dan twee keer zo snel als de standaard SCIP-configuratie.
  • De methode loste 7 nieuwe instanties op die met de standaardinstellingen niet binnen het tijdslimiet van 1 uur opgelost konden worden.
  • Voor niet-opgeloste instanties verbeterde de methode de Primal-Dual Integral (PDI), wat aangeeft dat de solver snellere en sterkere grenzen (bounds) bereikte.
  • De detectie-algoritmen zijn snel en schalen goed; de overhead voor presolving en postsolving is voor de meeste instanties verwaarloosbaar.

Betekenis en Impact

Dit paper vertegenwoordigt een belangrijke stap in de automatisering van symmetriebehandeling in optimalisatie:

• Brug tussen LP en MILP: Het overbrugt de kloof tussen krachtige symmetriebehandeling voor LP's en de complexere wereld van MILP's, waarbij het integriteit behoudt zonder de noodzaak van zware subprobleem-oplossers.
• Praktische Toepasbaarheid: De methode is geïmplementeerd en getest op een industriële solver (SCIP), wat aantoont dat het niet alleen theoretisch interessant is, maar ook concrete prestatiewinst oplevert.
• Efficiëntie: Door gebruik te maken van snelle color refinement en netwerkmatrix-detectie, blijft de methode computatie-efficiënt, zelfs voor zeer grote problemen.
• Toekomstperspectief: De auteurs wijzen op de noodzaak van snellere "crossover"-procedures (het terugvinden van een basisoplossing uit een interne punt) om de voordelen van DRCR volledig te benutten in branch-and-bound, en suggereren dat symmetrie-exploitatie hierbij een rol kan spelen.

Kortom, het paper introduceert een robuuste en snelle techniek om symmetrieën in zowel lineaire als gemengd-integer problemen te "vouwen" (folding), wat leidt tot aanzienlijke versnellingen in de oplossingstijd van complexe optimalisatieproblemen.