Konfiguration linjärt program

Det linjära konfigurationsprogrammet ( configuration-LP ) är en speciell linjär programmering som används för att lösa kombinatoriska optimeringsproblem . Det infördes i samband med problemet med styckningsbeståndet . Senare har det tillämpats på papperskorgarpackning och jobbschemaläggning . I konfigurations-LP finns det en variabel för varje möjlig konfiguration - varje möjlig multiset av artiklar som kan passa i en enda fack (dessa konfigurationer är också kända som mönster ) . Vanligtvis är antalet konfigurationer exponentiellt i problemstorleken, men i vissa fall är det möjligt att uppnå ungefärliga lösningar med endast ett polynomantal av konfigurationer.

I papperskorgen packning

Den inbyggda LP:n

I soppaketeringsproblemet finns det n artiklar med olika storlekar. Målet är att packa föremålen i ett minsta antal papperskorgar, där varje papperskorg kan innehålla högst B . En möjlig konfiguration är en uppsättning storlekar med summan av högst B .

• Exempel : anta att artikelstorlekarna är 3,3,3,3,3,4,4,4,4,4 och B =12. Sedan är de möjliga konfigurationerna: 3333; 333; 33, 334; 3, 34, 344; 4, 44, 444. Om vi ​​bara hade tre artiklar i storlek 3, kunde vi inte använda 3333-konfigurationen.

Beteckna med S uppsättningen av olika storlekar (och deras antal). Beteckna med C uppsättningen av olika konfigurationer (och deras antal). För varje storlek s i S och konfiguration c i C , ange:

• n _s - antalet föremål i storlek s .
• a _{s , c} - antalet förekomster av storlek s i konfiguration c .
• x _c - en variabel som anger antalet fack med konfiguration c .

Då är konfigurations-LP för bin-packing :

${\text{minimize}}~~~\summa _{c\in C}x_{c}~~~{\text{subject to}}$

$\sum _{c\in C}a_{s,c}x_{c}\geq n_{s}$ för alla s i S (- alla n _s artiklar i storlek s är packade).

$x_{c}\in \{0,\ldots ,n\}$ för alla c i C (- det finns högst n fack totalt, alltså högst n av varje individuell konfiguration).

Konfigurationen LP är ett linjärt heltalsprogram , så i allmänhet är det NP-hårt. Dessutom är även själva problemet i allmänhet mycket stort: ​​det har C- variabler och S- begränsningar. Om den minsta artikelstorleken är eB (för någon bråkdel e i (0,1)), så kan det finnas upp till 1/ e föremål i varje fack, så antalet konfigurationer C ~ S ^{1/ e} , vilket kan vara mycket stor om e är liten (om e betraktas som en konstant, så kan heltal LP lösas genom uttömmande sökning: det finns högst S ^1/e -konfigurationer, och för varje konfiguration finns det högst n möjliga värden, så det finns vid de flesta $n^{S^{1/e}}$ kombinationer att kontrollera. För varje kombination måste vi kontrollera S- begränsningar, så körtiden är ${ \displaystyle S\cdot n^{S^{1/e}}}$ , som är polynom i n när S, e är konstanta).

Emellertid tjänar denna ILP som bas för flera approximationsalgoritmer. Huvudidén med dessa algoritmer är att reducera den ursprungliga instansen till en ny instans där S är liten och e är stor, så C är relativt liten. Sedan kan ILP lösas antingen genom fullständig sökning (om S , C är tillräckligt små), eller genom att koppla upp den till en bråkdel av LP.

Den fraktionerade LP:n

Bråkkonfigurationens LP för bin-packing Det är den linjära programmeringsavslappningen av ovanstående ILP. Den ersätter den sista begränsningen $x_{c}\in \{0,\ldots ,n\}$ med begränsningen $x_{c}\geq 0$ . Med andra ord kan varje konfiguration användas ett bråkdel antal gånger. Avkopplingen presenterades först av Gilmore och Gomory, och den kallas ofta Gilmore-Gomory linjära program .

• Exempel : anta att det finns 31 artiklar i storlek 3 och 7 artiklar i storlek 4, och papperskorgen är 10. Konfigurationerna är: 4, 44, 34, 334, 3, 33, 333. Begränsningarna är [0,0 ,1,2,1,2,3]* x =31 och [1,2,1,1,0,0,0]* x =7. En optimal lösning på fraktionerad LP är [0,0,0,7,0,0,17/3] Det vill säga: det finns 7 fack med konfiguration 334 och 17/3 fack av konfiguration 333. Observera att endast två olika konfigurationer är behövda.

Kort sagt kan bråk-LP:n skrivas på följande sätt:

${\text{minimera}}~~\mathbf {1} \cdot \mathbf {x} ~~~{\text{st}}~~A\mathbf {x} \ geq \mathbf {n} ~~~{\text{and}}~~\mathbf {x} \geq 0$

Där 1 är vektorn (1,...,1) av storlek C , är A en S -för- C- matris där varje kolumn representerar en enda konfiguration, och n är vektorn ( n ₁ ,..., n _S ).

Lösning av bråk-LP

Ett linjärt program utan integralitetsbegränsningar kan lösas i tidspolynom i antalet variabler och begränsningar. Problemet är att antalet variabler i bråkkonfigurationen LP är lika med antalet möjliga konfigurationer, vilket kan vara enormt. Karmarkar och Karp presenterar en algoritm som övervinner detta problem.

Först konstruerar de det dubbla linjära programmet för fraktionell LP:

${\text{maximize}}~~\mathbf {n} \cdot \mathbf {y} ~~~{\text{st}}~~A^{T}\ mathbf {y} \leq \mathbf {1} ~~~{\text{and}}~~\mathbf {y} \geq 0$ .

Den har S- variabler y ₁ ,..., y _S , och C- begränsningar: för varje konfiguration c finns det en begränsning $A^{c}\cdot y\leq 1$ , där $A^{c}$ är kolumnen i A som representerar konfigurationen c . 3Den har följande ekonomiska tolkning. För varje storlek s bör vi fastställa ett icke-negativt pris y _s . Vår vinst är det totala priset på alla varor. Vi vill maximera vinsten med förbehåll för begränsningarna att det totala priset för varor i varje konfiguration är högst 1.

För det andra tillämpar de en variant av ellipsoidmetoden , som inte behöver lista alla begränsningar - det behöver bara ett separationsorakel . Ett separationsorakel är en algoritm som, givet en vektor y , antingen hävdar att det är genomförbart eller hittar en begränsning som den bryter mot. Separationsoraklet för den dubbla LP kan implementeras genom att lösa ryggsäcksproblemet med storlekarna s och värden y : om den optimala lösningen av ryggsäcksproblemet har ett totalt värde som högst 1, så är y genomförbart; om det är större än 1, är än y inte möjligt, och den optimala lösningen av ryggsäcksproblemet identifierar en konfiguration för vilken begränsningen överträds.

För det tredje visar de att man, med en ungefärlig lösning på ryggsäcksproblemet, kan få en ungefärlig lösning på den dubbla LP, och från detta en ungefärlig lösning på den ursprungliga LP; se Karmarkar-Karps bin packningsalgoritmer .

Allt som allt, för varje toleransfaktor h , hittar en grundläggande genomförbar lösning av kostnad som högst LOPT(I) + h , och körs i tid:

$O\left(S^{8}\log {S} \log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh }})\right)$ ,

där S är antalet olika storlekar, n är antalet olika föremål och storleken på det minsta föremålet är eB . Speciellt, om e ≥ 1/ n och h =1, hittar algoritmen en lösning med som mest LOPT+1 fack i tiden: $O\left(S^{8}\log {S}\log ^{2}{n}+S^{4}n\log {S}\log {n}\right)$ . En randomiserad variant av denna algoritm körs under förväntad tid:

$O\left(S^{7}\log {S} \log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh }})\right)$ .

Avrundning av bråk-LP

Karmarkar och Karp vidareutvecklade ett sätt att runda den fraktionerade LP:n till en ungefärlig lösning till den integrerade LP; se Karmarkar-Karps bin packningsalgoritmer . Deras bevis visar att det additiva integralitetsgapet för denna LP är i O(log ² ( n )). Senare förbättrade Hoberg och Rothvoss sitt resultat och bevisade att integralitetsgapet är i O(log( n )). Den mest kända nedre gränsen för integralitetsgapet är en konstant Ω(1). Att hitta det exakta integralitetsgapet är ett öppet problem.

I soptunna täckning

I soptäckningsproblemet finns det n artiklar med olika storlekar. Målet är att packa föremålen i ett maximalt antal papperskorgar, där varje papperskorg ska innehålla minst B . En naturlig konfigurations-LP för detta problem kan vara:

${\text{maximize}}~~\mathbf {1} \cdot \mathbf {x} ~~~{\text{st}}~~A\mathbf {x} \ leq \mathbf {n} ~~~{\text{and}}~~\mathbf {x} \geq 0$

där A representerar alla konfigurationer av objekt med summan av minst B (man kan bara ta inkluderings-minimal konfigurationer). Problemet med denna LP är att det är problematiskt att hantera små föremål i soptunnan, eftersom små föremål kan vara avgörande för den optimala lösningen. Med små föremål tillåtna kan antalet konfigurationer vara för stort även för tekniken med Karmarkar och Karp. Csirik, Johnson och Kenyon presenterar en alternativ LP. Först definierar de en uppsättning objekt som kallas små . Låt T vara den totala storleken på alla små föremål. Sedan konstruerar de en matris A som representerar alla konfigurationer med summa < 2. Sedan betraktar de ovanstående LP med en ytterligare begränsning:

$${\text{maximera}}~~\mathbf {1} \cdot \mathbf {x} ~~{\text{st}}$$

$$A\mathbf {x} \leq \mathbf {n}$$

$$\sum _{c\in C:sum(c)<B}(B- summa(c))\cdot x_{c}\leq T$$

$$\mathbf {x} \geq 0$$

Den extra begränsningen garanterar att det "lediga utrymmet" i papperskorgen kan fyllas av de små föremålen. Dualen i denna LP är mer komplex och kan inte lösas med ett enkelt orakel för separation av ryggsäcksproblem. Csirik, Johnson och Kenyon presenterar en annan metod för att lösa det ungefär tidsexponentiellt i 1/epsilon. Jansen och Solis-Oba presenterar en förbättrad metod för att lösa det ungefär tidsexponentiellt i 1/epsilon.

I maskinschemaläggning

I problemet med schemaläggning av icke-relaterade maskiner finns det några m olika maskiner som bör bearbeta några n olika jobb. När maskin i bearbetar jobb j tar det tid p _{i , j} . Målet är att dela upp jobben mellan maskinerna så att maximal färdigställandetid för en maskin är så liten som möjligt. Beslutsversionen av detta problem är: givet tid T , finns det en partition där färdigställandetiden för alla maskiner är högst T ?

För varje maskin i finns det ändligt många delmängder av jobb som kan bearbetas av maskin i högst T . Varje sådan delmängd kallas en konfiguration för machine i . Beteckna med C _i ( T ) mängden av alla konfigurationer för maskin i , givet tid T . För varje maskin i och konfiguration c i C _i ( T ), definiera en variabel $x_{i,c}$ som är lika med 1 om den faktiska konfigurationen som används i maskin i är c , och 0 annars. Sedan är LP-begränsningarna:

• $\sum _{c\in C_{i}(T)}x_{i,c}=1$ för varje maskin i i 1,.. ., m;
• $\sum _{i=1}^{m}\sum _{c\ni j,c\in C_{i}(T)}x_{i,c}=1$ för varje jobb j i 1,..., n;
• $x_{i,j}\in \{0,1\}$ för varje i , j .

Egenskaper

Integritetsgapet för konfigurations-LP för schemaläggning av icke-relaterade maskiner är 2 .

Se även

• Förpackning av kärl med hög mångfald