column generation

Angol

Főnév

column generation (tsz. column generations)

(informatika) A column generation (oszlopgenerálás) egy fejlett matematikai programozási technika, amelyet olyan nagy méretű lineáris vagy egészértékű optimalizálási problémák megoldására használnak, ahol az összes változó (oszlop) egyszerre történő figyelembevétele túlzottan számításigényes lenne.

1. Alapötlet

Ahelyett, hogy az összes döntési változót egyszerre figyelembe vennénk (ami milliós nagyságrendű is lehet), a column generation:

Egy alapmodellből indul (kis számú változóval)
Iteratív módon új oszlopokat (változókat) generál
Csak azokat, amelyek javíthatják az aktuális megoldást

📌 Lényeg: nem kezeljük egyszerre az egész modellt, hanem csak az éppen szükséges részhalmazát.

2. Mikor használjuk?

Nagy skálájú kombinatorikus optimalizálásnál
Ha a változók száma hatalmas, de csak kevés van a megoldásban
Példák:
- Járműútvonal-tervezés (Vehicle Routing Problem, VRP)
- Legénység-beosztás (Crew Scheduling)
- Vágási minták optimalizálása (Cutting Stock Problem)
- Generalizált hozzárendelési problémák (GAP)

3. Hogyan működik?

A módszer Dantzig–Wolfe dekompozíción alapul: a problémát master problémára és subproblemre bontja.

Folyamat lépésről lépésre:

Master Problem (MP):
- A fő lineáris programozási modell, kis számú oszloppal (kezdő megoldás)
- Megoldásával duális árakat nyerünk ki
Pricing Subproblem:
- Megkeresi, hogy van-e olyan új oszlop (változó), amely negatív csökkentett költséggel rendelkezik (→ javíthatja a megoldást)
- Ez gyakran valamilyen kombinatorikus probléma (pl. legrövidebb út, minimális költségű útvonal stb.)
Ha van ilyen oszlop:
- Hozzáadjuk az MP-hez, és újra optimalizálunk
Ha nincs több javítható oszlop → optimális megoldás a relaxált problémára

4. Csökkentett költség (Reduced Cost)

A pricing problem lényege: találni egy oszlopot, aminek csökkentett költsége negatív:

${\bar {c}}_{j}=c_{j}-\sum _{i}\pi _{i}a_{ij}$

– ahol:

${\textstyle c_{j}}$ : új változó célfüggvény-együtthatója
${\textstyle \pi _{i}}$ : a master problémából származó duális változók
${\textstyle a_{ij}}$ : az új oszlop ${\textstyle j}$ -edik oszlopa
${\textstyle {\bar {c}}_{j}}$ : csökkentett költség

Ha ${\textstyle {\bar {c}}_{j}<0}$ : akkor érdemes hozzáadni

5. Végső cél: egészértékű megoldás

A column generation LP-relaxációt old meg. Ha az eredeti probléma egészértékű, akkor:

Branch-and-Price: a branch-and-bound és column generation kombinációja
Használják pl. a járműbeosztás, vágási feladat, utas-kiszolgálás esetén

6. Példa – Cutting Stock Problem

Adott:

Tekercsek hossza: 100 egység
Rendelés:
- 20 db 45 cm-es
- 30 db 36 cm-es
- 40 db 31 cm-es

A kérdés: hány alaptekercs kell a megrendelés kielégítésére?

Megközelítés:

Minden vágási mód = egy „oszlop”
Master problem: minimális számú tekercs (vágási minták lineáris kombinációja)
Pricing problem: új vágási mód keresése → ez knapsack probléma

7. C++ és Python implementáció

A column generation komplex és több szintű: külön LP-solver (pl. Gurobi, CPLEX) és külön subproblem-megoldó kell hozzá.

📌 Pythonban elérhető:

PuLP vagy OR-Tools a master problémához
Egyedi kóddal generált subproblem (pl. dinamikus programozás)

8. Előnyök és hátrányok

✅ Előnyök:

Skálázható: több millió változóra is
Hatékony: csak a „fontos” oszlopokkal dolgozik
Alkalmas kombinatorikus problémákhoz

❌ Hátrányok:

Bonyolult implementáció
Pricing problem gyakran NP-nehéz
LP-megoldások nem mindig egészértékűek

9. Történeti háttér

1954 – George Dantzig és Philip Wolfe dolgozták ki
Az első ipari alkalmazások a telefonhálózatok és szállítás optimalizálása voltak

10. Összefoglalás

Fogalom	Leírás
Column generation	Egy optimalizálási technika, ahol oszlopokat iteratívan generálunk
Master problem	Az aktuális megoldandó LP, csak kevés oszloppal
Pricing problem	Megkeresi a legjobb új változót a duális árak alapján
A cél	A teljes (nagy) LP-re optimális megoldás megtalálása
Típusok	Lineáris, egészértékű, branch-and-price változatok
Felhasználás	Járatbeosztás, vágásoptimalizálás, járműútvonal-tervezés

A column generation különösen akkor hasznos, amikor egy probléma nagyon sok változót tartalmaz, de ezek csak egy része válik aktívvá a megoldásban. Ezzel a technikával óriási optimalizálási feladatokat is kezelhetővé tehetünk.

További információk

column generation - Szótár.net (en-hu)
column generation - Sztaki (en-hu)
column generation - Merriam–Webster
column generation - Cambridge
column generation - WordNet
column generation - Яндекс (en-ru)
column generation - Google (en-hu)
column generation - Wikidata
column generation - Wikipédia (angol)