Generování sloupců - Column generation

Generování sloupců nebo generování zpožděných sloupců je efektivní algoritmus pro řešení velkých lineárních programů .

Zastřešující myšlenka je, že mnoho lineárních programů je příliš velkých na to, aby explicitně zvážily všechny proměnné. Předpokladem je, že většina proměnných bude nepodstatná a v optimálním řešení předpokládá hodnotu nula. Z tohoto důvodu je při řešení problému potřeba teoreticky uvažovat pouze o podmnožině proměnných. Generování sloupců využívá tuto myšlenku ke generování pouze proměnných, které mají potenciál zlepšit objektivní funkci - to znamená k vyhledání proměnných se záporně sníženými náklady (za předpokladu, bez ztráty obecnosti , že problém je problémem minimalizace).

Řešení problému se dělí na dva problémy: hlavní problém a dílčí problém. Hlavní problém je původní problém, přičemž se uvažuje pouze s podmnožinou proměnných. Subproblem je nový problém vytvořený k identifikaci nové proměnné. Objektivní funkcí dílčího problému je snížená cena nové proměnné vzhledem k aktuálním duálním proměnným a omezení vyžadují, aby se proměnná řídila přirozeně se vyskytujícími omezeními.

Proces funguje následovně. Hlavní problém je vyřešen - z tohoto řešení jsme schopni získat dvojí ceny pro každé z omezení v hlavním problému. Tyto informace jsou poté využity v objektivní funkci dílčího problému. Podproblém je vyřešen. Pokud je objektivní hodnota dílčího problému záporná, byla identifikována proměnná se záporně sníženou cenou. Tato proměnná se poté přidá k hlavnímu problému a hlavní problém se znovu vyřeší. Opětovné vyřešení hlavního problému vygeneruje novou sadu duálních hodnot a proces se opakuje, dokud nebudou identifikovány žádné negativní proměnné se sníženými náklady. Subproblem vrací řešení s nezápornou sníženou cenou, můžeme dojít k závěru, že řešení hlavního problému je optimální.

V mnoha případech to umožňuje řešení velkých lineárních programů, které byly dříve považovány za neřešitelné. Klasickým příkladem problému, kde se tento problém úspěšně používá, je problém řezného materiálu . Jednou z konkrétních technik lineárního programování, která využívá tento druh přístupu, je Dantzig-Wolfeův rozkladový algoritmus. Generování sloupců bylo navíc aplikováno na mnoho problémů, jako je plánování posádky , směrování vozidel a problém kapacitního p-mediánu .