Problem ranca

Из Википедије, слободне енциклопедије

Problem ranca je problem koji je najviše istraživan u kombinatornoj optimizaciji, sa mnogo primena u stvarnom životu. Zbog ovoga je ispitano mnogo specijalnih slučajeva i napravljeno je mnogo generalizacija.

Zajedničko za sve verzije je n predmeta, a svaki predmet 1 \leq j \leq n ima pridruženu vrednost pj i težinu wj. Cilj je sakupiti određeni broj predmeta, tako da vrednost ranca bude maksimalna, ali da ne pređe zadatu vrednost W. Uglavnom, ovi koeficijenti se skaliraju da bi bili celi brojevi i gotovo uvek se pretpostavlja da su pozitivni.

Problem ranca u osnovnoj formi:

maksimalno \sum_{j=1}^n p_j x_j
predmet \sum_{j=1}^n w_j x_j \leq W,
 x_j \in \{0,1\} \forall j \in \{1,\ldots, n\}

Direktne generalizacije[уреди]

Jedna od češćih varijanti je da se svaki predmet može birati više puta. Konkretno, kod problema ograničenog ranca za svaki predmet j, i gornju granicu uj (koja može biti pozitivan ceo broj ili beskonačno) za broj predmeta j može biti izabrano:

maksimalno \sum_{j=1}^n p_j x_j
predmet \sum_{j=1}^n w_j x_j \leq W,
 u_j \geq x_j \geq 0, x_j ceo broj za sve j

Neograničeni problem ranca (koji se nekada naziva i celobrojni problem ranca) ne postavlja gornju granicu za broj predmeta koji mogu da se odaberu:

maksimalno \sum_{j=1}^n p_j x_j
predmet \sum_{j=1}^n w_j x_j \leq W,
 x_j \geq 0, x_j ceo broj za sve j

Lueker je pokazao 1975. godine [1] da je varijata bez granice NP-kompletan problem. Obe varijatne, i sa ograničenjem i bez ograničenja, imaju aproskimativnu šemu polinomijalnog vremena - FPTAS (u suštini, kao i kod 0-1 problemna ranca).

Ako se predmeti podele na k klasa označene sa N_i, i ako iz svake klase mora da se uzme tačno jedan predmet, dobija se problem ranca sa višetrukim izborom:

maksimalno \sum_{i=1}^k\sum_{j\in N_i} p_{ij} x_{ij}
predmet \sum_{i=1}^k\sum_{j\in N_i} w_{ij} x_{ij} \leq W,
\sum_{j \in N_i}x_{ij} = 1, za sve 1 \leq i \leq k
 x_{ij} \in \{0,1\} za sve 1 \leq i \leq k i sve j \in N_i

Ako su za sve predmete vrednost i težina identični, dobijamo problem zbira podskupa (često je dat odgovarajući problem, problem odlučivanja ):

maksimalno \sum_{j=1}^n p_j x_j
predmet \sum_{j=1}^n p_j x_j \leq W,
 x_j \in \{0,1\}

Ako imamo n predmeta i m rančeva sa kapacitetima W_i, dobijamo višestruki problem ranca:

maksimalno \sum_{i=1}^m\sum_{j=1}^n p_j x_{ij}
predmet \sum_{j=1}^n w_j x_{ij} \leq W_i, za sve 1 \leq i \leq m
\sum_{i=1}^m x_{ij} \leq 1, za sve 1 \leq j \leq n
 x_{ij} \in \{0,1\} za sve 1 \leq j \leq n i sve 1 \leq i \leq m

Kao specijalan slučaj višetrukog problema ranca, kada su vrednosti jednake težinama i svi binovi imaju isti kapacitet, možemo imati i problem zbira višetrukog podskupa:

Kvadratni problem ranca:

maksimalno \sum_{j=1}^n p_j x_j+\sum_{i=1}^{n-1}\sum_{j=i+1}^n p_{ij} x_i x_j
predmet \sum_{j=1}^n w_j x_j \leq W,
 x_j \in \{0,1\} za sve 1 \leq j \leq n

Problem ranca - Unija skupa:

SUKP (Set-Union Knapsack Problem) je definisao Kellerer i dr.[2] (na 423. str.):

Dat je skup od n predmeta N = \{1, \ldots, n\} i skup od m, tako reći, elemenata P = \{1, \ldots, m\}, gde svaki predmet j odgovara podskupu P_j skupa elemenata P. Predmeti j imaju nenegativne vrednosti p_j, j = 1, \ldots, n, a elementi i nenegativne težine w_i, i = 1, \ldots, m. Konačna težina skupa predemeta je data konačnom težinom elemenata unije odgovarajućih skupa elemenata. Cilj je naći podskup predmeta sa konačnom težinom koja ne prelazi kapacitet ranca i maksimalnu vrednost.

Višestruko ograničenje[уреди]

Ako postoji više od jednog ograničenja (na primer, i granica za obim i granica za težinu, gde obim i težina svakog predmeta nisu povezani), dobijamo problem ranca sa višestrukim ograničenjem, višedimenzionalni problem ranca, ili m-dimenzionalni problem ranca. (Napomena, "dimenzija" se ovde ne odnosi na oblik predmeta.) Ovo ima 0-1, ograničenu, i neograničenu varijantu; neograničena je prikazana ispod.

maksimalno \sum_{j=1}^n p_j x_j
predmet \sum_{j=1}^n w_{ij} x_j \leq W_i, za sve 1 \leq i \leq m
x_j \geq 0, x_j integer za sve  1\leq j \leq n

Pokazano je da je varijanta 0-1 (za sve fiksne m \ge 2) NP-komplentna oko 1980. godine i da nema FPTAS osim ako je P=NP.[3][4]

Ograničena i neograničena varijanta (za sve fiksne m \ge 2) imaju istu složenost.[5]

Za bilo koje fiksno m \ge 2, ovi problemi imaju pseudo-polinomijalni algoritam (sličan onom za klasičn problem ranca) i PTAS.[2]

Ranac-slični problemi[уреди]

Ako su sve vrednosti jednake 1, možemo da pokušamo da minimizujemo broj predmeta koji tačno popunjuju ranac:

minimalno \sum_{j=1}^n x_j
predmet \sum_{j=1}^n w_j x_j = W,
 x_j \in \{0,1\},  \forall j \in \{1,\ldots,n\}

Ako imamo broj skladišta (iste veličine), i želimo da spakujemo svih n predmeta u što je manje moguće skladišta, dobijamo bin-problem ranca, koji je urađen tako da ima indikator za varijable y_i=1 \Leftrightarrow skladište i se trenutno koristi:

milimalno \sum_{i=1}^n y_i
predmet \sum_{j=1}^n w_j x_{ij} \leq Wy_i, \forall i \in \{1,\ldots,n\}
\sum_{i=1}^n x_{ij} = 1 \forall j \in \{1,\ldots,n\}
 y_i \in \{0,1\} \forall i \in \{1,\ldots,n\}
 x_{ij} \in \{0,1\} \forall i \in \{1,\ldots,n\} \wedge \forall j \in \{1,\ldots,n\}
  • Problem seckanja zaliha je identičan bin-problemu ranca, ali pošto parcijalne istance obično imaju mnogo manje tipova predmeta, često se koristi druga formulacija. Predmet j je potreban Bj puta, svaki primer premdeta koji može da stane u samo jedan ranac ima promenljivu, xi (postoji m primera), i primer i koristi predmet j bij puta:
minimalno \sum_{i=1}^m x_i
predmet \sum_{i=1}^m b_{ij} x_i \leq B_j, za sve 1 \leq j \leq n
x_i \in \{0,1,\ldots ,n\} za sve 1\leq i \leq m

Ako na višestruki problem ranca, dodamo ograničenje da je svaki podskup veličine n i uklonimo ograničenje za konačnu težinu, dobijamo problem zadatka, koji je takođe problem pronalaženja maksimalnog bipartitivnog poklapanja:

maksimalno \sum_{i=1}^k\sum_{j=1}^n p_{ij} x_{ij}
predmet \sum_{i=1}^n x_{ij} = 1, za sve 1 \leq j \leq n
\sum_{j=1}^n x_{ij} = 1, za sve 1 \leq i \leq n
 x_{ij} \in \{0,1\} za sve 1 \leq i \leq k i sve j \in N_i

U varijanti ranac maksimalne gustine postoji inicijalna težina w_0, i mi uvećavamo gustinu izabranog predemta koi ne ugrožava kapacitet ograničenja: [6]

maksimalno \frac{\sum_{j=1}^n x_j p_j}{w_0 +\sum_{j=1}^n x_j w_j}
predmet \sum_{j=1}^n w_j x_j \leq W,
 x_j \in \{0,1\},  \forall j \in \{1,\ldots,n\}

Iako su manje poznadi od problema pomenutih iznad, postoji još nekoliko ranac-sličnih problema, uključujući:

  • Ugneždeni problem ranca
  • Kolapsirajući problem ranca
  • Nelinearan problem ranca
  • Obrnuto-parametarski problem ranca

Od ovih, poslednja tri su obrađena u referencnom radu Kellerer-a i drugih, Knapsack Problems.[2]

Reference[уреди]

  1. ^ Lueker, G.S. (1975). „Two NP-complete problems in nonnegative integer programming“. Report No. 178, Computer Science Laboratory, Princeton. 
  2. ^ а б в Kellerer, Hans and Pferschy, Ulrich and Pisinger, David (2004). Knapsack Problems. Springer Verlag. ISBN 3-540-40286-1. 
  3. ^ Gens, G. V. and Levner, E. V. (1979). „Complexity and Approximation Algorithms for Combinatorial Problems: A Survey“. Central Economic and Mathematical Institute, Academy of Sciences of the USSR, Moscow. 
  4. ^ „On the Existence of Fast Approximation Schemes“. Nonlinear Programming (Academic Press) 4: 415-437. 1980. 
  5. ^ Magazine, M. J.; Chern, M.-S. (1984). „A Note on Approximation Schemes for Multidimensional Knapsack Problems“. Mathematics of Operations Research 9 (2): 244-247. DOI:10.1287/moor.9.2.244. 
  6. ^ Cohen, R. and Katzir, L. 2008. The Generalized Maximum Coverage Problem. Inf. Process. Lett. 108, 1 (Sep. 2008), 15-22.

Literatura[уреди]