Kwadratowy problem plecakowy

Kwadratowy problem plecakowy (QKP) , wprowadzony po raz pierwszy w XIX wieku, jest rozszerzeniem problemu plecakowego , które pozwala na wyrażenie kwadratowe w funkcji celu: Biorąc pod uwagę zbiór przedmiotów, każdy o wadze, wartości i dodatkowym zysku, który może jakie można zarobić w przypadku wybrania dwóch pozycji, należy określić liczbę pozycji, które mają znaleźć się w kolekcji, nie przekraczającą pojemności plecaka , tak aby zmaksymalizować ogólny zysk. Zwykle kwadratowe problemy plecakowe wiążą się z ograniczeniem liczby kopii każdego rodzaju przedmiotu: 0 lub 1. Ten specjalny typ QKP tworzy Kwadratowy problem plecakowy 0-1 , po raz pierwszy omówiony przez Gallo i in. Problem plecakowy kwadratowy 0-1 jest odmianą problemów plecakowych, łączącą cechy problemu plecakowego nieograniczonego, problemu plecakowego 0-1 i problemu plecakowego kwadratowego.

Definicja

W szczególności kwadratowy problem plecakowy 0–1 ma następującą postać:

${\ Displaystyle {\ tekst {maksymalizacja}} \ lewo \ {\ suma _ {i = 1} ^ {n} p_ {i} x_ {i} + \ suma _ {i = 1} ^ {n} \ suma _ {j=1,i\neq j}^{n}P_{ij}x_{i}x_{j}:x\in X,x{\text{binary}}\right\}} z$

${\ Displaystyle {\ tekst {podlega}} X \ równoważnik \ lewo \ {x \ in \ {0,1 \} ^ {n}: \ suma _ {i = 1} ^ {n} w_ {i} x_ {i}\leq W;x_{i}\in \{0,1\}{\text{ for }}i=1,\ldots ,n\right\}.}$

$a$ binarna x _i reprezentuje, czy przedmiot $. jeśli$ się w plecaku, to zysk uzyskany poprzez wybranie przedmiotu , to osiągnięty dodane zostaną zarówno pozycje i, jak i j .

Nieformalnie problem polega na maksymalizacji sumy wartości przedmiotów w plecaku, tak aby suma wag była mniejsza lub równa pojemności plecaka.

Aplikacja

Jak można się spodziewać, QKP ma szeroki zakres zastosowań, w tym telekomunikację , sieć transportową , informatykę i ekonomię . W rzeczywistości Witzgall po raz pierwszy omówił QKP przy wyborze lokalizacji stacji satelitarnych w celu maksymalizacji globalnego ruchu przy uwzględnieniu ograniczeń budżetowych. Podobny model dotyczy problemów takich jak uwzględnianie lokalizacji lotnisk, stacji kolejowych czy terminali przeładunkowych. Zastosowania QKP w dziedzinie informatyki są bardziej powszechne po początkach: problem z projektowaniem kompilatora , problem kliki , projektowanie integracji na bardzo dużą skalę (VLSI). Ponadto problemy cenowe wydają się wynikać ze stosowania QKP, jak opisali Johnson i in.

Złożoność obliczeniowa

Ogólnie rzecz biorąc, wersja decyzyjna problemu plecakowego (Czy przy ograniczeniu określonej pojemności W można osiągnąć wartość co najmniej V?) jest NP-zupełna . Zatem dane rozwiązanie można zweryfikować w czasie wielomianowym, podczas gdy żaden algorytm nie jest w stanie skutecznie zidentyfikować rozwiązania.

Optymalizacja problemu plecakowego jest NP-trudna i nie ma znanego algorytmu, który mógłby rozwiązać ten problem w czasie wielomianowym.

Jako szczególna odmiana problemu plecakowego, kwadratowy problem plecakowy 0-1 jest również NP-trudny.

Chociaż w literaturze nie istnieje żaden skuteczny algorytm, istnieje czas pseudowielomianowy oparty na programowaniu dynamicznym i innych algorytmach heurystycznych , które zawsze mogą generować „dobre” rozwiązania.

Rozwiązywanie

Chociaż problem plecakowy jest jednym z najczęściej rozwiązywanych problemów z zakresu badań operacyjnych (OR), istnieją ograniczone wydajne algorytmy, które mogą rozwiązać kwadratowe problemy plecakowe 0-1. Dostępne algorytmy obejmują między innymi brutalną siłę , linearyzację i przeformułowanie wypukłe. Podobnie jak w przypadku innych problemów NP-trudnych, zwykle wystarczy znaleźć wykonalne rozwiązanie, nawet jeśli niekoniecznie jest ono optymalne. Algorytmy heurystyczne oparte na algorytmie zachłannym , programowanie dynamiczne mogą skutecznie dać stosunkowo „dobre” rozwiązanie 0-1 QKP.

Brutalna siła

Algorytm brutalnej siły rozwiązujący ten problem polega na zidentyfikowaniu wszystkich możliwych podzbiorów elementów bez przekraczania pojemności i wybraniu tego o optymalnej wartości. Pseudokod jest dostarczany w następujący sposób:

   0
    
        0
       0   
             // Dane wejściowe:  // Zyski (zapisane w tablicy p)  // Zyski kwadratowe (zapisane w macierzy P)  // Masy (zapisane w tablicy w)  // Liczba sztuk (n)  // Pojemność plecaka (W)  int  max  =  dla  wszystkich  podzbiorów  S  wykonaj  wartość  int  ,  waga  =  dla  i  od  do  S  .  rozmiar  -1  do  :  wartość  =  wartość  +  p  [  i  ] 
            
                   
                    
        
                
               waga  =  waga  +  w  [  ja  ]  dla  j  od  i  +  1  do  S  .  rozmiar  -1  do  :  wartość  =  wartość  +  P  [  i  ][  j  ]  jeśli  waga  <=  W  to  :  jeśli  wartość  >  max  wtedy  :  max  =  wartość 

Biorąc pod uwagę n elementów, będzie co najwyżej $)$ i dla każdego zbioru prawnego kandydata czas obliczania uzyskanych wartości wynosi $\ displaystyle O (n ^$ . Zatem klasa wydajności algorytmu brutalnej siły wynosi ${\ Displaystyle (2 ^ {n} n ^ {2}) = \ lambda (2 ^ {n})$ } jest wykładniczy.

Linearyzacja

Problemy w takiej postaci są trudne do bezpośredniego rozwiązania przy użyciu standardowych solwerów, dlatego ludzie próbują przeformułować je na program liniowy , korzystając ze zmiennych pomocniczych i ograniczeń, tak aby problem można było łatwo rozwiązać za pomocą komercyjnych pakietów. Dwa dobrze znane do linearyzacji dla QKP 0-1 to linearyzacja standardowa i linearyzacja Glovera.

Linearyzacja standardowa

Pierwsza to standardowa strategia linearyzacji, jak pokazano poniżej:

LP1: maksymalizuj

${\ Displaystyle \ suma _ {i = 1} ^ {n} p_ {i} x_ {i} + \ suma _ {i = 1} ^ {n} \ lewo (\ suma _ {j = 1, i <j }^{n}(P_{ij}+P_{ji})z_{ij}\right).}$

z zastrzeżeniem

${\ Displaystyle z_ {ij} \ równoważnik x_ {i}}$ dla wszystkich ${\ Displaystyle (i, j), i <j}$

${ \ Displaystyle z_ {ij} \ równoważnik x_ {j}}$ dla wszystkich ${\ Displaystyle (i, j), i <j}$

${\ Displaystyle x_ {i} + x_ {j} -1 \ równoważnik z_ {ij}}$ dla wszystkich ${\ Displaystyle (i, j), i <j}$

${\ Displaystyle z_ {ij} \ geq 0}$ dla wszystkich ${\ Displaystyle (i, j), i <j}$

${\ Displaystyle x \ w X, x}$ binarny

sformułowaniu xi _{x j} LP1 zastąpiliśmy wyraz zmienną ciągłą z _ij . To przeformułowuje QKP w problem plecakowy, który możemy następnie optymalnie rozwiązać za pomocą standardowych rozwiązań.

Linearyzacja Glovera

Drugie przeformułowanie, które jest bardziej zwięzłe, nazywa się linearyzacją Glovera. Poniżej pokazano sformułowanie Glovera, gdzie L _ja i U _ja to dolna i górna granica ${n}P_{ij}x_{j}} :$${\ displaystyle \ suma _ {j = 1, i \ neq j} ^$ odpowiednio

LP2: maksymalizować

${\ Displaystyle \ suma _ {i = 1} ^ {n} p_ {i} x_ {i} + \ suma _ {i = 1} ^ {n} z_ {i}}$

z zastrzeżeniem

${\ Displaystyle L_ {i} x_ {i} \ równoważnik z_ {i} \ równoważnik U_ {i} x_ { i}}$ dla ${\ Displaystyle ja = 1, \ ldots, n}$

${\ Displaystyle \ suma _ {j = 1, i \ neq jot} ^ {n} P_ {ij} x_ {j} -U_ {i} (1-x_ {i}) \ równoważnik z_ {i} \ równoważnik \ suma _ {j = 1, i \ neq j} ^ {n} P_ {ij} x_ {j} -L_ {i} (1-x_ {i})} dla ja =$ 1 $ja = 1, \ ldots, n}$

${\ Displaystyle x \ w X, x}$ binarny

W formule LP2 zastąpiliśmy wyrażenie ${\ displaystyle \ suma _ {j = 1, i \ neq j} ^ {n} P_ {ij} x_{i}x_{j}}$ ze zmienną ciągłą z _i . Podobnie możemy użyć standardowych solwerów do rozwiązania zlinearyzowanego problemu. $2n}$ Glovera obejmuje tylko zmienne pomocnicze z $displaystyle$$,$$podczas$ wymaga pomocniczych i ograniczeń osiągnąć

Przeformułowanie wypukłe kwadratowe

Należy pamiętać, że programy nieliniowe są trudne do rozwiązania ze względu na możliwość utknięcia na lokalnym maksimum . Jednakże, gdy program jest wypukły , każde maksimum lokalne jest maksimum globalnym . Program wypukły polega na maksymalizacji funkcji wklęsłej lub minimalizacji funkcji wypukłej na zbiorze wypukłym . Zbiór S jest wypukły, jeśli $v \ in S}$ , ${\ Displaystyle \ lambda u + (1- \ lambda) v \ w S}$ gdzie ${\ Displaystyle \ lambda \ in [0,1]}$ . Oznacza to, że dowolny punkt pomiędzy dwoma punktami w zbiorze musi być również elementem zbioru. Funkcja f jest wklęsła, jeśli ${\ Displaystyle f [\ lambda u + (1- \ lambda) v] \ równoważnik \ lambda f (u) + (1- \ lambda) f (v)}$ . Funkcja f jest wypukła, jeśli ${\ Displaystyle f [\ lambda u + (1- \ lambda) v] \geq \lambda f(u)+(1-\lambda )f(v)}$ . Nieformalnie funkcja jest wklęsła, jeśli odcinek łączący dwa punkty na wykresie leży powyżej lub na wykresie, natomiast funkcja jest wypukła, jeśli znajduje się poniżej lub na wykresie. Zatem przepisując funkcję celu na równoważną funkcję wypukłą, możemy przeformułować program na wypukły, co można rozwiązać za pomocą pakietów optymalizacyjnych.

Funkcję celu można zapisać jako przy użyciu notacji algebry liniowej do $Cx} .$ Musimy uczynić P dodatnią macierzą półokreśloną, aby przeformułować funkcję wypukłą. W tym przypadku modyfikujemy funkcję celu na ${\ Displaystyle p ^ {T} x + x ^ {T} Px + \ suma _ {i = 1} ^ {n} \ lewo (\ suma _ {j = 1, j \ neq i}^{n}|P_{ij}|\right)(x_{i}^{2}-x_{i})}$ poprzez zastosowanie wyników algebry liniowej, gdzie P jest macierzą dominującą po przekątnej , a zatem dodatnią półokreślony. To przeformułowanie można rozwiązać przy użyciu standardowego komercyjnego pakietu kwadratowego z liczbami mieszanymi.

Chciwy algorytm heurystyczny

George Dantzig zaproponował algorytm zachłannej aproksymacji problemu nieograniczonego plecaka, który można również zastosować do rozwiązania problemu QKP 0-1. Algorytm składa się z dwóch fraz: zidentyfikować rozwiązanie wyjściowe i ulepszyć je.

$jaki$ wybierając i posortuj elementy w kolejności malejącej potencjalnej wartości na jednostkę masy ${\ displaystyle (p_ {i} + \ suma _ {i \ neq j}^{n}P_{ij})/w_{i}}$ . Następnie wrzucaj do plecaka przedmioty o maksymalnym stosunku wartości do wagi, aż zabraknie miejsca na więcej, co stanowi rozwiązanie początkowe. Począwszy od rozwiązania początkowego, doskonalenie odbywa się poprzez wymianę parami. Dla każdej pozycji w zestawie rozwiązań zidentyfikuj elementy, które nie znajdują się w zestawie, w przypadku których zamiana skutkuje poprawą celu. Wybierz parę z maksymalną poprawą i zamień. Istnieje również możliwość, że usunięcie jednego z zestawu lub dodanie go do zestawu przyniesie największy wkład. Powtarzaj, aż nie będzie poprawy podczas wymiany. Klasa złożoności tego algorytmu to ${\ displaystyle O (2 ^ {n})},$ ponieważ w najgorszym przypadku zostanie zidentyfikowana każda możliwa kombinacja elementów.

Quadknap

Quadknap to dokładny algorytm rozgałęziony zaproponowany przez Caprarę i in., w którym górne granice są obliczane poprzez uwzględnienie relaksacji Lagrangianu , która przybliża trudny problem za pomocą prostszego problemu i karze naruszenia ograniczeń za pomocą mnożnika Lagrange'a w celu nałożenia kosztu na naruszenia . Quadknap zwalnia wymóg dotyczący liczby całkowitej podczas obliczania górnych granic. Suboptymalne mnożniki Lagrangianu pochodzą z optymalizacji podgradientowej i zapewniają wygodne przeformułowanie problemu. Algorytm ten jest dość wydajny, ponieważ mnożniki Lagrangianu są stabilne i przyjęto odpowiednie struktury danych w celu obliczenia ścisłej górnej granicy liniowego oczekiwanego czasu liczby zmiennych. Zgłoszono, że algorytm ten generuje dokładne rozwiązania instancji z maksymalnie 400 zmienne binarne , tj. znacznie większe niż te, które można rozwiązać innymi podejściami. Kod został napisany w języku C i jest dostępny online.

Heurystyka programowania dynamicznego

Podczas gdy programowanie dynamiczne może generować optymalne rozwiązania problemów plecakowych, podejścia do programowania dynamicznego dla QKP mogą dać jedynie rozwiązanie stosunkowo dobrej jakości, które może służyć jako dolna granica optymalnych celów. Chociaż działa w czasie pseudowielomianowym, ma duże wymagania dotyczące pamięci.

Algorytm programowania dynamicznego

Dla uproszczenia załóżmy, że wszystkie wagi są nieujemne. Celem jest maksymalizacja całkowitej wartości z zastrzeżeniem ograniczenia: całkowita waga jest mniejsza lub równa W. Następnie dla każdego zdefiniuj wartość najbardziej opłacalnego pakowania pierwszych m znalezionych elementów w sumie $w$$W$ waga w . To znaczy, niech

${\ Displaystyle f (m, w) = \ max \ lewo \ {\ suma _ {i = 1} ^ {m} p_ {i} x_ {i} + \ suma _ {i = 1} ^ {m} \ suma _{j=1,i\neq j}^{m}P_{ij}x_{i}x_{j}:\sum _{i=1}^{m}w_{i}=w,1\ leq i\leq m\right\}.}$

Następnie jest rozwiązaniem problemu. ${\ displaystyle f (m, w)} .$ Należy pamiętać, że w programowaniu dynamicznym rozwiązanie problemu wynika z rozwiązania jego mniejszych podproblemów. W tym konkretnym przypadku zacznij od pierwszego przedmiotu i spróbuj znaleźć lepsze opakowanie, rozważając dodanie przedmiotów o oczekiwanej wadze 𝑤. Jeśli waga dodawanego przedmiotu przekracza 𝑤 , to jest taka sama z $, w)}$${\ Displaystyle f (m-1, w)}$ . Biorąc $) {\$$f (m- 1,w)}$ że przedmiot ma mniejszą wagę w porównaniu z pożądaną wagą, jak jeśli dodawanie nie wnosi żadnego wkładu, lub tak samo jak rozwiązanie dla plecaka o mniejszej pojemności, a konkretnie o pojemności pomniejszonej o wagę wybranego przedmiotu plus wartość jednego prawidłowego przedmiotu, czyli ${\ Displaystyle f (m-1, w-w_ {m}) + p_ {m} + \ suma _ {i = 1} ^ {m-1}P_{im}x_{i}}$ . Podsumowując, mamy to

${\ Displaystyle f (m, w) = {\ początek {przypadków} \ max f (m-1, w), f (m-1, ww_ {m}) + p_ {m }+\sum _{i=1}^{m-1}P_{im}x_{i}&{\text{if }}w_{m}\leq w\\f(m-1,w)& {\text{w przeciwnym razie}}\end{przypadki}}}$

$zagnieżdżoną pętlę i$ dotycząca klasy efektywności: Oczywiście czas działania tego algorytmu wynosi zysku z nowego Nie przeczy to faktowi, że QKP jest NP-trudny, ponieważ W nie jest wielomianem długości sygnału wejściowego.

Zmieniony algorytm programowania dynamicznego

Należy zauważyć, że poprzedni algorytm wymaga miejsca na przechowywanie bieżącego pakowania elementów dla wszystkich $m$ w , nie być w stanie obsłużyć problemów o $,$ usuwając indeks m z ponieważ wszystkie obliczenia zależą tylko od

Zdefiniuj na nowo ${\ displaystyle f (w)}$ na bieżącą wartość najbardziej dochodowego pakowania znalezioną przez heurystykę. To jest,

${\ Displaystyle f (w) = \ max \ lewo \ {\ suma _ {i = 1} ^ {m} p_ {i} x_ {i} + \ suma _ {i = 1} ^ {m} \ suma _ {j=1,i\neq j}^{m}P_{ij}x_{i}x_{j}:\sum _{i=1}^{m}w_{i}=w,m\leq n \Prawidłowy\}.}$

Odpowiednio, dzięki programowaniu dynamicznemu mamy to

${\ Displaystyle f (m) = {\ początek {przypadków} \ max f (w), f (ww_ {m}) + p_ {m} + \ suma _ {i = 1} ^ {m-1} P_{im}x_{i}&{\text{if }}w_{m}\leq w,\\f(w)&{\text{w przeciwnym razie.}}\end{cases}}}$

$O (Wn$ nadal działa w pamięci ${\ Displaystyle O (Wn ^ {2})}$$^ {2} )}$ pamięć porównaniu z poprzednim .

Powiązane tematy badawcze

Naukowcy od dziesięcioleci badają kwadratowe problemy plecakowe 0-1. Jednym z celów jest znalezienie skutecznych algorytmów lub skutecznych heurystyk, szczególnie tych o wyjątkowej wydajności, rozwiązujących problemy w świecie rzeczywistym. Podczas pracy z którąkolwiek z nich nie należy ignorować związku pomiędzy wersją decyzyjną a wersją optymalizacyjną QKP 0-1. Z jednej strony, jeśli problem decyzyjny można rozwiązać w czasie wielomianowym, wówczas można znaleźć optymalne rozwiązanie, stosując ten algorytm iteracyjnie. Z drugiej strony, jeśli istnieje algorytm, który może rozwiązać problem optymalizacji skutecznie, wówczas można go wykorzystać do rozwiązania problemu decyzyjnego poprzez porównanie danych wejściowych z wartością optymalną.

Innym tematem w literaturze jest identyfikacja problemów „trudnych”. Naukowcy badający QKP 0-1 często przeprowadzają badania obliczeniowe, aby wykazać wyższość swoich strategii. Badania takie można również przeprowadzić w celu oceny wydajności różnych metod rozwiązywania problemów. W przypadku QKP 0-1 te badania obliczeniowe często opierają się na losowo generowanych danych, wprowadzonych przez Gallo i in. Zasadniczo każde badanie obliczeniowe QKP 0-1 wykorzystuje dane generowane losowo w następujący sposób. Wagi są liczbami całkowitymi pochodzącymi z rozkładu jednostajnego w przedziale [1, 50], a ograniczenia wydajności są liczbą całkowitą wziętą z równomiernego rozkładu pomiędzy 50 a sumą wag pozycji. Współczynniki obiektywne, czyli wartości wybierane są losowo spośród [1100]. Zaobserwowano, że generowanie instancji tej postaci daje problemy o bardzo zmiennym i nieprzewidywalnym stopniu trudności. Dlatego też prezentowane w literaturze badania obliczeniowe mogą być błędne. Dlatego niektóre badania mają na celu opracowanie metodologii generowania instancji QKP 0-1 o przewidywalnym i stałym poziomie trudności.

Zobacz też

• Problem z plecakiem
• Aukcja kombinatoryczna
• Optymalizacja kombinatoryczna
• Ciągły problem z plecakiem
• Lista problemów plecakowych
• Problem z pakowaniem

Linki zewnętrzne

• Kody Davida Pisingera dla różnych problemów plecakowych
• Kody kwadratowego problemu plecakowego