branch and price
Főnév
branch and price (tsz. branch and prices)
- (informatika) Branch-and-Price egy fejlett kombinatorikus optimalizálási technika, amely a Branch-and-Bound és a Column Generation módszereket ötvözi. Különösen hatékony olyan nagy méretű egészértékű programozási problémák megoldásában, ahol az összes változó (oszlop) együttes kezelése számításilag lehetetlen lenne.
📦 Lényege röviden
- A Column Generation módszerrel csak azokat a változókat („oszlopokat”) kezeljük, amelyek potenciálisan javítják a megoldást – nem az összeset.
- A Branch-and-Bound a problémát egy döntési fán keresztül oldja meg, elágaztatva és kizárva a nem optimális megoldási ágakat.
- A Branch-and-Price ezeket kombinálja: minden csomópontban (az elágazási fában) a korlátozott oszloptérrel definiált részproblémát oldja meg, amit dinamikusan bővít új oszlopokkal (változókkal) szükség szerint.
🧠 Mikor használjuk?
- Olyan Mixed-Integer Linear Programoknál (MILP), ahol a változók száma exponenciális lehet
- Ütemezési problémák, járműútvonal-problémák (VRP), vágási-készítési problémák (cutting stock)
- Strukturált problémáknál, ahol az alprobléma jól definiálható, pl. dinamikus programozással megoldható
⚙️ Működési lépések
- Master problem (korlátozott):
- Egy inicializált lineáris program kevés (kezdeti) változóval
- Dual értékek alapján alprobléma megoldása:
- Új változót keresünk, ami negatív csökkentett költséggel javíthatja az LP megoldását
- Ha van javító változó, visszatérünk a master problémához → újraoptimalizálás
- Ha nincs több javító változó, az LP optimális (a jelenlegi oszlopokkal)
- Branching:
- Ha az LP megoldás nem egészértékű, elágazunk (pl. x ≤ 0 és x ≥ 1)
- Minden új ágon újra elvégezzük az oszlopgenerálást
- Ismétlés:
- A folyamat addig folytatódik, amíg el nem érjük az egészértékű optimális megoldást
📐 Ábra (szöveges):
Root Node
|
---------------------
| |
Branch 1 Branch 2
| |
Column Gen Column Gen
| |
Optimal? Optimal?
↓ ↓
Integer? Integer?
🧮 Matematikai példa: Cutting Stock
A vágási-készítési probléma során cél, hogy minél kevesebb alapanyagból vágjunk ki adott méretű darabokat:
- A master problem az oszlopokat (vágási mintákat) tartalmazza
- Az alprobléma (pricing problem) egy korlátos hátizsákprobléma, amely a negatív csökkentett költségű mintát keresi
✅ Előnyök
| Előny | Magyarázat |
|---|---|
| ✅ Memóriatakarékos | Csak azokat a változókat használja, amik hasznosak |
| ✅ Skálázható | Kezeli az exponenciálisan sok változót indirekten |
| ✅ Rugalmas | Alprobléma gyakran gyorsan oldható meg külön (pl. DP-vel) |
| ✅ Pontos megoldás | Optimális, egészértékű megoldást ad |
❌ Hátrányok
| Hátrány | Magyarázat |
|---|---|
| ❌ Komplex implementáció | Nehéz jól megírni és karbantartani |
| ❌ Branching és pricing kombinációja bonyolult | A megszorítások hatása az alproblémára nem triviális |
| ❌ LP megoldások száma megnő | Sok újraoptimalizálásra van szükség |
🧩 TL;DR
A Branch-and-Price egy fejlett optimalizálási módszer, amely a Branch-and-Bound és a Column Generation kombinációja. Nagyon hasznos olyan problémák esetén, ahol sok lehetséges változó van, de csak néhányat érdemes ténylegesen használni. Használata bonyolultabb, de sokkal hatékonyabb a klasszikus módszereknél nagy keresési terek esetén.
- branch and price - Szótár.net (en-hu)
- branch and price - Sztaki (en-hu)
- branch and price - Merriam–Webster
- branch and price - Cambridge
- branch and price - WordNet
- branch and price - Яндекс (en-ru)
- branch and price - Google (en-hu)
- branch and price - Wikidata
- branch and price - Wikipédia (angol)