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 p_j i težinu w_j. Cilj je sakupiti određeni broj predmeta, tako da vrednost ranca bude maksimalna, ali da težina ranca 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 u_j (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]:

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\geq 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\geq 2$ ) imaju istu složenost.^[5]

Za bilo koje fiksno $m\geq 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 B_j puta, svaki primer premdeta koji može da stane u samo jedan ranac ima promenljivu, x_i (postoji m primera), i primer i koristi predmet j b_ij 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

^ Lueker, G.S. (1975). „Report No. 178, Computer Science Laboratory, Princeton; Two NP-complete problems in nonnegative integer programming”.
^ ^а ^б ^в Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Knapsack Problems. Springer Verlag. стр. 423. ISBN 3-540-40286-1.
^ Gens, G. V.; 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.
^ Korte, B.; Schrader, R. (1980). „On the Existence of Fast Approximation Schemes”. Nonlinear Programming. Academic Press. 4: 415—437.
^ Magazine, M. J.; Chern, M.-S.; Magazine, Michael J.; Chern, Maw-Sheng (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.
^ Cohen, Reuven; Katzir, Liran (2008). „The Generalized Maximum Coverage Problem”. Information Processing Letters. 108: 15—22. doi:10.1016/j.ipl.2008.03.017.

Literatura

"Algorithms for Knapsack Problems", D. Pisinger. Ph.D. thesis, DIKU, University of Copenhagen, Report 95/1 (1995).

[1] Lueker, G.S. (1975). „Report No. 178, Computer Science Laboratory, Princeton; Two NP-complete problems in nonnegative integer programming”.

[KP-KPP-2] а ^б ^в Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Knapsack Problems. Springer Verlag. стр. 423. ISBN 3-540-40286-1.

[3] Gens, G. V.; 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] Korte, B.; Schrader, R. (1980). „On the Existence of Fast Approximation Schemes”. Nonlinear Programming. Academic Press. 4: 415—437.

[5] Magazine, M. J.; Chern, M.-S.; Magazine, Michael J.; Chern, Maw-Sheng (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, Reuven; Katzir, Liran (2008). „The Generalized Maximum Coverage Problem”. Information Processing Letters. 108: 15—22. doi:10.1016/j.ipl.2008.03.017.

[1]

[2]

[3]

[4]

[5]

[6]