Kvadratiskt ryggsäcksproblem

Det kvadratiska ryggsäcksproblemet (QKP) , som introducerades först på 1800-talet, är en förlängning av ryggsäcksproblemet som tillåter kvadratiska termer i den objektiva funktionen: Givet en uppsättning artiklar, var och en med en vikt, ett värde och en extra vinst som kan tjänas in om två föremål väljs, bestämma antalet föremål som ska inkluderas i en samling utan att överskrida ryggsäckens kapacitet, för att maximera den totala vinsten. Vanligtvis kommer kvadratiska ryggsäcksproblem med en begränsning av antalet kopior av varje typ av föremål: antingen 0 eller 1. Denna speciella typ av QKP utgör 0-1 kvadratisk ryggsäcksproblem , som först diskuterades av Gallo et al. Det 0-1 kvadratiska ryggsäcksproblemet är en variant av ryggsäcksproblem som kombinerar funktionerna med problem med obegränsad ryggsäck, 0-1 ryggsäcksproblem och kvadratisk ryggsäcksproblem.

Definition

Specifikt har 0–1 kvadratisk ryggsäcksproblem följande form:

{\displaystyle {\text{maximera }}\left\{\sum _{i=1}^{n}p_{i}x_{i}+\summa _{i=1}^{n}\summa _ {j=1,i\neq j}^{n}P_{ij}x_{i}x_{j}:x\in X,x{\text{ binary}}\right\}} med förbehåll

{\text{med förbehåll för }}X\equiv \left\{x\in \{0,1\}^{n}:\summa _{i=1}^{n}w_{i}x_ {i}\leq W;x_{i}\in \{0,1\}{\text{ för }}i=1,\ldots ,n\right\}.

Här representerar den binära variabeln x _i om objekt i ingår i ryggsäcken, $p_{i}$ är vinsten som tjänas genom att välja objekt i och $P_{ij}$ är vinsten som uppnås om både punkt i och j läggs till.

Informellt är problemet att maximera summan av värdena på föremålen i ryggsäcken så att summan av vikterna är mindre än eller lika med ryggsäckens kapacitet.

Ansökan

Som man kan förvänta sig har QKP ett brett utbud av applikationer inklusive telekommunikation , transportnätverk , datavetenskap och ekonomi . Faktum är att Witzgall först diskuterade QKP när de valde platser för satellitstationer för att maximera den globala trafiken med hänsyn till en budgetbegränsning. Liknande modell gäller problem som att överväga placeringen av flygplatser, järnvägsstationer eller godshanteringsterminaler. Tillämpningar av QKP inom datavetenskap är vanligare efter de första dagarna: kompilatordesignproblem , klickproblem , design av mycket storskalig integration (VLSI). Dessutom verkar prissättningsproblem vara en tillämpning av QKP som beskrivs av Johnson et al.

Beräkningskomplexitet

I allmänhet är beslutsversionen av ryggsäcksproblemet (Kan ett värde på minst V uppnås under en begränsning av en viss kapacitet W?) NP-komplett . Således kan en given lösning verifieras till i polynomtid medan ingen algoritm kan identifiera en lösning effektivt.

Optimeringsryggsäcksproblemet är NP-hårt och det finns ingen känd algoritm som kan lösa problemet i polynomtid.

Som en speciell variant av ryggsäcksproblemet är det 0-1 kvadratiska ryggsäcksproblemet också NP-hårt.

Även om det inte finns någon tillgänglig effektiv algoritm i litteraturen, finns det en pseudopolynomtid baserad på dynamisk programmering och andra heuristiska algoritmer som alltid kan generera "bra" lösningar.

Lösning

Även om ryggsäcksproblemet är ett av de vanligaste lösta operationsforskningsproblemen (OR), finns det begränsade effektiva algoritmer som kan lösa 0-1 kvadratiska ryggsäcksproblem. Tillgängliga algoritmer inkluderar men är inte begränsade till brute force , linjärisering och konvex omformulering. Precis som andra NP-hårda problem räcker det oftast med att hitta en fungerande lösning även om den inte nödvändigtvis är optimal. Heuristiska algoritmer baserade på girig algoritm , dynamisk programmering kan ge en relativt "bra" lösning på 0-1 QKP effektivt.

Råstyrka

Brute-force-algoritmen för att lösa detta problem är att identifiera alla möjliga delmängder av objekten utan att överskrida kapaciteten och välja den med det optimala värdet. Pseudokoden tillhandahålls enligt följande:








   0
    
        0
       0   
             // Indata:  // Vinster (lagrade i array p)  // Kvadratiska vinster (lagrade i matris P)  // Vikter (lagrade i array w)  // Antal artiklar (n)  // Ryggsäckskapacitet (W)  int  max  =  för  alla  delmängder  S  do  int  värde  ,  vikt  =  för  i  från  till  S.  _  storlek  -1  do  :  värde  =  värde  +  p  [  i  ] 
            
                   
                    
        
                
               vikt  =  vikt  +  w  [  i  ]  för  j  från  i  +  1  till  S.  _  storlek  -1  do  :  värde  =  värde  +  P  [  i  ][  j  ]  om  vikt  <=  W  då  :  om  värde  >  max  då  :  max  =  värde

Givet n objekt kommer det att finnas högst $2^{n}$ delmängder och för varje laglig kandidatuppsättning är körtiden för att beräkna de intjänade värdena $O(n^{ 2})$ . Sålunda är effektivitetsklassen för brute-force-algoritmen $(2^{n}n^{2})=\lambda (2^{n})$ , vara exponentiell.

Linjärisering

Problem av sådan form är svåra att lösa direkt med hjälp av standardlösare och därför försöker folk omformulera det som ett linjärt program med hjälp av hjälpvariabler och begränsningar så att problemet enkelt kan lösas med kommersiella paket. Två välkända linjäriseringsmetoder för 0-1 QKP är standardlinjäriseringen och Glovers linjärisering.

Standard linearisering

Den första är den vanliga linjäriseringsstrategin, som visas nedan:

\sum _{i=1}^{n}p_{i}x_{i}+\sum _{i=1}^{n}\left(\sum _{j=1,i<j }^{n}(P_{ij}+P_{ji})z_{ij}\right).

maximera

med förbehåll för

z_{ij}\leq x_{i}

för alla

(i,j),i<j

z_{ij}\leq x_{j}

för alla

(i,j),i<j

x_{i}+x_{j}-1\leq z_{ij}

för alla

(i,j),i<j

z_{ij}\geq 0

för alla

(i,j),i<j

x\in X, x

binär

I formuleringen LP1 har vi ersatt x _i x _j termen med en kontinuerlig variabel z _ij . Detta omformulerar QKP till ett ryggsäcksproblem, som vi sedan kan lösa optimalt med standardlösare.

Glovers linjärisering

Den andra omformuleringen, som är mer kortfattad, kallas Glovers linjärisering. Glover-formuleringen visas nedan, där Li _och U _i är nedre och övre gränser på ${n}P_{ij}x_{j}}$ $\sum _{j=1,i\neq j$ ^ , respektive:

LP2: maximera

\sum _{i=1}^{n}p_{i}x_{i}+\summa _{i= 1}^{n}z_{i}

omfattas av

L_{i}x_{i}\leq z_{i}\leq U_{i}x_{ i}

för

i=1,\ldots ,n

{\displaystyle \sum _{j=1,i\neq j}^{n}P_{ij}x_{j}-U_{i}(1-x_{i})\leq z_{i}\leq \ summa _{j=1,i\neq j}^{n}P_{ij}x_{j}-L_{i}(1-x_{i})} för i =

1

i =1,\ldots ,n}

x\in X,x

binär

I formuleringen LP2 har vi ersatt uttrycket $\sum _{j=1,i\neq j}^{n}P_{ij} x_{i}x_{j}$ med en kontinuerlig variabel z _i . På samma sätt kan vi använda standardlösare för att lösa det linjäriserade problemet. Observera att Glovers linjärisering endast inkluderar $n$ hjälpvariabler med $2n$ begränsningar medan standardlinjärisering kräver ${n \choose 2}$ hjälpvariabler och $3{n \choose 2}$ begränsningar för att uppnå linjäritet.

Konvex kvadratisk omformulering

Observera att icke-linjära program är svåra att lösa på grund av möjligheten att fastna vid ett lokalt maximum . Men när programmet är konvext är varje lokalt maximum det globala maximum . Ett konvext program är att maximera en konkav funktion eller minimera en konvex funktion på en konvex uppsättning . En mängd S är konvex om $\forall u,v\in S$ , $\lambda u+(1-\lambda )v\in S$ där $\lambda \in [0,1]$ . Det vill säga, vilken punkt som helst mellan två punkter i mängden måste också vara en del av mängden. En funktion f är konkav om $f[\lambda u+(1-\lambda )v]\leq \lambda f(u)+(1-\lambda )f(v)$ . En funktion f är konvex om $f[\lambda u+(1-\lambda )v] \geq \lambda f(u)+(1-\lambda )f(v)$ . Informellt är en funktion konkav om linjesegmentet som förbinder två punkter på grafen ligger ovanför eller på grafen, medan en funktion är konvex om under eller på grafen. Genom att skriva om objektivfunktionen till en ekvivalent konvex funktion kan vi alltså omformulera programmet till att bli konvext, vilket kan lösas med hjälp av optimeringspaket.

Objektivfunktionen kan skrivas som $c^{T}x+x^{T}Cx$ med linjär algebranotation. Vi behöver göra P till en positiv semidefinitiv matris för att omformulera en konvex funktion. I det här fallet ändrar vi objektivfunktionen till $p^{T}x+x^{T}Px+\summa _{i=1}^{n}\left(\summa _{j=1,j\ neq i}^{n}|P_{ij}|\right)(x_{i}^{2}-x_{i})$ genom att tillämpa resultat från linjär algebra, där P är en diagonalt dominant matris och därmed en positiv halvbestämt. Denna omformulering kan lösas med hjälp av ett kommersiellt standardpaket med blandat heltal.

Girig heuristisk algoritm

George Dantzig föreslog en girig approximationsalgoritm till obegränsat ryggsäcksproblem som också kan användas för att lösa 0-1 QKP. Algoritmen består av två fraser: identifiera en initial lösning och förbättra den.

Beräkna först för varje objekt, det totala objektiva bidraget som kan realiseras genom att välja det, $p_{i}+\sum _{i\neq j}^{n}P_{ij }$ , och sortera objekten i fallande ordning efter det potentiella värdet per viktenhet, $(p_{i}+\summa _{i\ neq j}^{n}P_{ij})/w_{i}$ . Välj sedan föremålen med maximalt värde-viktförhållande i ryggsäcken tills det inte finns plats för mer, vilket utgör den initiala lösningen. Från och med den initiala lösningen genomförs förbättringen genom parvis utbyte. För varje objekt i lösningsuppsättningen, identifiera de objekt som inte finns i uppsättningen där byte resulterar i ett förbättrat mål. Välj paret med maximal förbättring och byt. Det finns också möjligheter att ta bort en från setet eller lägga till en till setet ger det största bidraget. Upprepa tills det inte blir något bättre byte. Komplexitetsklassen för denna algoritm är $O(2^{n})$ eftersom i värsta fall alla möjliga kombinationer av objekt kommer att identifieras.

Quadknap

Quadknap är en exakt gren-och-bunden algoritm som föreslagits av Caprara et al., där övre gränser beräknas genom att överväga en lagrangisk avslappning som approximerar ett svårt problem med ett enklare problem och straffar överträdelser av begränsningar med Lagrange-multiplikator för att lägga ut en kostnad på överträdelser . Quadknap släpper heltalskravet vid beräkning av de övre gränserna. Suboptimala lagrangiska multiplikatorer härleds från subgradientoptimering och ger en bekväm omformulering av problemet. Denna algoritm är ganska effektiv eftersom lagrangiska multiplikatorer är stabila och lämpliga datastrukturer används för att beräkna en snäv övre gräns i linjär förväntad tid i antalet variabler. Denna algoritm rapporterades generera exakta lösningar för instanser med upp till 400 binära variabler , dvs betydligt större än de som kan lösas med andra tillvägagångssätt. Koden skrevs i C och finns tillgänglig online.

Dynamisk programmeringsheuristik

Medan dynamisk programmering kan generera optimala lösningar på ryggsäcksproblem, kan dynamiska programmeringsmetoder för QKP bara ge en lösning av relativt god kvalitet, som kan fungera som en nedre gräns för de optimala målen. Medan den körs i pseudopolynomisk tid har den ett stort minneskrav.

Dynamisk programmeringsalgoritm

För enkelhetens skull, anta att alla vikter är icke-negativa. Målet är att maximera det totala värdet under förutsättning att den totala vikten är mindre än eller lika med W . Sedan för varje $w\leq W$ , definiera $f(m,w)$ som värdet av den mest lönsamma packningen av de första m föremål som hittats med en totalsumma vikt av w . Det vill säga låt

f(m,w)=\max \left\{\sum _{i=1}^{m}p_{i}x_{i}+\sum _{i=1}^{m}\ summa _{j=1,i\neq j}^{m}P_{ij}x_{i}x_{j}:\summa _{i=1}^{m}w_{i}=w,1\ leq i\leq m\right\}.

Då är $f(m,w)$ lösningen på problemet. Observera att genom dynamisk programmering uppstår lösningen på ett problem från lösningen på dess mindre delproblem. Börja i det här fallet med det första föremålet och försök hitta en bättre packning genom att överväga att lägga till föremål med en förväntad vikt på 𝑤. Om vikten på föremålet som ska läggas till överstiger 𝑤 , då är $f(m,w)$ samma med $f(m-1,w)$ . Med tanke på att artikeln har en mindre vikt jämfört med den önskade vikten, $f(m- 1,w)$ $f(m,w)$ antingen samma som om tillägg inte ger något bidrag, eller samma som lösningen för en ryggsäck med mindre kapacitet, närmare bestämt en med kapaciteten reducerad med vikten av det valda föremålet, plus värdet av ett korrekt föremål, dvs $f(m-1,w-w_{m})+p_{m}+\summa _{i=1}^ {m-1}P_{im}x_{i}$ . Avslutningsvis har vi det

f(m,w)={\begin{cases}\max f(m-1,w),f(m-1,w-w_{m})+p_{m }+\summa _{i=1}^{m-1}P_{im}x_{i}&{\text{if }}w_{m}\leq w\\f(m-1,w)& {\text{annars}}\end{case}}

Anmärkning om effektivitetsklass: Uppenbarligen är körtiden för denna algoritm ${\displaystyle O(Wn^{2})} ,$ baserat på den kapslade slingan och beräkningen av vinsten från ny packning. Detta motsäger inte det faktum att QKP är NP-hård eftersom W inte är polynom i längden på inmatningen.

Reviderad dynamisk programmeringsalgoritm

Observera att den tidigare algoritmen kräver $O(Wn^{2})$ utrymme för att lagra den aktuella packningen av föremål för alla m,w , som kanske inte kan hantera stora problem. Faktum är att detta enkelt kan förbättras genom att ta bort indexet m från $f(m,w)$ eftersom alla beräkningar endast beror på resultaten från föregående steg.

Omdefiniera $f(w)$ för att vara det aktuella värdet av den mest lönsamma packningen som hittas av heuristiken. Det är,

f(w)=\max \left\{\sum _{i=1}^{m}p_{i}x_{i}+\sum _{i=1}^{m}\summa _ {j=1,i\neq j}^{m}P_{ij}x_{i}x_{j}:\summa _{i=1}^{m}w_{i}=w,m\leq n \höger\}.

Följaktligen har vi det genom dynamisk programmering

f(m)={\begin{cases}\max f(w),f(w-w_{m})+p_{m}+\sum _{i=1}^{m-1} P_{im}x_{i}&{\text{if }}w_{m}\leq w,\\f(w)&{\text{annars.}}\end{cases}}

Observera att denna reviderade algoritm fortfarande körs i $O(Wn^{2})$ medan den bara tar upp $O(Wn)$ minne jämfört med föregående $O(Wn^{2})$ .

Relaterade forskningsämnen

Forskare har studerat 0-1 kvadratiska ryggsäcksproblem i årtionden. Ett fokus är att hitta effektiva algoritmer eller effektiv heuristik, särskilt de med enastående prestanda för att lösa verkliga problem. Förhållandet mellan beslutsversionen och optimeringsversionen av 0-1 QKP bör inte ignoreras när man arbetar med någon av dem. Å ena sidan, om beslutsproblemet kan lösas i polynomtid, kan man hitta den optimala lösningen genom att tillämpa denna algoritm iterativt. Å andra sidan, om det finns en algoritm som kan lösa optimeringsproblemet effektivt, då kan det användas för att lösa beslutsproblemet genom att jämföra input med det optimala värdet.

Ett annat tema i litteraturen är att identifiera vad som är de "svåra" problemen. Forskare som studerar 0-1 QKP utför ofta beräkningsstudier för att visa överlägsenheten hos deras strategier. Sådana studier kan också göras för att bedöma prestanda hos olika lösningsmetoder. För 0-1 QKP förlitar sig dessa beräkningsstudier ofta på slumpmässigt genererade data, introducerade av Gallo et al. I princip varje beräkningsstudie av 0-1 QKP använder data som genereras slumpmässigt enligt följande. Vikterna är heltal hämtade från en enhetlig fördelning över intervallet [1, 50], och kapacitetsbegränsningarna är ett heltal taget från en enhetlig fördelning mellan 50 och summan av artikelvikter. De objektiva koefficienterna, dvs värdena är slumpmässigt valda från [1 100]. Det har observerats att generering av instanser av denna form ger problem med mycket varierande och oförutsägbar svårighet. Därför kan de beräkningsstudier som presenteras i litteraturen vara osunda. Vissa undersökningar syftar därför till att utveckla en metod för att generera instanser av 0-1 QKP med en förutsägbar och konsekvent svårighetsgrad.

Se även

Anteckningar

externa länkar