Oszlop generáció - Column generation

Oszlopgenerálás vagy késleltetett oszlopgenerálás hatékony algoritmus nagy lineáris programok megoldására .

Átfogó gondolat, hogy sok lineáris program túl nagy ahhoz, hogy az összes változót kifejezetten figyelembe vegyük. Az előfeltétel az, hogy a változók nagy része nem alapszintű lesz, és az optimális megoldásnál nulla értéket vesz fel. Emiatt elméletben csak a változók egy részhalmazát kell figyelembe venni a probléma megoldása során. Az oszlopgenerálás felhasználja ezt az ötletet, hogy csak azokat a változókat hozza létre, amelyek javíthatják a célfüggvényt - vagyis negatív, csökkentett költségű változókat találnak (feltételezve, hogy az általánosság vesztesége nélkül a probléma minimalizálási probléma).

A megoldandó probléma két problémára oszlik: a főproblémára és az alproblémára. A fő probléma az eredeti probléma, a változóknak csak egy részét veszik figyelembe. Az alprobléma egy új probléma, amelyet egy új változó azonosítására hoztak létre. Az alprobléma célfüggvénye az új változó csökkentett költsége a jelenlegi kettős változókhoz képest, és a megszorítások megkövetelik, hogy a változó engedelmeskedjen a természetesen előforduló kényszereknek.

A folyamat a következőképpen működik. A fő probléma megoldódott - ebből a megoldásból kettős árat tudunk szerezni a fő probléma mindegyik korlátjára. Ezt az információt ezután felhasználják az alprobléma célfüggvényében. Az alprobléma megoldódott. Ha az alprobléma objektív értéke negatív, akkor egy negatív, csökkentett költségű változót azonosítottak. Ez a változó hozzáadódik a főproblémához, és a főprobléma újra megoldódik. A fő probléma újbóli megoldása új kettős értékkészletet generál, és a folyamatot addig ismételjük, amíg nem jeleznek negatív, csökkentett költségű változókat. Az alprobléma nem negatív, csökkentett költségű megoldást ad vissza, arra a következtetésre juthatunk, hogy a master probléma megoldása optimális.

Ez sok esetben lehetővé teszi a korábban vonhatatlannak tartott nagy lineáris programok megoldását. A probléma klasszikus példája, ahol ezt sikeresen alkalmazzák, a vágóállomány-probléma . A lineáris programozás egyik ilyen technikája, amely ezt a fajta megközelítést használja, a Dantzig – Wolfe bontási algoritmus. Ezenkívül az oszlopgenerálást számos problémára alkalmazták, például a személyzet ütemezésére , a járművek útvonaltervezésére és a kapacitált p-medián problémára .