Problemă de tip LP - LP-type problem

În studiul algoritmilor , o problemă de tip LP (numită și un program liniar generalizat ) este o problemă de optimizare care împărtășește anumite proprietăți cu programe liniare cu dimensiuni reduse și care poate fi rezolvată prin algoritmi similari. Problemele de tip LP includ multe probleme importante de optimizare care nu sunt ele însele programe liniare, cum ar fi problema găsirii celui mai mic cerc care conține un set dat de puncte plane. Ele pot fi rezolvate printr-o combinație de algoritmi randomizați într-un timp care este liniar în numărul de elemente care definesc problema și subexponențial în dimensiunea problemei.

Definiție

Problemele de tip LP au fost definite de Sharir & Welzl (1992) ca probleme în care se dă ca intrare un set finit S de elemente și o funcție f care mapează subseturi de S la valori dintr-un set complet ordonat. Funcția este necesară pentru a satisface două proprietăți cheie:

  • Monotonitate: pentru fiecare două seturi A ⊆ B ⊆ S , f ( A ) ≤ f ( B ) ≤ f ( S ).
  • Localitate: pentru fiecare două seturi A ⊆ B ⊆ S și fiecare element x în S , dacă f ( A ) = f ( B ) = f ( A ∪ { x }) , atunci f ( A ) = f ( B ∪ { x }) .

O bază a unei probleme de tip LP este un set B ⊆ S cu proprietatea că fiecare subset corespunzător al lui B are o valoare mai mică de f decât B în sine, iar dimensiunea (sau dimensiunea combinatorie ) a unei probleme de tip LP este definită ca să fie cardinalitatea maximă a unei baze.

Se presupune că un algoritm de optimizare poate evalua funcția f numai pe seturi care sunt ele însele baze sau care sunt formate prin adăugarea unui singur element la o bază. Alternativ, algoritmul poate fi limitat la două operații primitive: un test de încălcare care determină, pentru o bază B și un element x dacă f ( B ) = f ( B ∪ { x }) și un calcul de bază care (cu același intrări) găsește o bază a lui B ∪ { x }. Sarcina de realizat de algoritm este de a evalua f ( S ) folosind doar aceste evaluări restricționate sau primitive.

Exemple și aplicații

Bile Lp

Un program liniar poate fi definit de un sistem de d variabile reale non-negative , supuse la n constrângeri liniare de inegalitate, împreună cu o funcție obiectiv liniară non-negativă care trebuie minimizată. Acest lucru poate fi plasat în cadrul problemelor de tip LP lăsând S să fie setul de constrângeri și definind f ( A ) (pentru un subset A al constrângerilor) să fie valoarea minimă a funcției obiective a programului liniar mai mic definit de A . Cu ipoteze de poziție generală adecvate (pentru a preveni mai multe puncte de soluție care au aceeași valoare de funcție obiectivă optimă), aceasta satisface cerințele de monotonie și localitate ale unei probleme de tip LP și are dimensiune combinatorie egală cu numărul d de variabile. În mod similar, un program întreg (constând dintr-o colecție de constrângeri liniare și o funcție obiectivă liniară, ca într-un program liniar, dar cu restricția suplimentară că variabilele trebuie să ia numai valori întregi) satisface atât proprietățile monotonicității, cât și localitatea unui LP -problemă de tip, cu aceleași ipoteze de poziție generală ca și pentru programele liniare. Teoremele lui Bell (1977) și Scarf (1977) arată că, pentru un program întreg cu variabile d , dimensiunea combinatorie este de cel mult  2 d .

Multe probleme naturale de optimizare în geometria de calcul sunt de tip LP:

Image
Cea mai mică problemă a cercului
  • Cea mai mică problemă a cercului este problema găsirii razei minime a unui cerc care conține un set dat de n puncte în plan. Acesta satisface monotonitatea (adăugarea mai multor puncte poate face doar cercul mai mare) și localitatea (dacă cel mai mic cerc pentru setul A conține B și x , atunci același cerc conține și B ∪ { x }). Deoarece cel mai mic cerc este întotdeauna determinat de aproximativ trei puncte, problema celui mai mic cerc are dimensiunea combinatorie trei, chiar dacă este definită folosind geometria euclidiană bidimensională. Mai general, cea mai mică bilă de puncte de închidere în dimensiuni d formează o problemă de tip LP de dimensiune combinatorie d + 1 . Cea mai mică problemă a cercului poate fi generalizată la cea mai mică bilă care cuprinde un set de bile, la cea mai mică bilă care atinge sau înconjoară fiecare set de bile, la problema ponderată cu 1 centru sau la probleme similare cu bile mai mici în Spații euclidiene, cum ar fi spațiul cu distanțe definite de divergența lui Bregman . Problema legată de găsirea celui mai mic elipsoid care conține este, de asemenea, o problemă de tip LP, dar cu o dimensiune combinatorie mai mare, d ( d + 3) / 2 .
  • Fie K 0 , K 1 , ... o secvență de n mulțimi convexe în spațiul euclidian d- dimensional și să presupunem că dorim să găsim cel mai lung prefix al acestei secvențe care are un punct de intersecție comun. Aceasta poate fi exprimată ca o problemă de tip LP în care f ( A ) = - i unde K i este primul membru al lui A care nu aparține unui prefix intersectat al lui A și unde f ( A ) = - n dacă există nu este un astfel de membru. Dimensiunea combinatorie a acestui sistem este d + 1 .
  • Să presupunem că ni se oferă o colecție de cutii dreptunghiulare aliniate la axă în spațiu tridimensional și dorim să găsim o linie direcționată în octantul pozitiv al spațiului care taie toate casetele. Aceasta poate fi exprimată ca o problemă de tip LP cu dimensiunea combinatorie 4.
  • Problema găsirii celei mai apropiate distanțe între doi politopi conveși , specificată de seturile lor de vârfuri, poate fi reprezentată ca o problemă de tip LP. În această formulare, mulțimea S este mulțimea tuturor vârfurilor din ambii politopi, iar valoarea funcției f ( A ) este negarea celei mai mici distanțe dintre corpurile convexe ale celor două subseturi A de vârfuri din cei doi politopi. Dimensiunea combinatorie a problemei este d + 1 dacă cei doi politopi sunt disjuni, sau d + 2 dacă au o intersecție neocupată.
  • Fie S = { f 0 , f 1 , ... } un set de funcții cvasiconvexe . Atunci max i f i maxim punctual este el însuși cvasiconvex, iar problema găsirii valorii minime a max i f i este o problemă de tip LP. Are dimensiune combinatorie cel mult 2 d + 1 , unde d este dimensiunea domeniului funcțiilor, dar pentru funcții suficient de netede dimensiunea combinatorie este mai mică, cel mult d + 1 . Multe alte probleme de tip LP pot fi, de asemenea, exprimate folosind funcțiile cvasiconvexe în acest fel; de exemplu, cea mai mică problemă a cercului de închidere este problema minimizării max i f i unde fiecare dintre funcțiile f i măsoară distanța euclidiană de la unul dintre punctele date.

Problemele de tip LP au fost, de asemenea, utilizate pentru a determina rezultatele optime ale anumitor jocuri în teoria algoritmică a jocurilor , pentru a îmbunătăți plasarea vertexului în plasele metodei elementelor finite , pentru a rezolva problemele de localizare a facilității , pentru a analiza complexitatea în timp a anumitor algoritmi de căutare în timp exponențial și pentru a reconstrui pozițiile tridimensionale ale obiectelor din imaginile lor bidimensionale.

Algoritmi

Seidel

Seidel (1991) a oferit un algoritm pentru programarea liniară cu dimensiuni reduse care poate fi adaptat cadrului problematic de tip LP. Algoritmul Seidel ia ca intrare setul S și un set separat X (inițial gol) de elemente despre care se știe că aparțin bazei optime. Apoi ia în considerare elementele rămase unul câte unul într-o ordine aleatorie, efectuând teste de încălcare pentru fiecare și, în funcție de rezultat, efectuând un apel recursiv către același algoritm cu un set mai mare de elemente de bază cunoscute. Poate fi exprimat cu următorul pseudocod: 

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

Într - o problemă cu dimensiune combinatorie d , testul de încălcare în I iterație a algoritmului nu numai atunci când x este una din d - | X | elemente de bază rămase, ceea ce se întâmplă cel mult cu probabilitatea ( d - | X |) / i . Pe baza acestui calcul, se poate demonstra că, în general, numărul așteptat de teste de încălcare efectuate de algoritm este O ( d ! N) , liniar în n, dar mai rău decât exponențial în d .

Clarkson

Clarkson (1995) definește doi algoritmi, un algoritm recursiv și un algoritm iterativ, pentru programare liniară bazată pe tehnici de eșantionare aleatorie, și sugerează o combinație a celor doi care apelează algoritmul iterativ din algoritmul recursiv. Algoritmul recursiv alege în mod repetat eșantioane a căror dimensiune este aproximativ rădăcina pătrată a dimensiunii de intrare, rezolvă recursiv problema eșantionată și apoi folosește teste de încălcare pentru a găsi un subset al elementelor rămase care trebuie să includă cel puțin un element de bază: 

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 fiecare iterație, mărimea așteptată a V este O ( √ n ) , și de fiecare dată când V este nevidă include cel puțin un element nou al eventualului baza S . Prin urmare, algoritmul efectuează cel mult d iterații, fiecare dintre care efectuează n teste de încălcare și efectuează un singur apel recursiv către o subproblemă de dimensiunea O ( d √ n ) .

Algoritmul iterativ al lui Clarkson atribuie greutăți fiecărui element al lui S , inițial toate egale. Apoi alege un set R de 9 d 2 elemente din S la întâmplare și calculează mulțimile B și V ca în algoritmul anterior. Dacă greutatea totală a lui V este de cel mult 2 / (9 d - 1) ori greutatea totală a lui S (așa cum se întâmplă cu probabilitate constantă), atunci algoritmul dublează greutățile fiecărui element al lui V și, ca înainte, repetă acest proces până la V devine gol. În fiecare iterație, se poate demonstra că greutatea bazei optime crește cu o rată mai mare decât greutatea totală a lui S , din care rezultă că algoritmul trebuie să se termine în cadrul iterațiilor O (log n ) .

Prin utilizarea algoritmului recursiv pentru a rezolva o anumită problemă, trecerea la algoritmul iterativ pentru apelurile sale recursive și apoi trecerea din nou la algoritmul Seidel pentru apelurile efectuate de algoritmul iterativ, este posibilă rezolvarea unei probleme de tip LP folosind O ( dn + d ! d O (1) log n ) teste de încălcare.

Atunci când este aplicat unui program liniar, acest algoritm poate fi interpretat ca fiind o metodă dual simplex . Cu anumite primitive de calcul suplimentare, dincolo de testul de încălcare și primitive de calcul de bază, această metodă poate fi făcută deterministă.

Matoušek, Sharir și Welzl

Matoušek, Sharir & Welzl (1996) descriu un algoritm care folosește o proprietate suplimentară a programelor liniare care nu este întotdeauna deținută de alte probleme de tip LP, că toate bazele au aceeași cardinalitate una de alta. Dacă o problemă de tip LP nu are această proprietate, se poate face să o aibă adăugând d elemente fictive noi și modificând funcția f pentru a returna perechea ordonată a vechii sale valori f ( A ) și a numărului min ( d , | A |) , ordonat lexicografic .

În loc să adauge elemente de S unul câte unul sau să găsească mostre ale elementelor, Matoušek, Sharir & Welzl (1996) descriu un algoritm care elimină elementele pe rând. La fiecare pas, menține o bază C care poate fi inițial ansamblul de elemente fictive. Poate fi descris cu următorul pseudocod: 

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

În majoritatea apelurilor recursive ale algoritmului, testul de încălcare reușește și instrucțiunea if este omisă. Cu toate acestea, cu o probabilitate mică, testul de încălcare eșuează, iar algoritmul face o bază de calcul suplimentară și apoi un apel recursiv suplimentar. După cum arată autorii, timpul așteptat pentru algoritm este liniar în n și exponențial în rădăcina pătrată a d log n . Prin combinarea acestei metode cu procedurile recursive și iterative ale lui Clarkson, aceste două forme de dependență de timp pot fi separate una de cealaltă, rezultând un algoritm care efectuează teste de încălcare O ( dn ) în algoritmul recursiv exterior și un număr care este exponențial în rădăcină pătrată a d log d în nivelurile inferioare ale algoritmului.

Variații

Optimizare cu valori aberante

Matoušek (1995) consideră o variație a problemelor de optimizare de tip LP în care se dă, împreună cu mulțimea S și funcția obiectivă f , un număr k ; sarcina este de a elimina k elemente din S pentru a face funcția obiectivă pe setul rămas cât mai mică posibil. De exemplu, atunci când este aplicat la cea mai mică problemă de cerc, aceasta ar da cel mai mic cerc care conține toate, cu excepția k dintr-un set dat de puncte plane. El arată că, pentru toate problemele de tip LP nedegenerate (adică problemele în care toate bazele au valori distincte) această problemă poate fi rezolvată în timp O ( nk d ) , prin rezolvarea unui set de O ( k d ) LP -de tip probleme definite de subseturi de S .

Probleme implicite

Unele probleme de optimizare geometrică pot fi exprimate ca probleme de tip LP în care numărul de elemente din formularea de tip LP este semnificativ mai mare decât numărul de valori de date de intrare pentru problema de optimizare. De exemplu, luați în considerare o colecție de n puncte în plan, fiecare mișcându-se cu viteză constantă. În orice moment, diametrul acestui sistem este distanța maximă dintre două dintre punctele sale. Problema găsirii unui timp la care diametrul este minimizat poate fi formulată ca minimizarea punctuală maximă a funcțiilor O ( n 2 ) cvasiconvexe, câte una pentru fiecare pereche de puncte, măsurând distanța euclidiană între pereche în funcție de timp. Astfel, poate fi rezolvată ca o problemă de tip LP de dimensiune combinatorie două pe un set de elemente O ( n 2 ) , dar acest set este semnificativ mai mare decât numărul de puncte de intrare.

Chan (2004) descrie un algoritm pentru rezolvarea problemelor de tip LP definite implicit, cum ar fi acesta, în care fiecare element de tip LP este determinat de un k -tuple de valori de intrare, pentru o constantă k . Pentru a aplica abordarea sa, trebuie să existe un algoritm de decizie , care poate determina, pentru un anumit tip LP bază B și un set S de n valori de intrare, dacă B este o bază pentru problema de tip LP determinat de S .

Algoritmul lui Chan efectuează următorii pași:

  • Dacă numărul de valori de intrare este sub o anumită valoare prag, găsiți setul de elemente de tip LP pe care le determină și rezolvați problema explicită de tip LP rezultată.
  • În caz contrar, partiționați valorile de intrare într-un număr adecvat mai mare decât k de subseturi de dimensiuni egale S i .
  • Dacă f este funcția obiectivă pentru problema de tip LP definită implicit care trebuie rezolvată, atunci definiți o funcție g care mapează colecțiile de subseturi S i la valoarea lui f pe uniunea colecției. Apoi, colecția subseturilor S i și funcția obiectivă g definește o problemă de tip LP, de aceeași dimensiune ca și problema implicită de rezolvat.
  • Rezolvați problema (explicită) de tip LP definită de g folosind algoritmul lui Clarkson, care efectuează un număr liniar de teste de încălcare și un număr polilogaritmic de evaluări de bază. Evaluările de bază pentru g pot fi efectuate prin apeluri recursive către algoritmul lui Chan, iar testele de încălcare pot fi efectuate prin apeluri către algoritmul de decizie.

Presupunând că algoritmul de decizie durează o perioadă de timp O ( T ( n )) care crește cel puțin polinomial în funcție de dimensiunea de intrare n , Chan arată că pragul pentru trecerea la o formulare LP explicită și numărul de subseturi în partiție poate fi ales în așa fel încât algoritmul de optimizare implicit de tip LP să ruleze și în timpul O ( T ( n )) .

De exemplu, pentru diametrul minim al punctelor în mișcare, algoritmul de decizie trebuie doar să calculeze diametrul unui set de puncte la un moment fix, o problemă care poate fi rezolvată în timp O ( n log n ) folosind tehnica etrierelor rotative . Prin urmare, algoritmul lui Chan pentru găsirea timpului la care diametrul este minimizat necesită și timp O ( n log n ) . Chan folosește această metodă pentru a găsi un punct de adâncime maximă Tukey dintr-o colecție dată de n puncte în spațiul euclidian d- dimensional, în timpul O ( n d - 1 + n log n ) . O tehnică similară a fost utilizată de Braß, Heinrich-Litan și Morin (2003) pentru a găsi un punct de adâncime maximă Tukey pentru distribuția uniformă pe un poligon convex.

Istorie și probleme conexe

Descoperirea algoritmilor de timp liniar pentru programarea liniară și observarea că aceiași algoritmi ar putea fi folosiți în multe cazuri pentru a rezolva probleme de optimizare geometrică care nu erau programe liniare se întoarce cel puțin la Megiddo ( 1983 , 1984 ), care a dat un timp liniar așteptat algoritm pentru ambele programe liniare cu trei variabile și pentru cea mai mică problemă a cercului. Cu toate acestea, Megiddo a formulat generalizarea programării liniare mai degrabă din punct de vedere geometric decât combinator, ca o problemă de optimizare convexă, mai degrabă decât ca o problemă abstractă pe sisteme de seturi. În mod similar, Dyer (1986) și Clarkson (în versiunea de conferință din 1988 a lui Clarkson 1995 ) au observat că metodele lor ar putea fi aplicate atât programelor convexe, cât și programelor liniare. Dyer (1992) a arătat că problema minimă a elipsoidului de închidere ar putea fi formulată și ca o problemă de optimizare convexă prin adăugarea unui număr mic de constrângeri neliniare. Utilizarea randomizării pentru a îmbunătăți limitele de timp pentru programarea liniară dimensională mică și problemele conexe a fost inițiată de Clarkson și de Dyer & Frieze (1989) .

Definiția problemelor de tip LP în ceea ce privește funcțiile care satisfac axiomele localității și monotoniei provine din Sharir & Welzl (1992) , dar alți autori din același interval de timp au formulat generalizări combinatorii alternative ale programelor liniare. De exemplu, într - un cadru dezvoltat de Gärtner (1995) , funcția f este înlocuită cu o ordonare totala pe subseturi de S . Este posibil să rupem legăturile într-o problemă de tip LP pentru a crea o ordine totală, dar numai în detrimentul unei creșteri a dimensiunii combinatorii. În plus, la fel ca în problemele de tip LP, Gärtner definește anumite primitive pentru efectuarea calculelor pe subseturi de elemente; cu toate acestea, formalizarea sa nu are un analog al dimensiunii combinatorii.

O altă generalizare abstractă atât a programelor liniare, cât și a problemelor de complementaritate liniară , formulată de Stickney & Watson (1978) și ulterior studiată de alți autori, se referă la orientările marginilor unui hipercub cu proprietatea că fiecare față a hipercubului (inclusiv întregul hipercub ca față) are o chiuvetă unică , un vârf fără margini de ieșire. O orientare de acest tip poate fi formată dintr-o problemă de tip LP prin corespondența subseturilor lui S cu vârfurile unui hipercub în așa fel încât două subseturi diferă de un singur element dacă și numai dacă vârfurile corespunzătoare sunt adiacente și de orientând marginea dintre mulțimile vecine A ⊆ B spre B dacă f ( A ) ≠ f ( B ) și spre A în caz contrar. Orientarea rezultată are proprietatea suplimentară că formează un grafic aciclic direcționat , din care se poate arăta că un algoritm randomizat poate găsi chiuveta unică a întregului hipercub (baza optimă a problemei de tip LP) în mai mulți pași exponențială în rădăcina pătrată a lui  n .

Cadrul mai recent dezvoltat al spațiilor violatorilor generalizează problemele de tip LP, în sensul că fiecare problemă de tip LP poate fi modelată de un spațiu de violator, dar nu neapărat invers. Spațiile violatorului sunt definite în mod similar cu problemele de tip LP, printr-o funcție f care mapează seturile la valorile obiective ale funcției, dar valorile lui f nu sunt ordonate. În ciuda lipsei de ordonare, fiecare set S are un set de baze bine definit (seturile minime cu aceeași valoare ca întregul set) care pot fi găsite prin variații ale algoritmilor lui Clarkson pentru probleme de tip LP. Într-adevăr, s-a demonstrat că spațiile violatorilor caracterizează exact sistemele care pot fi rezolvate de algoritmii lui Clarkson.

Note

Referințe