Kolonne generasjon

Kolonne generasjon eller forsinket kolonne generasjon 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 må bare en delmengde av variabler vurderes i teorien når man løser problemet. Kolonnegenerering utnytter denne ideen til å generere bare variablene som har potensial til å forbedre objektiv funksjon—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 vurderes. Delproblemet er et nytt problem opprettet for å identifisere en ny variabel. Delproblemets objektive funksjon er den reduserte kostnaden for den nye variabelen med hensyn til de nåværende doble variablene, og begrensningene krever at variabelen overholder de naturlig forekommende begrensningene.

prosessen fungerer som følger. Master problemet er løst—fra denne løsningen, er vi i stand til å få doble priser for hver av begrensningene i master problemet. Denne informasjonen brukes deretter i delproblemets objektive funksjon. Delproblemet er løst. Hvis delproblemets objektive verdi er negativ, er det identifisert en variabel med negativ redusert kostnad. Denne variabelen blir deretter lagt til master problemet, og master problemet er re-løst. Re-løse 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å hovedproblemet er optimal.

i mange tilfeller tillater dette store lineære programmer som tidligere var ansett som vanskelige å bli løst. Det klassiske eksempelet på et problem hvor dette er vellykket brukt, er skjæreproblemet. En spesiell teknikk i lineær programmering som bruker denne typen tilnærming er Dantzig-Wolfe dekomponeringsalgoritmen. I tillegg har kolonnegenerering blitt brukt på mange problemer som mannskapsplanlegging, kjøretøyruting og det kapasiterte p-medianproblemet.

denne matematikkrelaterte artikkelen er foreløpig kort eller mangelfull. Du kan hjelpe Wikipedia ved å utvide Den.