Kolonnegenerering - Column generation

Kolonnegenerering eller forsinket kolonnegenerering er en effektiv algoritme for å løse store lineære programmer .

Den overordnede ideen er at mange lineære programmer er for store til å vurdere alle variablene eksplisitt. Forutsetningen er at de fleste variablene vil være ikke-grunnleggende og anta en verdi på null i den optimale løsningen. På grunn av dette trenger bare en delmengde av variabler å bli vurdert i teorien når man skal løse problemet. Kolonnegenerering utnytter denne ideen til å generere bare variablene som har potensial til å forbedre den objektive funksjonen - det vil si å finne variabler med negativ redusert kostnad (forutsatt uten tap av generalitet at problemet er et minimeringsproblem).

Problemet som løses er delt inn i to problemer: hovedproblemet og delproblemet. Hovedproblemet er det opprinnelige problemet med bare en delmengde av variabler som blir vurdert. Delproblemet er et nytt problem opprettet for å identifisere en ny variabel. Den objektive funksjonen til delproblemet er den reduserte kostnaden for den nye variabelen i forhold til de nåværende doble variablene, og begrensningene krever at variabelen overholder de naturlig forekommende begrensningene.

Prosessen fungerer som følger. Masterproblemet er løst - fra denne løsningen er vi i stand til å oppnå doble priser for hver av begrensningene i masterproblemet. Denne informasjonen blir deretter brukt i den objektive funksjonen til delproblemet. Delproblemet er løst. Hvis den objektive verdien av delproblemet er negativ, er det identifisert en variabel med negativ redusert kostnad. Denne variabelen blir deretter lagt til hovedproblemet, og hovedproblemet løses på nytt. Løsning av hovedproblemet vil generere et nytt sett med doble verdier, og prosessen gjentas til ingen negative reduserte kostnadsvariabler er identifisert. Delproblemet returnerer en løsning med ikke-negativ redusert kostnad, vi kan konkludere med at løsningen på masterproblemet er optimal.

I mange tilfeller gjør dette det mulig å løse store lineære programmer som tidligere ble ansett som uoppnåelige. Det klassiske eksemplet på et problem der dette er vellykket brukt er kuttelagerproblemet . En spesiell teknikk i lineær programmering som bruker denne typen tilnærming er dekomponeringsalgoritmen Dantzig – Wolfe . I tillegg har kolonnegenerering blitt brukt på mange problemer som planlegging av mannskap , ruting av kjøretøy og kapasitert p-medianproblem .