Lista över ryggsäcksproblem

Ryggsäcksproblemet är ett av de mest studerade problemen inom kombinatorisk optimering , med många verkliga tillämpningar. Av denna anledning har många specialfall och generaliseringar undersökts.

Gemensamt för alla versioner är en uppsättning av n artiklar, där varje objekt $1\leq j\leq n$ har en tillhörande vinst p _j och vikt w _j . Den binära beslutsvariabeln x _j används för att välja objektet. Målet är att välja några av föremålen, med maximal total vinst, samtidigt som man följer att den maximala totalvikten för de valda föremålen inte får överstiga W . I allmänhet skalas dessa koefficienter till att bli heltal, och de antas nästan alltid vara positiva.

Ryggsäcksproblemet i sin mest grundläggande form :

maximera $\sum _{j=1}^{n}p_{j}x_{j}$
föremål för	$\sum _{j=1}^{n}w_{j}x_{j}\leq W,$
	$x_{j}\in \{0,1\}$	$\forall j\in \{1,\ldots ,n\}$

Direkta generaliseringar

En vanlig variant är att varje artikel kan väljas flera gånger. Det avgränsade ryggsäcksproblemet specificerar, för varje objekt j , en övre gräns u _j (som kan vara ett positivt heltal eller oändligt) på antalet gånger som objekt j kan väljas:

maximera $\sum _{j=1}^{n}p_{j}x_{j}$
föremål för	$\sum _{j=1}^{n}w_{j}x_{j}\leq W,$
	$0\leq x_{j}\leq u_{j},x_{j}$ integral för alla j

Problemet med obegränsad ryggsäck (kallas ibland heltalsryggsäcksproblemet ) sätter inga övre gränser för antalet gånger ett objekt kan väljas:

maximera $\sum _{j=1}^{n}p_{j}x_{j}$
föremål för	$\sum _{j=1}^{n}w_{j}x_{j}\leq W,$
	$x_{j}\geq 0,x_{j}$ integral för alla j

Den obegränsade varianten visades vara NP-komplett 1975 av Lueker. Både de avgränsade och obegränsade varianterna tillåter en FPTAS (i ​​huvudsak samma som den som användes i 0-1 ryggsäcksproblemet).

Om objekten är uppdelade i k klasser betecknade ${\displaystyle N_{i}},$ och exakt ett objekt måste tas från varje klass, får vi flervalsproblemet med ryggsäck :

maximera $\sum _{i=1}^{k}\summa _{j\in N_{i}}p_{ij}x_{ I j}$
föremål för	$\sum _{i=1}^{k}\sum _{j\in N_{i}}w_{ij} x_{ij}\leq W,$
	$\sum _{j\in N_{i}}x_{ij}=1,$	för alla $1\leq i\leq k$
	$x_{ij}\in \{0,1\}$	för alla $1\leq i\leq k$ och alla $j\in N_{i}$

Om vinsten och vikten för varje post är lika, får vi delmängdssummansproblemet ( ofta anges motsvarande beslutsproblem istället):

maximera $\sum _{j=1}^{n}p_{j}x_{j}$
föremål för	$\sum _{j=1}^{n}p_{j}x_{j}\leq W,$
	$x_{j}\in \{0,1\}$

Om vi ​​har n föremål och m ryggsäckar med kapacitet $W_{i}$ får vi problemet med flera ryggsäckar :

maximera $\sum _{i=1}^{m}\summa _{j=1}^{n}p_{j}x_{ij }$
föremål för	${\displaystyle \sum _{j=1}^{n}w_{j}x_{ij}\leq W_{i},$	för alla $1\leq i\leq m$
	$\sum _{i=1}^{m}x_{ij}\leq 1,$	för alla $1\leq j\leq n$
	$x_{ij}\in \{0,1\}$	för alla $1\leq j\leq n$ och alla $1\leq i\leq m$

Som ett specialfall av problemet med flera ryggsäckar, när vinsten är lika med vikter och alla papperskorgar har samma kapacitet, kan vi ha problem med flera delmängder .

Kvadratiskt ryggsäcksproblem :

maximera $\sum _{j=1}^{n}p_{j }x_{j}+\summa _{i=1}^{n-1}\summa _{j=i+1}^{n}p_{ij}x_{i}x_{j}$
föremål för	$\sum _{j=1}^{n}w_{j}x_{j}\leq W,$
	$x_{j}\in \{0,1\}$	för alla $1\leq j\leq n$

Set-Union Knapsack Problem :

SUKP definieras av Kellerer et al (på sidan 423) enligt följande:

Givet en uppsättning av $n$ poster $N=\{1,\ldots ,n\}$ och en uppsättning $m$ så kallade element $P=\{1,\ldots ,m\}$ , varje objekt $j$ motsvarar en delmängd $P_{j}$ av elementuppsättning $P$ . Objekten $j$ har icke-negativ vinst $p_{j}$ , $j=1,\ldots ,n$ , och elementen ${\ displaystyle i}$ har icke-negativa vikter $w_{i}$ , $i=1,\ldots ,m$ . Den totala vikten av en uppsättning artiklar ges av den totala vikten av elementen i föreningen av motsvarande elementuppsättningar. Målet är att hitta en delmängd av föremålen vars totalvikt inte överstiger ryggsäckens kapacitet och maximal vinst.

Flera begränsningar

Om det finns mer än en begränsning (till exempel både en volymgräns och en viktgräns, där volymen och vikten för varje föremål inte är relaterade), får vi problemet med flera ryggsäckar , flerdimensionellt ryggsäcksproblem eller m - dimensionellt ryggsäcksproblem . (Observera att "dimension" här inte hänvisar till formen på några föremål.) Detta har 0-1, begränsade och obegränsade varianter; den obegränsade visas nedan.

maximera $\sum _{j=1}^{n}p_{j}x_{j}$
föremål för	${\displaystyle \sum _{j=1}^{n}w_{ij}x_{j}\leq W_{i},$	för alla $1\leq i\leq m$
	$x_{j}\geq 0$ , $x_{j}$ heltal	för alla $1\leq j\leq n$

0-1-varianten (för alla fasta $m\geq 2$ ) visades vara NP-komplett runt 1980 och ännu starkare, har ingen FPTAS om inte P=NP.

De avgränsade och obundna varianterna (för alla fasta $m\geq 2$ ) uppvisar också samma hårdhet.

För alla fasta $m\geq 2$ tillåter dessa problem en pseudopolynomisk tidsalgoritm (liknande den för grundläggande ryggsäck) och en PTAS .

Ryggsäcksliknande problem

Om alla vinster är 1, kommer vi att försöka maximera antalet föremål som inte skulle överstiga ryggsäckens kapacitet:

maximera $\sum _{j=1}^{n}x_{j}$
föremål för	$\sum _{j=1}^{n}w_{j}x_{j}\leq W,$
	$x_{j}\in \{0,1\},$	$\forall j\in \{1,\ldots ,n\}$

Om vi ​​har ett antal behållare (av samma storlek), och vi vill packa alla n artiklar i så få behållare som möjligt, får vi problem med bin packing , som modelleras genom att ha indikatorvariabler ${\ displaystyle y_{i}=1\Leftrightarrow }$ container i används:

minimera $\sum _{i=1}^{n}y_{i}$
föremål för	$\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\}$

Problemet med styckningslager är identiskt med problemet med soppackningsproblem , men eftersom praktiska instanser vanligtvis har mycket färre typer av föremål, används ofta en annan formulering. Objekt j behövs B _j gånger, varje "mönster" av föremål som passar in i en enda ryggsäck har en variabel, x _i (det finns m mönster), och mönster i använder objekt j b _ij gånger:

minimera $\sum _{i=1}^{m}x_{i}$
föremål för	$\sum _{i=1}^{m}b_{ij}x_{i}\geq B_{j},$	för alla $1\leq j\leq n$
	$x_{i}\in \{0,1,\ldots ,n\}$	för alla $1\leq i\leq m$

Om vi, till flervalsryggsäcksproblemet, lägger till begränsningen att varje delmängd är av storlek n och tar bort begränsningen på totalvikt, får vi tilldelningsproblemet , vilket också är problemet med att hitta en maximal tvådelad matchning :

maximera $\sum _{i=1}^{k}\summa _{j=1}^{n}p_{ij}x_{ I j}$
föremål för	$\sum _{i=1}^{n}x_{ij}=1,$	för alla $1\leq j\leq n$
	$\sum _{j=1}^{n}x_{ij}=1,$	för alla $1\leq i\leq n$
	$x_{ij}\in \{0,1\}$	för alla $1\leq i\leq k$ och alla $j\in N_{i}$

I varianten av ryggsäcken för maximal densitet finns en initial vikt $w_{0}$ och vi maximerar densiteten för utvalda föremål som inte bryter mot kapacitetsbegränsningen:

maximera ${\frac {\sum _{j=1}^{n}x_{j}p_{j}}{ w_{0}+\sum _{j=1}^{n}x_{j}w_{j}}}$
föremål för	$\sum _{j=1}^{n}w_{j}x_{j}\leq W,$
	$x_{j}\in \{0,1\},$	$\forall j\in \{1,\ldots ,n\}$

Även om det är mindre vanliga än de ovan, finns flera andra ryggsäcksliknande problem, inklusive:

• Kapslad ryggsäcksproblem
• Problem med att kollapsa ryggsäcken
• Icke-linjärt ryggsäcksproblem
• Omvänt parametriskt ryggsäcksproblem

De tre sista av dessa diskuteras i Kellerer et al:s referensverk, Knapsack Problems .

• "Algorithms for Rugsack Problems" , D. Pisinger. Ph.D. avhandling, DIKU, Köpenhamns universitet, Rapport 95/1 (1995).