LP-type probleem - LP-type problem

In de studie van algoritmen is een LP-type probleem (ook wel een gegeneraliseerd lineair programma genoemd ) een optimalisatieprobleem dat bepaalde eigenschappen deelt met laagdimensionale lineaire programma's en dat kan worden opgelost door vergelijkbare algoritmen. Problemen van het LP-type omvatten veel belangrijke optimalisatieproblemen die zelf geen lineaire programma's zijn, zoals het probleem van het vinden van de kleinste cirkel die een gegeven reeks vlakke punten bevat. Ze kunnen worden opgelost door een combinatie van gerandomiseerde algoritmen in een hoeveelheid tijd die lineair is in het aantal elementen dat het probleem definieert, en subexponentieel in de dimensie van het probleem.

Definitie

LP-type problemen werden door Sharir & Welzl (1992) gedefinieerd als problemen waarbij een eindige verzameling S elementen als invoer wordt gegeven , en een functie f die subverzamelingen van S afbeeldt op waarden uit een totaal geordende verzameling. De functie is vereist om aan twee belangrijke eigenschappen te voldoen:

  • Monotoniciteit: voor elke twee sets A ⊆ B ⊆ S , f ( A ) f ( B ) f ( S ).
  • Lokaliteit: voor elke twee verzamelingen A ⊆ B ⊆ S en elk element x in S , als f ( A ) = f ( B ) = f ( A ∪ { x }) , dan is f ( A ) = f ( B ∪ { x }) .

Een basis van een LP-type probleem is een verzameling B ⊆ S met de eigenschap dat elke juiste deelverzameling van B een kleinere waarde van f heeft dan B zelf, en de dimensie (of combinatorische dimensie ) van een LP-type probleem wordt gedefinieerd als de maximale kardinaliteit van een basis zijn.

Er wordt aangenomen dat een optimalisatie-algoritme de functie f alleen kan evalueren op verzamelingen die zelf basen zijn of die worden gevormd door een enkel element aan een basis toe te voegen. Als alternatief kan het algoritme worden beperkt tot twee primitieve bewerkingen: een overtredingstest die voor een basis B en een element x bepaalt of f ( B ) = f ( B ∪ { x }) , en een basisberekening die (met dezelfde inputs) vindt een basis van B ∪ { x }. De taak die het algoritme moet uitvoeren, is om f ( S ) te evalueren door alleen deze beperkte evaluaties of primitieven te gebruiken.

Voorbeelden en toepassingen

Lp Ballen

Een lineair programma kan worden gedefinieerd door een systeem van d niet-negatieve reële variabelen , onderworpen aan n lineaire ongelijkheidsbeperkingen, samen met een niet-negatieve lineaire doelfunctie die moet worden geminimaliseerd. Dit kan in het kader van problemen van het LP-type worden geplaatst door S de verzameling beperkingen te laten zijn en f ( A ) (voor een deelverzameling A van de beperkingen) te definiëren als de minimale objectieve functiewaarde van het kleinere lineaire programma gedefinieerd door een . Met geschikte algemene positie-aannames (om te voorkomen dat meerdere oplossingspunten dezelfde optimale objectieve functiewaarde hebben), voldoet dit aan de monotoniciteit en lokaliteitsvereisten van een LP-type probleem, en heeft het een combinatorische dimensie gelijk aan het aantal d variabelen. Evenzo voldoet een geheeltallig programma (bestaande uit een verzameling lineaire beperkingen en een lineaire doelfunctie, zoals in een lineair programma, maar met de extra beperking dat de variabelen alleen gehele waarden mogen aannemen) zowel aan de monotoniciteit als aan de lokaliteitseigenschappen van een LP -type probleem, met dezelfde algemene positie-aannames als voor lineaire programma's. Stellingen van Bell (1977) en Scarf (1977) laten zien dat voor een integer programma met d- variabelen de combinatorische dimensie maximaal  2 d is .

Veel natuurlijke optimalisatieproblemen in computationele geometrie zijn van het LP-type:

Image
Kleinste cirkel probleem
  • Het kleinste cirkelprobleem is het probleem van het vinden van de minimale straal van een cirkel met een gegeven verzameling van n punten in het vlak. Het voldoet aan monotoniciteit (het toevoegen van meer punten kan de cirkel alleen maar groter maken) en lokaliteit (als de kleinste cirkel voor verzameling A B en x bevat , dan bevat dezelfde cirkel ook B ∪ { x }). Omdat de kleinste cirkel altijd wordt bepaald door zo'n drie punten, heeft het kleinste cirkelprobleem combinatorische dimensie drie, ook al is het gedefinieerd met behulp van tweedimensionale Euclidische meetkunde. Meer in het algemeen vormt de kleinste omsluitende bal van punten in d dimensies een LP-type probleem van combinatorische dimensie d + 1 . Het kleinste cirkelprobleem kan worden gegeneraliseerd naar de kleinste bal die een set ballen omsluit, naar de kleinste bal die elk van een set ballen raakt of omringt, naar het gewogen 1-centrumprobleem , of naar soortgelijke kleinere omsluitende balproblemen in niet- Euclidische ruimten zoals de ruimte met afstanden gedefinieerd door Bregman divergentie . Het gerelateerde probleem van het vinden van de kleinste omsluitende ellipsoïde is ook een LP-type probleem, maar met een grotere combinatorische dimensie, d ( d + 3)/2 .
  • Laat K 0 , K 1 , ... een rij zijn van n convexe verzamelingen in de d- dimensionale Euclidische ruimte, en stel dat we de langste prefix van deze rij willen vinden die een gemeenschappelijk snijpunt heeft. Dit kan worden uitgedrukt als een LP-type probleem waarin f ( A ) = − i waarbij K i het eerste lid van A is dat niet behoort tot een snijdend voorvoegsel van A , en waarbij f ( A ) = − n als er is niet zo'n lid. De combinatorische dimensie van dit systeem is d + 1 .
  • Stel dat we een verzameling van op de as uitgelijnde rechthoekige dozen in een driedimensionale ruimte krijgen, en we willen een lijn vinden die in het positieve octant van de ruimte is gericht en die door alle dozen snijdt. Dit kan worden uitgedrukt als een LP-type probleem met combinatorische dimensie 4.
  • Het probleem van het vinden van de kleinste afstand tussen twee convexe polytopen , gespecificeerd door hun sets hoekpunten, kan worden weergegeven als een LP-type probleem. In deze formulering is de verzameling S de verzameling van alle hoekpunten in beide polytopen, en de functiewaarde f ( A ) is de negatie van de kleinste afstand tussen de convexe rompen van de twee deelverzamelingen A van hoekpunten in de twee polytopen. De combinatorische dimensie van het probleem is d + 1 als de twee polytopen onsamenhangend zijn, of d + 2 als ze een niet-lege kruising hebben.
  • Laat S = { f 0 , f 1 , ... } een verzameling quasiconvexe functies zijn . Dan de maximale puntsgewijs max i f i zelf quasiconvex en het probleem van het vinden van de minimale waarde van max i f i een LP-probleemtype. Het heeft een combinatorische dimensie van maximaal 2 d + 1 , waarbij d de dimensie is van het domein van de functies, maar voor voldoende vloeiende functies is de combinatorische dimensie kleiner, maximaal d + 1 . Veel andere problemen van het LP-type kunnen op deze manier ook worden uitgedrukt met behulp van quasconvexe functies; het kleinste omsluitende cirkelprobleem is bijvoorbeeld het probleem van het minimaliseren van max i f i waarbij elk van de functies f i de Euclidische afstand vanaf een van de gegeven punten meet.

Problemen van het LP-type zijn ook gebruikt om de optimale resultaten van bepaalde spellen in de algoritmische speltheorie te bepalen , de plaatsing van hoekpunten in mazen van de eindige-elementenmethode te verbeteren , faciliteitslocatieproblemen op te lossen, de tijdcomplexiteit van bepaalde zoekalgoritmen met exponentiële tijd te analyseren en de driedimensionale posities van objecten uit hun tweedimensionale afbeeldingen.

Algoritmen

Seidel

Seidel (1991) gaf een algoritme voor laagdimensionale lineaire programmering dat kan worden aangepast aan het LP-type probleemraamwerk. Seidel's algoritme neemt als invoer de verzameling S en een aparte verzameling X (aanvankelijk leeg) van elementen waarvan bekend is dat ze tot de optimale basis behoren. Vervolgens worden de resterende elementen één voor één in willekeurige volgorde bekeken, voor elk element overtredingstests uitgevoerd en, afhankelijk van het resultaat, een recursieve aanroep naar hetzelfde algoritme uitgevoerd met een grotere set bekende basiselementen. Het kan worden uitgedrukt met de volgende pseudocode: 

function seidel(S, f, X) is
    R := empty set
    B := X
    for x in a random permutation of S:
        if f(B) ≠ f(B ∪ {x}):
            B := seidel(R, f, basis(X ∪ {x}))
        R := R ∪ {x}
    return B

In een probleem met combinatorische dimensie d , faalt de overtredingstest in de i th iteratie van het algoritme alleen als x een van de d − | X | resterende basiselementen, wat met hoogstens waarschijnlijkheid gebeurt ( d − | X |)/ i . Op basis van deze berekening kan worden aangetoond dat het totale verwachte aantal overtredingstests dat door het algoritme wordt uitgevoerd O( d ! n) is , lineair in n maar slechter dan exponentieel in d .

Clarkson

Clarkson (1995) definieert twee algoritmen, een recursief algoritme en een iteratief algoritme, voor lineair programmeren op basis van willekeurige steekproeven, en suggereert een combinatie van beide die het iteratieve algoritme van het recursieve algoritme oproept. Het recursieve algoritme kiest herhaaldelijk willekeurige steekproeven waarvan de grootte ongeveer de vierkantswortel van de invoergrootte is, lost het bemonsterde probleem recursief op en gebruikt vervolgens overtredingstests om een ​​subset van de resterende elementen te vinden die ten minste één basiselement moet bevatten: 

function recursive(S, f) is
    X := empty set
    repeat
        R := a random subset of S with size d√n
        B := basis for R ∪ X, computed recursively
        V := {x | f(B) ≠ f(B ∪ {x})}
        X := X ∪ V
    until V is empty
    return B

In elke iteratie, de verwachte grootte van V is O ( √ n ) , en wanneer V niet leeg deze ten minste een nieuw element van de uiteindelijke basis S . Daarom voert het algoritme maximaal d iteraties uit, die elk n overtredingstesten uitvoeren en een enkele recursieve aanroep doen naar een subprobleem met de grootte O( d √ n ) .

Het iteratieve algoritme van Clarkson kent gewichten toe aan elk element van S , aanvankelijk allemaal gelijk. Vervolgens kiest het willekeurig een verzameling R van 9 d 2 elementen uit S en berekent de verzamelingen B en V zoals in het vorige algoritme. Als het totale gewicht van V maximaal 2/(9 d − 1) maal het totale gewicht van S is (zoals gebeurt met constante waarschijnlijkheid), dan verdubbelt het algoritme de gewichten van elk element van V , en herhaalt het dit proces zoals eerder totdat V wordt leeg. In elke iteratie kan worden aangetoond dat het gewicht van de optimale basis sneller toeneemt dan het totale gewicht van S , waaruit volgt dat het algoritme moet eindigen binnen O (log n ) iteraties.

Door het recursieve algoritme te gebruiken om een ​​bepaald probleem op te lossen, over te schakelen naar het iteratieve algoritme voor zijn recursieve aanroepen en dan weer over te schakelen naar het algoritme van Seidel voor de aanroepen van het iteratieve algoritme, is het mogelijk om een ​​gegeven LP-type probleem op te lossen met O( dn + d ! d O(1) log n ) overtredingstests.

Wanneer toegepast op een lineair programma, kan dit algoritme worden geïnterpreteerd als een dual simplex-methode . Met bepaalde aanvullende computationele primitieven buiten de overtredingstest en basisberekeningsprimitieven, kan deze methode deterministisch worden gemaakt.

Matousek, Sharir en Welzl

Matoušek, Sharir & Welzl (1996) beschrijven een algoritme dat gebruikmaakt van een extra eigenschap van lineaire programma's die niet altijd door andere problemen van het LP-type wordt aangehouden, namelijk dat alle basen dezelfde kardinaliteit van elkaar hebben. Als een LP-type probleem deze eigenschap niet heeft, kan het worden verkregen door d nieuwe dummy-elementen toe te voegen en door de functie f te wijzigen om het geordende paar van zijn oude waarde f ( A ) en van het getal min( d ,| A |) , lexicografisch geordend .

In plaats van elementen van S één voor één toe te voegen of monsters van de elementen te vinden, beschrijven Matoušek, Sharir & Welzl (1996) een algoritme dat elementen één voor één verwijdert. Bij elke stap handhaaft het een basis C die aanvankelijk de verzameling dummy-elementen kan zijn. Het kan worden beschreven met de volgende pseudocode: 

function msw(S, f, C) is
    if S = C then
        return C
    choose a random element x of S \ C
    B = msw(S \ x, f, C)
    if f(B) ≠ f(B ∪ {x}) then
        B := basis(B ∪ {x})
        B := msw(S, f, B)
    return B

In de meeste recursieve aanroepen van het algoritme slaagt de overtredingstest en wordt het if-statement overgeslagen. Met een kleine waarschijnlijkheid faalt de overtredingstest en maakt het algoritme een aanvullende basisberekening en vervolgens een aanvullende recursieve aanroep. Zoals de auteurs laten zien, is de verwachte tijd voor het algoritme lineair in n en exponentieel in de vierkantswortel van d log n . Door deze methode te combineren met de recursieve en iteratieve procedures van Clarkson, kunnen deze twee vormen van tijdsafhankelijkheid van elkaar worden gescheiden, wat resulteert in een algoritme dat O( dn ) -schendingstests uitvoert in het buitenste recursieve algoritme en een getal dat exponentieel is in de vierkantswortel van d log d in de lagere niveaus van het algoritme.

variaties

Optimalisatie met uitschieters

Matoušek (1995) beschouwt een variatie van optimalisatieproblemen van het LP-type waarbij één, samen met de verzameling S en de doelfunctie f , een getal k wordt gegeven ; de taak is om k elementen uit S te verwijderen om de doelfunctie op de resterende verzameling zo klein mogelijk te maken. Als dit bijvoorbeeld wordt toegepast op het probleem met de kleinste cirkel, zou dit de kleinste cirkel opleveren die alles behalve k van een gegeven reeks vlakke punten bevat. Hij laat zien dat voor alle niet-gedegenereerde problemen van het LP-type (d.w.z. problemen waarin alle basen verschillende waarden hebben) dit probleem kan worden opgelost in de tijd O( nk d ) , door een verzameling O( k d ) LP op te lossen. -type problemen gedefinieerd door subsets van S .

Impliciete problemen

Sommige geometrische optimalisatieproblemen kunnen worden uitgedrukt als LP-type problemen waarin het aantal elementen in de LP-type formulering significant groter is dan het aantal invoergegevenswaarden voor het optimalisatieprobleem. Beschouw als voorbeeld een verzameling van n punten in het vlak, die elk met constante snelheid bewegen. Op elk moment is de diameter van dit systeem de maximale afstand tussen twee van zijn punten. Het probleem van het vinden van een tijdstip waarop de diameter wordt geminimaliseerd kan worden geformuleerd als het minimaliseren van de puntsgewijze maximaal O ( n 2 ) quasiconvex functies, één voor elk paar punten, het meten van de Euclidische afstand tussen het paar als functie van de tijd. Aldus kan worden opgelost als een LP-probleemtype combinatorische dimensie twee op een reeks O ( n 2 ) elementen, maar deze set is aanzienlijk groter dan het aantal ingangspunten.

Chan (2004) beschrijft een algoritme voor het oplossen van impliciet gedefinieerde problemen van het LP-type, zoals dit waarin elk element van het LP-type wordt bepaald door een k -tupel van invoerwaarden, voor een constante k . Om zijn benadering toe te passen, moet er een beslissingsalgoritme bestaan dat voor een gegeven LP-type basis B en set S van n invoerwaarden kan bepalen of B een basis is voor het LP-type probleem bepaald door S .

Het algoritme van Chan voert de volgende stappen uit:

  • Als het aantal invoerwaarden onder een bepaalde drempelwaarde ligt, zoek dan de verzameling LP-type elementen die het bepaalt en los het resulterende expliciete LP-type probleem op.
  • Anders Verdeel de invoerwaarden in een geschikt getal groter dan k van even grote subsets S i .
  • Als f is de objectieve functie voor de impliciet gedefinieerde LP-type op te lossen probleem, hier een functie g die is toegewezen verzamelingen subsets S i de waarde van f op de vereniging van de collectie. Vervolgens het verzamelen van subsets S i en de doelfunctie g zichzelf definieert een LP-probleemtype van dezelfde afmeting als impliciete op te lossen probleem.
  • Los het (expliciete) LP-type probleem gedefinieerd door g op met behulp van het algoritme van Clarkson, dat een lineair aantal overtredingstesten en een polylogaritmisch aantal basisevaluaties uitvoert. De basisevaluaties voor g kunnen worden uitgevoerd door recursieve oproepen naar het algoritme van Chan, en de overtredingstesten kunnen worden uitgevoerd door oproepen naar het beslissingsalgoritme.

Met de aanname dat het beslissingsalgoritme een hoeveelheid tijd O( T ( n )) nodig heeft die ten minste polynoom groeit als functie van de invoergrootte n , laat Chan zien dat de drempel voor het overschakelen naar een expliciete LP-formulering en het aantal deelverzamelingen in de partitie kan zodanig worden gekozen dat het impliciete optimalisatie-algoritme van het LP-type ook in de tijd O( T ( n )) loopt .

Voor de minimale diameter van bewegende punten hoeft het beslissingsalgoritme bijvoorbeeld alleen de diameter van een reeks punten op een vast tijdstip te berekenen, een probleem dat kan worden opgelost in O( n log n ) tijd met behulp van de roterende schuifmaattechniek . Daarom kost Chan's algoritme voor het vinden van het tijdstip waarop de diameter wordt geminimaliseerd, ook tijd O( n log n ) . Chan gebruikt deze methode om een ​​punt met maximale Tukey-diepte te vinden tussen een gegeven verzameling van n punten in de d- dimensionale Euclidische ruimte, in de tijd O( n d − 1 + n log n ) . Een vergelijkbare techniek werd gebruikt door Braß, Heinrich-Litan & Morin (2003) om een ​​punt met maximale Tukey-diepte te vinden voor de uniforme verdeling op een convexe veelhoek.

Geschiedenis en gerelateerde problemen

De ontdekking van lineaire tijdalgoritmen voor lineaire programmering en de observatie dat dezelfde algoritmen in veel gevallen kunnen worden gebruikt om geometrische optimalisatieproblemen op te lossen die geen lineaire programma's waren, gaat in ieder geval terug tot Megiddo ( 1983 , 1984 ), die een lineaire verwachte tijd gaf. algoritme voor zowel lineaire programma's met drie variabelen als het kleinste cirkelprobleem. Megiddo formuleerde de veralgemening van lineaire programmering echter eerder geometrisch dan combinatorisch, als een convex optimalisatieprobleem in plaats van als een abstract probleem op stelsels van verzamelingen. Evenzo merkten Dyer (1986) en Clarkson (in de conferentieversie van Clarkson 1995 uit 1988 ) op dat hun methoden zowel op convexe programma's als op lineaire programma's kunnen worden toegepast. Dyer (1992) toonde aan dat het minimum omsluitende ellipsoïde probleem ook kan worden geformuleerd als een convex optimalisatieprobleem door een klein aantal niet-lineaire beperkingen toe te voegen. Het gebruik van randomisatie om de tijdsgrenzen voor laagdimensionale lineaire programmering en gerelateerde problemen te verbeteren werd ontwikkeld door Clarkson en door Dyer & Frieze (1989) .

De definitie van problemen van het LP-type in termen van functies die voldoen aan de axioma's van lokaliteit en monotoniciteit is afkomstig van Sharir & Welzl (1992) , maar andere auteurs formuleerden in hetzelfde tijdsbestek alternatieve combinatorische generalisaties van lineaire programma's. Bijvoorbeeld, in een raamwerk ontwikkeld door Gärtner (1995) wordt de functie f vervangen door een totale ordening op de deelverzamelingen van S . Het is mogelijk om de banden in een LP-type probleem te verbreken om een ​​totale orde te creëren, maar alleen ten koste van een toename van de combinatorische dimensie. Bovendien definieert Gärtner, net als bij problemen van het LP-type, bepaalde primitieven voor het uitvoeren van berekeningen op subsets van elementen; zijn formalisering heeft echter geen analogie van de combinatorische dimensie.

Een andere abstracte generalisatie van zowel lineaire programma's als lineaire complementariteitsproblemen , geformuleerd door Stickney & Watson (1978) en later bestudeerd door verschillende andere auteurs, betreft oriëntaties van de randen van een hyperkubus met de eigenschap dat elk vlak van de hyperkubus (inclusief de hele hyperkubus als een gezicht) heeft een unieke gootsteen , een hoekpunt zonder uitgaande randen. Een oriëntatie van dit type kan worden gevormd uit een LP-type probleem door de deelverzamelingen van S zo te corresponderen met de hoekpunten van een hyperkubus dat twee deelverzamelingen verschillen door een enkel element als en slechts als de corresponderende hoekpunten aangrenzend zijn, en door oriënteren van de rand tussen naburige verzamelingen A ⊆ B richting B als f ( A ) ≠ f ( B ) en in de richting A verder. De resulterende oriëntatie heeft de extra eigenschap dat het een gerichte acyclische grafiek vormt , waaruit kan worden aangetoond dat een gerandomiseerd algoritme de unieke put van de hele hyperkubus (de optimale basis van het LP-type probleem) in een aantal stappen kan vinden exponentieel in de vierkantswortel van  n .

Het meer recent ontwikkelde raamwerk van overtrederruimten generaliseert LP-type problemen, in die zin dat elk LP-type probleem kan worden gemodelleerd door een overtrederruimte, maar niet noodzakelijkerwijs vice versa. Overtredingsruimten worden op dezelfde manier gedefinieerd als problemen van het LP-type, door een functie f die sets toewijst aan objectieve functiewaarden, maar de waarden van f zijn niet geordend. Ondanks het gebrek aan ordening, heeft elke set S een goed gedefinieerde set bases (de minimale sets met dezelfde waarde als de hele set) die kunnen worden gevonden door variaties van Clarkson's algoritmen voor problemen van het LP-type. Het is inderdaad aangetoond dat overtrederruimten de systemen precies karakteriseren die kunnen worden opgelost door de algoritmen van Clarkson.

Opmerkingen:

Referenties