Column generatie - Column generation

Kolomgeneratie of vertraagde kolomgeneratie is een efficiënt algoritme voor het oplossen van grote lineaire programma's .

Het overkoepelende idee is dat veel lineaire programma's te groot zijn om alle variabelen expliciet te beschouwen. Het uitgangspunt is dat de meeste variabelen niet-basis zijn en in de optimale oplossing een waarde van nul aannemen. Daarom hoeft in theorie slechts een subset van variabelen in overweging te worden genomen bij het oplossen van het probleem. Kolomgeneratie maakt gebruik van dit idee om alleen de variabelen te genereren die het potentieel hebben om de doelfunctie te verbeteren - dat wil zeggen: variabelen vinden met negatief gereduceerde kosten (aangenomen zonder verlies van algemeenheid dat het probleem een ​​minimaliseringsprobleem is).

Het op te lossen probleem is opgesplitst in twee problemen: het hoofdprobleem en het subprobleem. Het hoofdprobleem is het oorspronkelijke probleem, waarbij slechts een subset van variabelen in aanmerking wordt genomen. Het subprobleem is een nieuw probleem dat is gecreëerd om een ​​nieuwe variabele te identificeren. De objectieve functie van het subprobleem is de verminderde kosten van de nieuwe variabele met betrekking tot de huidige dubbele variabelen, en de beperkingen vereisen dat de variabele gehoorzaamt aan de natuurlijk voorkomende beperkingen.

Het proces werkt als volgt. Het hoofdprobleem is opgelost - met deze oplossing zijn we in staat om dubbele prijzen te verkrijgen voor elk van de beperkingen in het hoofdprobleem. Deze informatie wordt vervolgens gebruikt in de objectieve functie van het deelprobleem. Het deelprobleem is opgelost. Als de objectieve waarde van het deelprobleem negatief is, is er een variabele met negatieve lagere kosten geïdentificeerd. Deze variabele wordt vervolgens toegevoegd aan het hoofdprobleem en het hoofdprobleem wordt opnieuw opgelost. Door het hoofdprobleem opnieuw op te lossen, wordt een nieuwe set dubbele waarden gegenereerd, en het proces wordt herhaald totdat er geen negatieve variabelen voor lagere kosten worden geïdentificeerd. Het subprobleem levert een oplossing op met niet-negatieve verlaagde kosten, we kunnen concluderen dat de oplossing voor het hoofdprobleem optimaal is.

In veel gevallen kunnen hierdoor grote lineaire programma's die voorheen als hardnekkig werden beschouwd, worden opgelost. Het klassieke voorbeeld van een probleem waarbij dit met succes wordt gebruikt, is het probleem van de snijmaterialen . Een specifieke techniek in lineaire programmering die deze benadering gebruikt, is het Dantzig-Wolfe-decompositie- algoritme. Bovendien is het genereren van kolommen toegepast op veel problemen, zoals planning van de bemanning , routebepaling van voertuigen en het probleem met de capacitieve p-mediaan .