Lista problemów plecakowych

Problem plecakowy jest jednym z najczęściej badanych problemów optymalizacji kombinatorycznej i ma wiele zastosowań w życiu codziennym. Z tego powodu zbadano wiele przypadków szczególnych i uogólnień.

p dla wszystkich wersji zestaw n elementów, z których każdy w ma zysk i . Binarna zmienna decyzyjna x j służy do wyboru pozycji. Celem jest zebranie kilku przedmiotów z maksymalnym całkowitym zyskiem, przy czym maksymalna łączna waga wybranych przedmiotów nie może przekroczyć W . Ogólnie rzecz biorąc, współczynniki te są skalowane do liczb całkowitych i prawie zawsze przyjmuje się, że są dodatnie.

Problem plecakowy w najbardziej podstawowej postaci:

maksymalizować
z zastrzeżeniem

Bezpośrednie uogólnienia

Jednym z powszechnych wariantów jest to, że każdy element można wybrać wiele razy. Ograniczony problem plecakowy określa dla każdego elementu j górną granicę u j (która może być dodatnią liczbą całkowitą lub nieskończonością) liczby przypadków wybrania elementu j :

maksymalizować
z zastrzeżeniem
całka dla wszystkich j

Nieograniczony problem plecakowy (czasami nazywany całkowitym problemem plecakowym ) nie nakłada żadnych górnych ograniczeń na liczbę przypadków, w których element może zostać wybrany:

maksymalizować
z zastrzeżeniem
całka dla wszystkich j

Nieograniczony wariant okazał się NP-zupełny w 1975 roku przez Luekera. Zarówno ograniczone, jak i nieograniczone warianty dopuszczają FPTAS (zasadniczo taki sam jak ten używany w problemie plecakowym 0-1).

Jeśli przedmioty są podzielone na k klas oznaczonych iz każdej klasy należy pobrać dokładnie przedmiot, otrzymujemy problem plecakowy wielokrotnego wyboru : N ja }

maksymalizować
z zastrzeżeniem
dla wszystkich
dla wszystkich jot

Jeśli dla każdej pozycji zysk i waga są równe, otrzymujemy problem sumy podzbioru (często zamiast tego podaje się odpowiedni problem decyzyjny ):

maksymalizować
z zastrzeżeniem

Jeśli mamy n przedmiotów i m plecaków o pojemnościach , otrzymujemy problem wielu plecaków :

maksymalizować
z zastrzeżeniem dla wszystkich
dla wszystkich
dla wszystkich i wszystkie

Jako szczególny przypadek problemu wielu plecaków, gdy zyski są równe ciężarom, a wszystkie pojemniki mają taką samą pojemność, możemy mieć problem sum wielu podzbiorów .

Kwadratowy problem plecakowy :

maksymalizować
z zastrzeżeniem
dla wszystkich

Problem plecakowy Set-Union :

SUKP jest zdefiniowany przez Kellerera i wsp. (na stronie 423) w następujący sposób:

zestaw elementów } zestaw , każdy element podzbiorowi jot zestawu elementów . . Pozycje mają nieujemne zyski \ , a elementy mają nieujemne wagi , . Całkowita waga zestawu elementów jest określona przez całkowitą wagę elementów połączenia odpowiednich zestawów elementów. Celem jest znalezienie podzbioru przedmiotów o łącznej masie nieprzekraczającej pojemności plecaka i maksymalnego zysku.

Wiele ograniczeń

Jeśli istnieje więcej niż jedno ograniczenie (na przykład zarówno limit objętości, jak i limit wagi, gdzie objętość i waga każdego przedmiotu nie są powiązane), otrzymujemy problem plecakowy z wieloma ograniczeniami , wielowymiarowy problem plecakowy lub m - wymiarowy problem z plecakiem . (Uwaga: „wymiar” nie odnosi się tutaj do kształtu żadnych przedmiotów). Ma to warianty 0-1, ograniczone i nieograniczone; nieograniczony pokazano poniżej.

maksymalizować
z zastrzeżeniem dla wszystkich
, liczba całkowita dla wszystkich

że wariant 0-1 (dla dowolnego ustalonego jest NP-zupełny około 1980 I silniej, nie ma FPTAS, chyba że P = NP

Warianty ograniczone i nieograniczone (dla dowolnego ustalonego wykazują tę samą

Dla każdego ustalonego dopuszczają algorytm pseudowielomianowego podobny do tego dla podstawowego plecaka) i PTAS .

Problemy jak z plecakiem

Jeśli wszystkie zyski wynoszą 1, spróbujemy zmaksymalizować liczbę przedmiotów, która nie przekroczy pojemności plecaka:

maksymalizować
z zastrzeżeniem

Jeśli mamy kilka pojemników (o tym samym rozmiarze) i chcemy zapakować wszystkie n przedmiotów do jak najmniejszej liczby pojemników, otrzymujemy problem pakowania w pojemniki , który jest modelowany przez zmienne wskaźnikowe używany jest kontener i :

minimalizować
z zastrzeżeniem

Problem z rozbiorem jest identyczny z problemem z pakowaniem do pojemników , ale ponieważ praktyczne przypadki obejmują zwykle znacznie mniej rodzajów przedmiotów, często stosuje się inne sformułowanie. Przedmiot j jest potrzebny B j razy, każdy „wzór” przedmiotów mieszczących się w jednym plecaku ma zmienną x i (jest m wzorców), a wzór i wykorzystuje przedmiot j b ij razy:

zminimalizować
z zastrzeżeniem dla wszystkich
dla wszystkich

Jeśli do problemu plecakowego wielokrotnego wyboru dodamy ograniczenie, że każdy podzbiór ma rozmiar n i usuniemy ograniczenie dotyczące całkowitej wagi, otrzymamy problem przypisania , który jest również problemem znalezienia maksymalnego dopasowania dwudzielnego :

maksymalizować
z zastrzeżeniem dla wszystkich
dla wszystkich
dla wszystkich jot

W wariancie plecakowym o maksymalnej gęstości istnieje waga początkowa i maksymalizujemy gęstość wybranych przedmiotów, które nie naruszają ograniczenia pojemności: w

maksymalizować
z zastrzeżeniem

Chociaż mniej powszechne niż powyższe, istnieje kilka innych problemów podobnych do plecaka, w tym:

  • Zagnieżdżony problem plecakowy
  • Problem z zapadającym się plecakiem
  • Nieliniowy problem plecakowy
  • Odwrotnie parametryczny problem plecakowy

Ostatnie trzy z nich omówiono w pracy referencyjnej Kellerera i wsp. Problemy plecakowe .

  1. ^   Martello, Silvano i Toth, Paolo (1990). Problemy plecakowe: algorytmy i implementacje komputerowe . John Wiley & Synowie . ISBN 978-0471924203 . {{ cite book }} : CS1 maint: wiele nazwisk: lista autorów ( link )
  2. ^ a b c d   Kellerer, Hans i Pferschy, Ulrich i Pisinger, David (2004). Problemy z plecakiem . Springer Verlag . ISBN 978-3-540-40286-2 . {{ cite book }} : CS1 maint: wiele nazwisk: lista autorów ( link )
  3. ^ Lueker, GS (1975). „Dwa problemy NP-zupełne w nieujemnym programowaniu liczb całkowitych”. Raport nr 178, Laboratorium Informatyki, Princeton. {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )
  4. ^ Gens, GV i Levner, EV (1979). „Algorytmy złożoności i aproksymacji dla problemów kombinatorycznych: ankieta”. Centralny Instytut Ekonomiczno-Matematyczny Akademii Nauk ZSRR w Moskwie. {{ cite news }} : CS1 maint: używa parametru autorów ( link )
  5. ^ „O istnieniu schematów szybkiego zbliżania” . Programowanie nieliniowe . 4 : 415–437. 1980.
  6. ^ Magazyn, MJ; Chern, M.-S. (1984). „Uwaga na temat schematów aproksymacji dla wielowymiarowych problemów plecakowych”. Matematyka badań operacyjnych . 9 (2): 244–247. doi : 10.1287/moor.9.2.244 .
  7. ^   Cohen, Reuven; Katzir, Liran (2008). „Uogólniony problem maksymalnego zasięgu”. Listy dotyczące przetwarzania informacji . 108 : 15–22. CiteSeerX 10.1.1.156.2073 . doi : 10.1016/j.ipl.2008.03.017 .