Seznam problémů s batohem - List of knapsack problems

The batoh problém je jedním z nejvíce studovaných problémů v kombinatorická optimalizace s mnoha aplikacemi v reálném životě. Z tohoto důvodu bylo zkoumáno mnoho zvláštních případů a zobecnění.^[1]^[2]

Společné pro všechny verze je sada n položky, s každou položkou ${displaystyle 1leq jleq n}$ s přidruženým ziskem str_j ,hmotnost w_j. Proměnná binárního rozhodnutí X_j slouží k výběru položky. Cílem je vybrat některé z položek s maximálním celkovým ziskem, přičemž je třeba dodržet maximální celkovou váhu vybraných položek Ž. Obecně se tyto koeficienty upravují tak, aby se z nich stala celá čísla, a téměř vždy se předpokládá, že jsou kladné.

The batoh problém v nejzákladnější podobě:

maximalizovat ${displaystyle sum _ {j = 1} ^ {n} p_ {j} x_ {j}}$
podléhá	${displaystyle sum _ {j = 1} ^ {n} w_ {j} x_ {j} leq W,}$
	${displaystyle x_ {j} v {0,1}}$	${displaystyle forall jin {1, ldots, n}}$

Přímé zobecnění

Jedna společná varianta je, že každou položku lze vybrat několikrát. The ohraničený problém s batohem určuje pro každou položku j, horní mez u_j (což může být kladné celé číslo nebo nekonečno) na počet opakování položky j lze vybrat:

maximalizovat ${displaystyle sum _ {j = 1} ^ {n} p_ {j} x_ {j}}$
podléhá	${displaystyle sum _ {j = 1} ^ {n} w_ {j} x_ {j} leq W,}$
	${displaystyle u_ {j} geq x_ {j} geq 0, x_ {j}}$ integrální pro všechny j

The neomezený problém s batohem (někdy nazývaný celočíselný batoh) nedává žádné horní hranice počtu případů, kdy může být položka vybrána:

maximalizovat ${displaystyle sum _ {j = 1} ^ {n} p_ {j} x_ {j}}$
podléhá	${displaystyle sum _ {j = 1} ^ {n} w_ {j} x_ {j} leq W,}$
	${displaystyle x_ {j} geq 0, x_ {j}}$ integrální pro všechny j

Ukázalo se, že neomezená varianta je NP-kompletní v roce 1975 Lueker.^[3] Omezené i neomezené varianty připouštějí FPTAS (v zásadě stejné jako u problému s batohem 0-1).

Pokud jsou položky rozděleny na k třídy označené ${displaystyle N_ {i}}$ , a z každé třídy musí být odebrána přesně jedna položka, dostaneme problém s batohem s výběrem z několika možností:

maximalizovat ${displaystyle sum _ {i = 1} ^ {k} sum _ {jin N_ {i}} p_ {ij} x_ {ij}}$
podléhá	${displaystyle sum _ {i = 1} ^ {k} sum _ {jin N_ {i}} w_ {ij} x_ {ij} leq W,}$
	${displaystyle sum _ {jin N_ {i}} x_ {ij} = 1,}$	pro všechny ${displaystyle 1leq ileq k}$
	${displaystyle x_ {ij} v {0,1}}$	pro všechny ${displaystyle 1leq ileq k}$ a všechno ${displaystyle jin N_ {i}}$

Pokud jsou pro každou položku zisk a váha stejné, dostaneme problém s podmnožinou (často odpovídající rozhodovací problém místo toho):

maximalizovat ${displaystyle sum _ {j = 1} ^ {n} p_ {j} x_ {j}}$
podléhá	${displaystyle sum _ {j = 1} ^ {n} p_ {j} x_ {j} leq W,}$
	${displaystyle x_ {j} v {0,1}}$

Pokud ano n položky a m batohy s kapacitou ${displaystyle W_ {i}}$ , dostaneme problém s více batohy:

maximalizovat ${displaystyle sum _ {i = 1} ^ {m} sum _ {j = 1} ^ {n} p_ {j} x_ {ij}}$
podléhá	${displaystyle sum _ {j = 1} ^ {n} w_ {j} x_ {ij} leq W_ {i},}$	pro všechny ${displaystyle 1leq ileq m}$
	${displaystyle sum _ {i = 1} ^ {m} x_ {ij} leq 1,}$	pro všechny ${displaystyle 1leq jleq n}$
	${displaystyle x_ {ij} v {0,1}}$	pro všechny ${displaystyle 1leq jleq n}$ a všechno ${displaystyle 1leq ileq m}$

Jako zvláštní případ problému s více batohy, když se zisky rovnají vahám a všechny koše mají stejnou kapacitu, můžeme mít problém součtu více podmnožin.

Kvadratický batoh:

maximalizovat ${displaystyle sum _ {j = 1} ^ {n} p_ {j} x_ {j} + sum _ {i = 1} ^ {n-1} sum _ {j = i + 1} ^ {n} p_ { ij} x_ {i} x_ {j}}$
podléhá	${displaystyle sum _ {j = 1} ^ {n} w_ {j} x_ {j} leq W,}$
	${displaystyle x_ {j} v {0,1}}$	pro všechny ${displaystyle 1leq jleq n}$

Set-Union Batoh Problém:

SUKP definují Kellerer et al^[2] (na straně 423) takto:

Vzhledem k souboru ${displaystyle n}$ položky ${displaystyle N = {1, ldots, n}}$ a sada ${displaystyle m}$ takzvané prvky ${displaystyle P = {1, ldots, m}}$ , každý předmět ${displaystyle j}$ odpovídá podmnožině ${displaystyle P_ {j}}$ sady prvků ${displaystyle P}$ . Předměty ${displaystyle j}$ mít nezáporné zisky ${displaystyle p_ {j}}$ , ${displaystyle j = 1, ldots, n}$ a prvky ${displaystyle i}$ mít nezáporné váhy ${displaystyle w_ {i}}$ , ${displaystyle i = 1, ldots, m}$ . Celková váha sady položek je dána celkovou hmotností prvků spojení příslušných sad prvků. Cílem je najít podmnožinu položek s celkovou hmotností nepřesahující kapacitu batohu a maximálním ziskem.

Několik omezení

Pokud existuje více než jedno omezení (například omezení objemu a omezení hmotnosti, kde objem a hmotnost každé položky nesouvisí), dostaneme mnohonásobně omezený problém s batohem, vícerozměrný problém s batohemnebo m-rozměrný batoh. (Poznámka: „kóta“ zde neodkazuje na tvar žádné položky.) Má 0-1, ohraničené a neohraničené varianty; neomezený je uveden níže.

maximalizovat ${displaystyle sum _ {j = 1} ^ {n} p_ {j} x_ {j}}$
podléhá	${displaystyle sum _ {j = 1} ^ {n} w_ {ij} x_ {j} leq W_ {i},}$	pro všechny ${displaystyle 1leq ileq m}$
	${displaystyle x_ {j} geq 0}$ , ${displaystyle x_ {j}}$ celé číslo	pro všechny ${displaystyle 1leq jleq n}$

Varianta 0-1 (pro všechny pevné ${displaystyle mgeq 2}$ ) se ukázalo být NP-kompletní kolem roku 1980 a silněji, nemá FPTAS, pokud P = NP.^[4]^[5]

Omezené a neomezené varianty (pro všechny pevné ${displaystyle mgeq 2}$ ) také vykazují stejnou tvrdost.^[6]

Pro všechny pevné ${displaystyle mgeq 2}$ , tyto problémy připouští a pseudo-polynomiální čas algoritmus (podobný jako u základního batohu) a a PTAS.^[2]

Problémy podobné batohu

Pokud jsou všechny zisky 1, pokusíme se maximalizovat počet položek, které by nepřekročily kapacitu batohu:

maximalizovat ${displaystyle sum _ {j = 1} ^ {n} x_ {j}}$
podléhá	${displaystyle sum _ {j = 1} ^ {n} w_ {j} x_ {j} leq W,}$
	${displaystyle x_ {j} v {0,1},}$	${displaystyle forall jin {1, ldots, n}}$

Pokud máme několik kontejnerů (stejné velikosti) a chceme je zabalit všechny n položky v co nejmenším počtu kontejnerů, dostaneme problém s balením koše, který je modelován pomocí indikátorových proměnných ${displaystyle y_ {i} = 1 Levý pravý šíp}$ kontejner i se používá:

minimalizovat ${displaystyle sum _ {i = 1} ^ {n} y_ {i}}$
podléhá	${displaystyle sum _ {j = 1} ^ {n} w_ {j} x_ {ij} leq Wy_ {i},}$	${displaystyle forall iin {1, ldots, n}}$
	${displaystyle sum _ {i = 1} ^ {n} x_ {ij} = 1}$	${displaystyle forall jin {1, ldots, n}}$
	${displaystyle y_ {i} v {0,1}}$	${displaystyle forall iin {1, ldots, n}}$
	${displaystyle x_ {ij} v {0,1}}$	${displaystyle forall iin {1, ldots, n} klín pro all jin {1, ldots, n}}$

The problém řezného materiálu je totožný s problém s balením koše, ale protože praktické instance mají obvykle mnohem méně typů položek, často se používá jiná formulace. Položka j je potřeba B_j každý „vzor“ položek, které se vejdou do jednoho batohu, má proměnnou, X_i (existují m vzory) a vzor i používá položku j b_ij časy:

minimalizovat ${displaystyle sum _ {i = 1} ^ {m} x_ {i}}$
podléhá	${displaystyle sum _ {i = 1} ^ {m} b_ {ij} x_ {i} leq B_ {j},}$	pro všechny ${displaystyle 1leq jleq n}$
	${displaystyle x_ {i} v {0,1, ldots, n}}$	pro všechny ${displaystyle 1leq ileq m}$

Pokud k problému s batohem s výběrem z několika možností přidáme omezení, že každá podmnožina má velikost n a odstraníme omezení celkové hmotnosti, dostaneme problém s přiřazením, což je také problém najít maximum bipartitní shoda:

maximalizovat ${displaystyle sum _ {i = 1} ^ {k} sum _ {j = 1} ^ {n} p_ {ij} x_ {ij}}$
podléhá	${displaystyle sum _ {i = 1} ^ {n} x_ {ij} = 1,}$	pro všechny ${displaystyle 1leq jleq n}$
	${displaystyle sum _ {j = 1} ^ {n} x_ {ij} = 1,}$	pro všechny ${displaystyle 1leq ileq n}$
	${displaystyle x_ {ij} v {0,1}}$	pro všechny ${displaystyle 1leq ileq k}$ a všechno ${displaystyle jin N_ {i}}$

V Batoh s maximální hustotou varianta je počáteční hmotnost ${displaystyle w_ {0}}$ a maximalizujeme hustotu vybraných položek, které neporušují omezení kapacity:^[7]

maximalizovat ${displaystyle {frac {sum _ {j = 1} ^ {n} x_ {j} p_ {j}} {w_ {0} + sum _ {j = 1} ^ {n} x_ {j} w_ {j} }}}$
podléhá	${displaystyle sum _ {j = 1} ^ {n} w_ {j} x_ {j} leq W,}$
	${displaystyle x_ {j} v {0,1},}$	${displaystyle forall jin {1, ldots, n}}$

I když jsou méně časté než výše uvedené, existuje několik dalších problémů podobných batohu, včetně:

Vnořený problém s batohem
Problém se skládacím batohem
Nelineární problém s batohem
Problém s inverzně-parametrickým batohem

Poslední tři z nich jsou popsány v referenční práci Kellerer et al, Problémy s batohem.^[2]

Reference

^ Martello, Silvano a Toth, Paolo (1990). Problémy s batohem: Algoritmy a počítačové implementace. John Wiley & Sons. ISBN 978-0471924203.CS1 maint: více jmen: seznam autorů (odkaz)
^ ^A ^b ^C ^d Kellerer, Hans and Pferschy, Ulrich and Pisinger, David (2004). Problémy s batohem. Springer Verlag. ISBN 978-3-540-40286-2.CS1 maint: více jmen: seznam autorů (odkaz)
^ Lueker, GS (1975). "Dva NP-úplné problémy v nezáporném celočíselném programování". Zpráva č. 178, Computer Science Laboratory, Princeton. Citovat deník vyžaduje | deník = (Pomoc)
^ Gens, G. V. a Levner, E. V. (1979). "Složitost a přibližné algoritmy pro kombinatorické problémy: průzkum". Ústřední ekonomický a matematický institut, Akademie věd SSSR, Moskva.CS1 maint: používá parametr autoři (odkaz)
^ „O existenci schémat rychlé aproximace“. Nelineární programování. 4: 415–437. 1980.
^ Magazine, M. J .; Chern, M.-S. (1984). "Poznámka k aproximačním schématům pro vícerozměrné problémy s batohy". Matematika operačního výzkumu. 9 (2): 244–247. doi:10,1287 / bř. 9.2.244.
^ Cohen, Reuven; Katzir, Liran (2008). "Zobecněný problém maximálního pokrytí". Dopisy o zpracování informací. 108: 15–22. CiteSeerX 10.1.1.156.2073. doi:10.1016 / j.ipl.2008.03.017.

„Algoritmy pro problémy s batohy“, D. Pisinger. Ph.D. diplomová práce, DIKU, University of Copenhagen, Report 95/1 (1995).

[KP-MT-1] Martello, Silvano a Toth, Paolo (1990). Problémy s batohem: Algoritmy a počítačové implementace. John Wiley & Sons. ISBN 978-0471924203.CS1 maint: více jmen: seznam autorů (odkaz)

[KP-KPP-2] A ^b ^C ^d Kellerer, Hans and Pferschy, Ulrich and Pisinger, David (2004). Problémy s batohem. Springer Verlag. ISBN 978-3-540-40286-2.CS1 maint: více jmen: seznam autorů (odkaz)

[3] Lueker, GS (1975). "Dva NP-úplné problémy v nezáporném celočíselném programování". Zpráva č. 178, Computer Science Laboratory, Princeton. Citovat deník vyžaduje | deník = (Pomoc)

[4] Gens, G. V. a Levner, E. V. (1979). "Složitost a přibližné algoritmy pro kombinatorické problémy: průzkum". Ústřední ekonomický a matematický institut, Akademie věd SSSR, Moskva.CS1 maint: používá parametr autoři (odkaz)

[5] „O existenci schémat rychlé aproximace“. Nelineární programování. 4: 415–437. 1980.

[6] Magazine, M. J .; Chern, M.-S. (1984). "Poznámka k aproximačním schématům pro vícerozměrné problémy s batohy". Matematika operačního výzkumu. 9 (2): 244–247. doi:10,1287 / bř. 9.2.244.

[7] Cohen, Reuven; Katzir, Liran (2008). "Zobecněný problém maximálního pokrytí". Dopisy o zpracování informací. 108: 15–22. CiteSeerX 10.1.1.156.2073. doi:10.1016 / j.ipl.2008.03.017.

[1]

[2]

[3]

[4]

[5]

[6]

[7]