Az oszlopgenerálás vagy lusta oszlopgenerálás hatékony módszer a nagy lineáris programozási problémák megoldására .
A módszer általános ötlete az, hogy sok lineáris programozási probléma túl nagy ahhoz, hogy az összes változót kifejezetten kiírja. Mivel a változók többsége nem fog szerepelni a bázisban, és ezért az optimális megoldásban nulla lesz, a probléma megoldásához csak a változók egy részhalmaza szükséges. Az oszlopgenerálás alátámasztja ezt az elképzelést azzal, hogy csak azokat a változókat generálja, amelyekben megvan a lehetőség a célfüggvény javítására – vagyis csak a negatívan csökkentett költségű változókat keresi ( az általánosság elvesztése nélkül feltételezzük , hogy a minimalizálási probléma megoldás alatt).
A feladat két részre oszlik - a fő feladatra és egy részfeladatra. A fő probléma az eredeti probléma azzal a feltételezéssel, hogy a változóknak csak egy részhalmazát veszik figyelembe. A részfeladat egy új feladat, melynek célja új változók keresése. A részprobléma célfüggvénye az aktuális kettős változók csökkentett ára, a korlátokat pedig a változók természetes korlátai generálják.
A folyamat a következőképpen működik. Megoldjuk a fő problémát, a megoldásból kettős változót kapunk az eredeti feladat minden kényszeréhez. Ezt az információt a részfeladat célfüggvényében használjuk fel. Megoldunk egy részproblémát. Ha a részfeladat célfüggvénye negatív, akkor egy negatív csökkentett árú változót találunk, és ezt a változót hozzáadjuk a fő problémához, és előállítjuk a fő probléma következő megoldását. A fő probléma új optimális megoldása új kettős változókat ad, és a folyamat mindaddig ismétlődik, amíg a részprobléma megoldásai negatív értékeket adnak. Ha a részprobléma megoldása a célfüggvény pozitív értékét adja, akkor arra a következtetésre juthatunk, hogy a fő probléma optimális megoldását megtaláltuk.
Ez a megközelítés sok esetben nagy lineáris programozási problémák megoldását teszi lehetővé. Az oszlopgenerálási módszer alkalmazásának klasszikus példája a beágyazási probléma . Az egyik lineáris programozási technika, amely ugyanezt a megközelítést használja, a Danzig-Wolfe-felbontás . Ezen túlmenően az oszlopgenerálást számos probléma esetén használják, mint például a munkaütemezés [1] , az útválasztás és a kényszerített p-medián probléma [2] [3] .
Ha nagy problémákat old meg változó bázis módszerrel (lásd a szimplex módszer , "Változó bázis módszer" fejezet), gyakran előfordul hasonló eset, amikor nem csak oszlopokat, hanem sorokat is lehet generálni. A változó bázis módszer azt a tényt használja ki, hogy a nagy lineáris programozási feladatokban, amelyekben a legtöbb megszorítást egyenlőtlenségek adják, a legtöbb megszorítás nem ér el szigorú korlátot (egy további változó nem egyenlő nullával), ami azt jelenti, hogy egy ilyen megszorítás nem lehet figyelembe venni a végső megoldásban. A változó bázis módszerrel történő feladatok megoldása során még egy részfeladat megoldható - a kimeneti oszlop meghatározása. Ezzel a megközelítéssel megoldható néhány játékelméleti probléma (lásd például Blotto játékok ), amelyek több millió sort és oszlopot tartalmaznak.