On the facet pivot simplex method for linear programming

Dit artikel stelt een nieuwe facet-pivotsimplexmethode voor lineaire programmering voor die in numerieke tests superieur veelbelovend blijkt ten opzichte van de traditionele hoekpunt-pivotbenadering, en biedt nieuwe hoop voor het ontdekken van een pivotalgoritme met polynomiale tijd.

De kern

Stel je voor dat je de absoluut beste plek probeert te vinden om een limonadekraam op te zetten in een stad. De stad heeft de vorm van een complex, veelzijdig gebouw (een polytoop), en je wilt de hoek vinden die je het meeste geld oplevert.

Al meer dan 70 jaar is de standaardmanier om dit te doen de Vertex Pivot-methode (uitgevonden door George Dantzig). Denk aan deze methode als een toerist die rondloopt aan de buitenkant van het gebouw. Ze beginnen bij één hoek (vertex), kijken naar de aangrenzende hoeken en lopen naar de hoek die er beter uitziet. Ze blijven van hoek naar hoek huppelen langs de randen totdat ze de beste plek hebben gevonden.

Het probleem is dat het gebouw soms is ontworpen met een lastig doolhof van hoeken. In de worst-case scenario's moet de toerist misschien door elke enkele hoek lopen in een specifieke, vermoeiende volgorde voordat ze de beste plek vinden. Dit is als het lopen door een doolhof dat exponentieel langer wordt naarmate het gebouw groter wordt.

Het Nieuwe Idee: De "Facet Pivot"-methode

In dit artikel stelt de auteur, Yaguang Yang, een nieuwe manier voor om dit probleem op te lossen, genaamd de Facet Pivot Simplex-methode.

In plaats van langs de hoeken (vertices) te lopen, stel je voor dat je een bouwinspecteur bent die kijkt naar de facetten van het gebouw.

• De Oude Manier (Vertex): Je bent een toerist die van hoek naar hoek huppelt.
• De Nieuwe Manier (Facet): Je bent een inspecteur die de facetten verwisselt die je huidige "basis" definiëren om dichter bij de beste plek te komen.

Hier is hoe de nieuwe methode in eenvoudige termen werkt:

1. Begin met de Facetten, Niet de Hoeken: In plaats van te beginnen bij een hoek, begint het algoritme met het kiezen van een set facetten (beperkingen) die een tijdelijke, misschien imperfecte positie definiëren.
2. Verwissel Facetten, Niet Hoeken: Het algoritme kijkt naar de facetten die momenteel "gebroken" zijn of niet worden voldaan (zoals een facet dat de verkeerde kant op leunt). Het kiest de ergste en verwisselt deze met een ander facet dat helpt het probleem op te lossen.
3. Geen "Fase 1"-omweg: De oude methode vereist vaak een lange, dure "Fase 1"-reis alleen maar om een geldig startpunt te vinden voordat het überhaupt kan beginnen met het zoeken naar de beste plek. De nieuwe methode is slim: het begint met een opzet die wiskundig gegarandeerd direct werkt, waardoor die lange omweg volledig wordt overgeslagen. Het is alsof je een magische sleutel hebt die de deur van het gebouw direct opent, in plaats van eerst het slot te proberen te openen.

Waarom is dit opwindend?

Het artikel beweert dat deze nieuwe methode zeer veelbelovend is om twee hoofdredenen:

• Het is Sneller op Moeilijke Doolhoven: De auteur testte dit op "Klee-Minty-cubes", wiskundige doolhoven die specifiek zijn ontworpen om de oude toeristenmethode ertoe te brengen eeuwig te duren. De nieuwe facet-verwisselende methode loste deze doolhoven veel sneller op, met slechts een paar stappen in plaats van duizenden.
• Het is Robuuster: Bij tests op een enorme verzameling wiskundige problemen uit de echte wereld (de Netlib-benchmarks) loste de nieuwe methode bijna allemaal succesvol op. De oude "toeristen"-methode bleef soms steken of nam erg lang, en de "dual"-methode (een ander type toerist) gaf soms op omdat de geometrie van het gebouw te lastig was. De facet-verwisselende methode ging beter om met deze lastige geometrieën.

De Haken en Ogen (en de Hoop)

Het artikel erkent dat voor zeer grote, eenvoudige problemen de oude methode (of andere methoden zoals "Interior Point"-methoden, die lijken op het vliegen met een drone door het midden van het gebouw) misschien nog steeds sneller is.

De grote hoop is echter dat deze nieuwe "facet-verwisselende" aanpak de sleutel zou kunnen zijn tot het oplossen van een beroemd 60 jaar oud wiskundig mysterie: Kunnen we een methode vinden die gegarandeerd snel is (polynomiale tijd) voor elk probleem?

Decennialang hebben wiskundigen geprobeerd te bewijzen dat de oude "hoek-huppelende" methode snel genoeg is, maar ze vonden gevallen waarin het ontzettend traag is. Deze nieuwe "facet-verwisselende" methode biedt een nieuw perspectief. Het vertrouwt niet op dezelfde oude regels, en vroege tests suggereren dat het de weg kan zijn naar een oplossing die zowel snel als betrouwbaar is voor alle soorten lineaire programmeringsproblemen.

Samenvattend: Het artikel introduceert een nieuwe manier om wiskundige optimalisatieproblemen op te lossen door "facetten" te verwisselen in plaats van "hoeken" te huppelen. Het slaat de saaie opstappen over, gaat beter om met lastige doolhoven dan de oude methoden, en geeft wiskundigen nieuwe hoop om een perfecte, snelle oplossing voor alle problemen te vinden.

Technische samenvatting

Technische Samenvatting: Over de facet-pivotsimplexmethode voor lineaire programmering

Probleemstelling
Het artikel behandelt de computationele efficiëntie en theoretische beperkingen van de standaard vertex-pivotsimplexmethode voor het oplossen van Lineaire Programmerings (LP) problemen. Hoewel Dantzig's vertex-simplexmethode in de praktijk zeer effectief blijft, ontbreekt er een bewezen polynomiale tijdscomplexiteitsgrens. Theoretisch omvat het worst-case scenario voor vertex-methoden een exponentieel aantal iteraties (zoals aangetoond door Klee-Minty-kubussen), en de zoektocht naar een polynomiale pivot-algoritme is decennialang vruchteloos gebleven. Bovendien vereisen traditionele vertex-methoden vaak een computatievrij intensief "Fase I"-proces om een initiële haalbare basisoplossing te vinden, met name voor algemene LP-problemen die ongelijkheids- en grensbeperkingen omvatten.

Methodologie
De auteurs stellen een facet-pivotsimplexmethode voor die de pivot-operatie fundamenteel verschuift van vertices naar facetten (beperkingen).

• Algemene Formulering: De methode werkt op een algemene LP-formulering:
  $$\min c^T x$$
  $$\text{onder voorwaarde } A_I x = b_I, \quad A_J x \ge b_J, \quad \ell \le x \le u$$
  In tegenstelling tot standaardvormen die ongelijkheden omzetten in gelijkheden via slackvariabelen, behandelt deze benadering ongelijkheidsbeperkingen direct als facetten van het haalbare polytoop.

• Algoritmische Logica:

  • Basisdefinitie: In plaats van een basis van variabelen (vertices), onderhoudt het algoritme een basis van $d$ lineair onafhankelijke facetten (beperkingen), waarbij $d$ de dimensie van het probleem is.
  • Iteratief Proces: Het algoritme start met een initiële basisoplossing (vaak direct afgeleid van grensbeperkingen) die niet noodzakelijk haalbaar is. In elke iteratie kiest het een binnentredend facet (een niet-basisbeperking) en een vertrekkend facet (een basisbeperking) om de basis bij te werken.
  • Haalbaarheid en Optimaliteit: Het algoritme onderhoudt een representatie van de objectieve vector $c$ als een niet-negatieve lineaire combinatie van de huidige basisfacetten (waarmee een voorwaarde afgeleid uit het Lemma van Farkas wordt voldaan). Het verbetert de oplossing iteratief door facetten te vervangen om beperkingsviolaties te verminderen.
  • Beëindiging: Het proces stopt wanneer een haalbare basisoplossing wordt gevonden. Volgens de gepresenteerde optimaliteitsstellingen is dat punt optimaal als de objectieve vector kan worden uitgedrukt als een niet-negatieve combinatie van de actieve basisfacetten op een haalbaar punt.
  • Eindige Convergentie: Het artikel bewijst dat, wanneer de "minste/laagste indexregel" wordt toegepast voor het selecteren van binnentredende en vertrekkende facetten, het algoritme cycli vermijdt en in een eindig aantal stappen terminateert.

• Belangrijkste Onderscheidingen ten opzichte van de Duale Simplex: Hoewel de facet-pivotmethode enkele geometrische overeenkomsten deelt met de duale simplexmethode (bewegen tussen bases van beperkingen), is deze onderscheidend omdat deze uitsluitend op het oorspronkelijke probleem werkt zonder expliciet een duaal probleem te construeren of op te lossen. Het behandelt de algemene vorm direct, waardoor de conversie naar standaardvorm wordt vermeden.

Belangrijkste Bijdragen

1. Algoritmisch Voorstel: Het artikel introduceert een specifiek facet-pivot-algoritme (Algoritme 4.1) dat algemene LP-problemen oplost zonder een initialisatiestap in Fase I te vereisen.
2. Theoretische Waarborgen: De auteurs leveren wiskundige bewijzen (gebaseerd op het Lemma van Farkas) die aantonen dat het algoritme in een eindig aantal iteraties een optimale oplossing vindt en correct onhaalbare of onbegrensde problemen identificeert.
3. Implementatie: Een MATLAB-implementatie van het algoritme wordt geboden, samen met implementaties van Dantzig's simplex, duale simplex en interior-point-methoden voor vergelijking.
4. Omgaan met Beperkingen: De methode behandelt op natuurlijke wijze onder- en bovengrenzen en vrije variabelen zonder kunstmatige slackvariabelen in te voeren, wat resulteert in een kleinere probleemgrootte in vergelijking met conversies naar standaardvorm.

Experimentele Resultaten
De auteurs voerden numerieke tests uit op verschillende benchmarksets:

• Netlib-benchmarks: Op standaard Netlib-problemen met onder- en bovengrenzen vereiste de facet-pivotmethode over het algemeen minder CPU-seconden dan Dantzig's meest negatieve pivotregel. Het loste succesvol problemen op waarbij de duale simplexmethode faalde vanwege rangdeficiëntie of slechte conditie.
• Grootschalige Problemen: Voor zeer grote problemen (bijv. $n > 50.000$) presteerden Interior Point Methods (IPM), zoals verwacht, beter dan alle pivot-methoden. De facet-pivotmethode toonde echter robuustheid waar de duale simplexmethode faalde.
• Klee-Minty-kubussen: De facet-pivotmethode vertoonde aanzienlijk betere prestaties dan Dantzig's vertex-methode op Klee-Minty-varianten, waarbij veel minder iteraties nodig waren (vaak lineair of bijna lineair in dimensie $d$) in vergelijking met de exponentiële iteraties die door de vertex-methode worden vereist.
• Willekeurige Algemene Problemen: Voor algemene LP-problemen die in standaardmethoden Fase I vereisen, was de facet-pivotmethode aanzienlijk efficiënter dan Dantzig's methode omdat het de initialisatie in Fase I omzeilde.
• Standaard Willekeurige Problemen: Voor standaard LP-problemen waar Fase I niet vereist is, bleek Dantzig's methode iets efficiënter in CPU-tijd, hoewel het aantal iteraties vergelijkbaar was.

Betekenis en Claims
Het artikel beweert dat de facet-pivotsimplexmethode een veelbelovend alternatief biedt voor op vertices gebaseerde methoden, met name voor algemene LP-problemen met ongelijkheidsbeperkingen. De primaire betekenis ligt in:

• Eliminatie van Fase I: Door te starten vanuit een basisoplossing afgeleid van grensbeperkingen, vermijdt het de dure initialisatiefase die traditionele simplexmethode vereist voor algemene problemen.
• Robuustheid: Het toont grotere numerieke stabiliteit dan de duale simplexmethode op slecht geconditioneerde Netlib-problemen.
• Hoop voor Polynomiale Complexiteit: Hoewel de auteurs niet claimen een polynomiale tijdsbound te hebben bewezen, suggereren zij dat dit nieuwe type pivot-algoritme (werkend op facetten in plaats van vertices) een nieuwe weg biedt voor onderzoek naar het vinden van een polynomiale pivot-simplexmethode, waarmee Smale's 9e probleem wordt aangepakt.
• Praktische Efficiëntie: De methode blijkt zeer concurrerend en vaak superieur aan Dantzig's methode voor problemen met veel ongelijkheidsbeperkingen, zonder de overhead van het omzetten daarvan in gelijkheden.

De auteurs handhaven een nederige toon, waarbij zij erkennen dat Interior Point Methods superieur blijven voor zeer grootschalige problemen en dat de facet-pivotmethode een nieuwe richting is die verder onderzoek vereist om de theoretische complexiteitsgrenzen volledig te begrijpen.