Kolumngenerering

Kolumngenerering eller fördröjd kolumngenerering är en effektiv algoritm för att lösa stora linjära program .

Den övergripande tanken är att många linjära program är för stora för att explicit överväga alla variabler. Tanken är alltså att börja med att lösa det betraktade programmet med endast en delmängd av dess variabler. läggs variabler som har potential att förbättra målfunktionen till programmet. När det är möjligt att påvisa att lägga till nya variabler inte längre skulle förbättra värdet av den objektiva funktionen, stoppas proceduren. Förhoppningen när man tillämpar en kolumngenereringsalgoritm är att endast en mycket liten del av variablerna kommer att genereras. Denna förhoppning stöds av det faktum att i den optimala lösningen kommer de flesta variabler att vara icke-grundläggande och anta värdet noll, så den optimala lösningen kan hittas utan dem.

I många fall tillåter denna metod att lösa stora linjära program som annars skulle vara svårhanterliga. Det klassiska exemplet på ett problem där det framgångsrikt används är styckningsbeståndsproblemet . En speciell teknik inom linjär programmering som använder denna typ av tillvägagångssätt är Dantzig-Wolfe-sönderdelningsalgoritmen . Dessutom har kolumngenerering tillämpats på många problem som besättningsschemaläggning , fordonsdirigering och det kapaciterade p-medianproblemet.

Algoritm

Algoritmen tar hänsyn till två problem: huvudproblemet och delproblemet. Huvudproblemet är det ursprungliga problemet med endast en delmängd av variabler som beaktas. Delproblemet är ett nytt problem skapat för att identifiera en förbättrad variabel ( dvs. som kan förbättra huvudproblemets objektiva funktion) .

Algoritmen fortsätter sedan enligt följande:

1. Initiera huvudproblemet och delproblemet
2. Lös huvudproblemet
3. Sök efter en förbättrad variabel med delproblemet
4. Om en förbättrad variabel hittas: lägg till den i huvudproblemet och gå sedan till steg 2
5. Annars: Lösningen av masterproblemet är optimal. Sluta.

Att hitta en förbättrad variabel

Den svåraste delen av denna procedur är hur man hittar en variabel som kan förbättra huvudproblemets objektiva funktion . Detta kan göras genom att hitta variabeln med den mest negativa reducerade kostnaden (förutsatt att problemet är ett minimeringsproblem utan förlust av allmänhet) . Om ingen variabel har en negativ reducerad kostnad, är den nuvarande lösningen av huvudproblemet optimal.

När antalet variabler är mycket stort är det inte möjligt att hitta en förbättrande variabel genom att beräkna all reducerad kostnad och välja en variabel med negativ reducerad kostnad. Därför är tanken att endast beräkna den variabel som har den lägsta reducerade kostnaden. Detta kan göras med hjälp av ett optimeringsproblem som kallas prissättningsproblemet som starkt beror på strukturen av det ursprungliga problemet. Delproblemets objektiva funktion är den reducerade kostnaden för den sökta variabeln i förhållande till de aktuella dubbla variablerna, och begränsningarna kräver att variabeln följer de naturligt förekommande begränsningarna. Kolumngenereringsmetoden är särskilt effektiv när denna struktur gör det möjligt att lösa delproblemet med en effektiv algoritm, vanligtvis en dedikerad kombinatorisk algoritm .

Vi beskriver nu hur och varför man beräknar den reducerade kostnaden för variablerna. Betrakta följande linjära program i standardform:

${\begin{aligned}&\min _{x}c^{T}x\\&{\text{underkastat}}\\ &Ax=b\\&x\in \mathbb {R} ^{+}\end{aligned}}$

som vi kommer att kalla det primära problemet såväl som dess dubbla linjära program :

${\begin{aligned}&\max _{u}u^{T}b\\&{\text{underkastat}}\\ &u^{T}A\leq c\\&u\in \mathbb {R} \end{aligned}}$

Låt dessutom $x^{*}$ och $u^{*}$ vara optimala lösningar för dessa två problem som kan tillhandahållas av vilken linjär lösare som helst. Dessa lösningar verifierar begränsningarna för deras linjära program och har, genom dualitet , samma värde av objektiv funktion ( $c^{T}x^{*}=u^{*T }b$ ) som vi kallar $z^{*}$ . Detta optimala värde är en funktion av de olika koefficienterna för det primära problemet: $z^{*}=z^{*}(c,A,b)$ . Observera att det finns en dubbel variabel $u_{i}^{*}$ för varje begränsning av den primära linjära modellen. Det är möjligt att visa att en optimal dubbelvariabel $u_{i}^{*}$ kan tolkas som den partiella derivatan av det optimala värdet $z^{*}$ för målet funktion med avseende på koefficienten $b_{i}$ på den högra sidan av begränsningarna: $u_{i}^{*}={\ frac {\partial z^{*}}{\partial b_{i}}}$ ou encore $u^{*}={\frac {\partial z^{*} }{\partial b}}$ . Enklare uttryckt, $u_{i}^{*}$ indikerar med hur mycket som lokalt ökar det optimala värdet för objektivfunktionen när koefficienten $b_{i}$ ökar med en enhet.

Tänk nu på att en variabel $y$ inte beaktades förrän då i det primära problemet. Observera att detta motsvarar att säga att variabeln $y$ fanns i modellen men tog ett nollvärde. Vi kommer nu att observera effekten på det primära problemet med att ändra värdet på $y$ från $0$ till ${\hat {y}}$ . Om $c_{y}$ och $A_{y}$ är respektive koefficienter som är associerade med variabeln $y$ i objektivfunktionen och i begränsningarna så ändras det linjära programmet som följer:

${\begin{aligned}&\min _{x}c^{T}x+c_{ y}{\hat {y}}\\&{\text{underkastat}}\\&Ax=b-A_{y}{\hat {y}}\\&x\in \mathbb {R} ^{+ }\end{aligned}}$

För att veta om det är intressant att lägga till variabeln $y$ till problemet ( dvs för att låta det ta ett värde som inte är noll), vill vi veta om värdet $z_{ \hat {y}}^{*}$ för objektivfunktionen för detta nya problem minskar när värdet ${\hat {y}}$ för variabeln $y$ ökar. Med andra ord vill vi veta ${\frac {dz_{\hat {y}}^{*}}{d{\hat {y}}}}$ . För att göra detta, notera att $z_{\hat {y}}^{*}$ kan uttryckas enligt värdet av den objektiva funktionen för det initiala primala problemet: $z_{\hat {y}}^{*}=c_{y}{\hat {y}}+z^{*} (c,A,b-A_{y}{\hat {y}})$ . Vi kan sedan beräkna det derivat som intresserar oss:

${\begin{ aligned}{\frac {dz_{\hat {y}}^{*}}{d{\hat {y}}}}&~=~&&{\frac {\partial z_{\hat {y}}^ {*}}{\partial {\hat {y}}}}+{\frac {dz^{*}}{d{\hat {y}}}}\\&~=~&&c_{y}+{ \frac {\partial z^{*}}{\partial c}}{\frac {dc}{d{\hat {y}}}}+{\frac {\partial z^{*}}{\partial A}}{\frac {dA}{d{\hat {y}}}+{\frac {\partial z^{*}}{\partial b}}{\frac {db}{d{\hat {y}}}}\\&~=~&&c_{y}+{\frac {\partial z^{*}}{\partial b}}{\frac {db}{d{\hat {y}} }}\\&~=~&&c_{y}+u^{*}(-A_{y})\\&~=~&&c_{y}-u^{*}A_{y}\end{aligned} }$

Med andra ord, effekten av att ändra värdet ${\hat {y}}$ på värdet $z_{\hat {y}}^{*}$ översätts till två termer . För det första påverkar denna förändring direkt objektivfunktionen och för det andra modifieras den högra sidan av begränsningarna vilket påverkar de optimala variablerna $x^{*}$ vars storlek mäts med hjälp av de dubbla variablerna $u^{*}$ . Derivatan ${\displaystyle {\frac {dz_{\hat {y}}^{*}}{d{\hat {y}}}}} kallas i allmänhet den$ reducerade kostnaden för variabeln $y$ och kommer att betecknas med $cr_{y}$ i det följande.