Kolonnegenerering eller doven kolonnegenerering er en effektiv tilgang til at løse store lineære programmeringsproblemer .
Den generelle idé med metoden er, at mange lineære programmeringsproblemer er for store til eksplicit at skrive alle variablerne ud. Da de fleste af variablerne ikke vil indgå i grundlaget, og derfor vil have en værdi på nul i den optimale løsning, er det kun nødvendigt med en delmængde af variablerne for at løse problemet. Kolonnegenerering understøtter denne idé ved kun at generere de variable, der har potentialet til at forbedre den objektive funktion - det vil sige, at der kun søges efter variabler med en negativ reduceret pris (vi antager uden tab af generalitet , at minimeringsproblemet er bliver løst).
Opgaven er delt op i to – hovedopgaven og en delopgave. Hovedproblemet er det oprindelige problem med den antagelse, at kun en delmængde af variabler betragtes. En delopgave er en ny opgave, hvis formål er at finde nye variable. Delproblemets objektive funktion er den reducerede pris for de nuværende dobbelte variable, og begrænsningerne genereres af naturlige begrænsninger på variablerne.
Processen fungerer som følger. Vi løser hovedproblemet, fra løsningen får vi dobbelte variabler for hver begrænsning af det oprindelige problem. Disse oplysninger bruges i delopgavens objektive funktion. Vi løser et delproblem. Hvis delopgavens objektive funktion er negativ, findes en variabel med negativ reduceret pris, og denne variabel lægges til hovedproblemet og den næste løsning af hovedproblemet produceres. Den nye optimale løsning på hovedproblemet vil give nye dobbelte variable, og processen gentages, så længe løsningerne på delproblemet giver negative værdier. Når løsningen af delproblemet giver en positiv værdi af den objektive funktion, kan vi konkludere, at den optimale løsning på hovedproblemet er fundet.
I mange tilfælde tillader denne tilgang at løse store lineære programmeringsproblemer. Et klassisk eksempel på anvendelse af kolonnegenereringsmetoden er indlejringsproblemet . En lineær programmeringsteknik, der bruger den samme tilgang, er Danzig-Wolfe-nedbrydningen . Derudover bruges kolonnegenerering i mange problemer såsom arbejdsplanlægning [1] , routing og det begrænsede p-medianproblem [2] [3] .
Når man løser store problemer ved hjælp af variabel basismetoden (se simpleksmetoden , afsnittet "Variabel basismetode"), opstår et lignende tilfælde ofte, når det er muligt at generere ikke kun kolonner, men også rækker. Variabelbasismetoden bruger det faktum, at i store lineære programmeringsproblemer, hvor de fleste begrænsninger er givet af uligheder, når de fleste begrænsninger ikke en streng begrænsning (en ekstra variabel er ikke lig med nul), hvilket betyder, at en sådan begrænsning kan ikke indgå i den endelige løsning. Ved løsning af problemer ved hjælp af variabel basismetoden kan der løses en delopgave mere - at bestemme outputkolonnen. Ved at bruge denne tilgang er det muligt at løse nogle spilteoretiske problemer (se f.eks. Blotto-spil ), der indeholder millioner af rækker og kolonner.