Kolonnegenerering - Column generation

Kolonnegenerering eller forsinket kolonnegenerering er en effektiv algoritme til løsning af store lineære programmer .

Den overordnede idé er, at mange lineære programmer er for store til eksplicit at overveje alle variablerne. Udgangspunktet er, at de fleste af variablerne vil være ikke-basale og antage en værdi på nul i den optimale løsning. På grund af dette er det kun en delmængde af variabler, der skal overvejes i teorien, når problemet løses. Kolonnegenerering udnytter denne idé til kun at generere de variabler, der har potentialet til at forbedre den objektive funktion - det vil sige at finde variabler med negativt reducerede omkostninger (forudsat uden tab af generalitet at problemet er et minimeringsproblem).

Problemet, der løses, er opdelt i to problemer: masterproblemet og delproblemet. Hovedproblemet er det oprindelige problem, hvor kun en undersæt af variabler overvejes. Underproblemet er et nyt problem oprettet for at identificere en ny variabel. Den objektive funktion af delproblemet er de reducerede omkostninger ved den nye variabel i forhold til de nuværende dobbelte variabler, og begrænsningerne kræver, at variablen overholder de naturligt forekommende begrænsninger.

Processen fungerer som følger. Masterproblemet er løst - fra denne løsning er vi i stand til at opnå dobbeltpriser for hver af begrænsningerne i masterproblemet. Denne information bruges derefter i den objektive funktion af underproblemet. Underproblemet er løst. Hvis den objektive værdi af delproblemet er negativ, er der identificeret en variabel med negativt reducerede omkostninger. Denne variabel føjes derefter til masterproblemet, og masterproblemet løses igen. Genløsning af masterproblemet vil generere et nyt sæt dobbeltværdier, og processen gentages, indtil der ikke identificeres negative reducerede omkostningsvariabler. Underproblemet returnerer en løsning med ikke-negative reducerede omkostninger, vi kan konkludere, at løsningen på masterproblemet er optimal.

I mange tilfælde gør dette det muligt at løse store lineære programmer, der tidligere var blevet betragtet som uhelbredelige. Det klassiske eksempel på et problem, hvor dette med succes anvendes, er skærebeholdningsproblemet . En særlig teknik i lineær programmering, der bruger denne form for tilgang, er nedbrydelingsalgoritmen Dantzig – Wolfe . Derudover er kolonnegenerering blevet anvendt på mange problemer såsom besætningsplanlægning , køretøjsrute og det kapaciterede p-medianproblem .