Förpackning med hög mångfald

Stormångsförpackning är ett specialfall av problem med lagerförpackning , där antalet olika föremålsstorlekar är litet, medan antalet föremål med varje storlek är stort. Medan det allmänna bin-packningsproblemet är NP-hårt , kan inställningen för hög multiplicitet lösas i polynomtid, förutsatt att antalet olika storlekar är en fast konstant.

Problemdefinition

Indata till problemet är positiva heltal:

• d - antalet olika storlekar (även kallat problemets dimension );
• B - behållarens kapacitet.
• s ₁ , ..., s _d - storlekarna. Storleksvektorn betecknas med s .
• n ₁ , ..., n _d - multipliciteterna; n _i är antalet artiklar med storlek s _i . Vektorn av multipliciteter betecknas med n .
  • n anger det totala antalet objekt, det vill säga n = n ₁ +...+ n _d .
  • V betecknar det största heltal som förekommer i beskrivningen av problemet, det vill säga V = max( s ₁ , ..., s _d , n ₁ , ..., n _d , B)

Utgången är en packning - en tilldelning av föremålen till papperskorgar, så att den totala storleken på föremålen i varje papperskorg är högst B , och med förbehåll för detta är antalet papperskorgar så litet som möjligt.

Exempel : anta att d =2, s ₁ =30, s ₂ =40, n ₁ = n ₂ =5, B =120. Så det finns n =10 objekt med storlekarna: 30,30,30,30,30,40,40,40,40,40. Sedan är en möjlig packning: {30,30,30,30}, {40,40,40}, {30,40,40}, som använder 3 fack.

Konfigurationer

En konfiguration är en uppsättning artiklar som får plats i en enda papperskorg. Den kan representeras av en vektor med d heltal, som anger mångfalden av de olika storlekarna i konfigurationen. Formellt definierar vi för varje konfiguration c en heltalsvektor a _c = a _c,1 , ..., a _c,d så att a _c ≤ n och a _c · s ≤ B.

I exemplet ovan är en av konfigurationerna c ={30,40,40}, eftersom 1*30+2*40 ≤ 120. Dess motsvarande vektor är en _c =(1,2). Andra konfigurationsvektorer är (4,0), (3,0), (2,0), (2,1), (1,0), (1,1), (1,2), (0,1) (0,2), (0,3). Om vi ​​bara hade tre föremål i storlek 3, kunde vi inte använda (4,0)-konfigurationen.

Det är möjligt att presentera problemet med hjälp av det linjära konfigurationsprogrammet : för varje konfiguration c finns en variabel xc _. , som anger antalet fack där c används Det totala antalet fack som används är helt enkelt summan av x _c över alla konfigurationer, betecknat med 1 · x . Det totala antalet objekt som används från varje storlek är summan av vektorerna a _c · x _c över alla konfigurationer c. Sedan är problemet att minimera 1 · x så att summan av a _c · x _c , över alla konfigurationer c , är åtminstone n , så att alla artiklar packas.

Algoritmer

Grundläggande algoritmer

Antag först att alla objekt är stora, det vill säga varje s _i är åtminstone e·B för någon bråkdel e >0. Sedan är det totala antalet artiklar i varje fack högst 1/ e , så det totala antalet konfigurationer är högst d ^{1/ e} . Varje konfiguration visas högst n gånger. Därför finns det högst $n^{d^{1/e}}$ kombinationer att kontrollera. För varje kombination måste vi kontrollera d begränsningar (en för varje storlek), så körtiden är ${\displaystyle d\cdot n^{d^{1/e}}} ,$ vilket är polynom i n när d, e är konstanta.

Huvudproblemet med denna algoritm (förutom att den bara fungerar när objekten är stora) är att dess körtid är polynom i n , men längden på ingången (i binär representation) är linjär i log( V ), vilket är av storleksordningen log( n ).

Körtidspolynom i indatastorleken

Filippi och Agnetis presenterade en algoritm som hittar en lösning med som mest OPT+ d -2 bins i tiden O(poly(log V )). Speciellt för d =2 olika storlekar hittar deras algoritm en optimal lösning i tiden O(log V ).

Goemans och Rothvoss presenterade en algoritm för varje fix d , som hittar den optimala lösningen när alla tal är givna i binär kodning. Deras algoritm löser följande problem: givet två d -dimensionella polytoper P och Q , hitta det minsta antalet heltalspunkter i P vars summa ligger i Q . Deras algoritm körs i tid $(\log V)^{2^{O(d)}}$ . Deras algoritm kan anpassas till andra problem, såsom schemaläggning av identiska maskiner och schemaläggning av icke-relaterade maskiner med olika begränsningar.

Avrunda en allmän instans till en instans med hög multiplicitet

Flera approximationsalgoritmer för det allmänna soppackningsproblemet använder följande schema:

• Separera objekten till "small" (mindre än eB , för någon bråkdel e i (0,1)) och "large" (minst eB ).
• Hantera de stora föremålen först:
  • Avrunda föremålsstorlekarna på något sätt, så att antalet olika storlekar som mest är någon konstant d.
  • Lös det resulterande problemet med hög mångfald.
• Fördela de små föremålen girigt , t.ex. Om inga nya papperskorgar skapas är vi klara. Om nya fack skapas betyder det att alla fack (förutom kanske den sista) är fulla upp till minst (1- e ) B . Därför är antalet fack som mest OPT/(1- e )+1 ≤ (1+2 e )OPT+1.

Algoritmerna skiljer sig åt i hur de rundar instansen.

Linjär avrundning

Lueker och de-la-Vega och uppfann idén om adaptiv ingångsavrundning . Ordna föremålen efter deras storlek och gruppera dem i 1/ e ² grupper av kardinalitet ne ² . I varje grupp, avrunda storlekarna uppåt till maxstorleken i gruppen. Nu finns det bara d =1/ e ² olika storlekar. Lösningen med den avrundade instansen är också möjlig för den ursprungliga instansen, men antalet fack kan vara större än nödvändigt. För att kvantifiera förlusten, betrakta instansen avrundad nedåt till den maximala storleken i den föregående gruppen (den första gruppen avrundas nedåt till 0). Den nedrundade instansen D är nästan lika med den avrundade instansen U , förutom att det i D finns några ne ² nollor medan det i U finns några ne ² stora objekt istället; men deras storlek är högst B . Därför kräver U högst 2 fler fack än D ^. Eftersom D kräver färre fack än optimum får vi att Bins( U ) ≤ OPT + ne ² , det vill säga vi har ett additivfel som kan göras så litet som vi vill genom att välja e .

Om alla artiklar är stora (av storleken minst eB ), så innehåller varje fack i OPT högst 1/ e artiklar (med storleken minst eB ), så OPT måste vara minst en . Därför är Bins( U ) ≤ (1+ e )OPT. Efter att ha hanterat de små föremålen får vi som mest $(1+2e)\mathrm {OPT} +1$ .

Geometrisk avrundning

Karmarkar och Karp presenterar en mer effektiv avrundningsmetod som de kallar geometrisk avrundning (i motsats till den linjära avrundningen av de-la-Vega och Lueker). Baserat på dessa innovationer presenterar de en algoritm med körtidspolynom i $n$ och $1/\varepsilon$ . Deras algoritm hittar $\displaystyle \mathrm {OPT} +{\mathcal {O}}(\log ^{2}(\$ lösning med storlek som högst .

Förbättringar

Denna teknik förbättrades senare av flera författare:

• $\displaystyle \mathrm {OPT} +O(\log$ som mest . Hoberg och Rothvoss förbättrade

• ${\displaystyle \mathrm {OPT} +O(\log(\mathrm {OPT} )$ algoritm för att generera en lösning med maximal storlek . Algoritmen är randomiserad och dess körtid är polynom i det totala antalet objekt.

Se även

• Styckningsproblem - liknar kärlförpackning med hög mångfald, men målet är att minimera den totala mängden slöseri med utrymme i varje behållare, snarare än antalet kärl. Dessutom, i vissa varianter, är antalet föremål från varje storlek inte fast, utan kan flyttas mellan vissa givna nedre och övre gränser.