branch and cut

Angol

Főnév

branch and cut (tsz. branch and cuts)

(informatika) A Branch and Cut (rövidítve B&C) egy hatékony kombinatorikus optimalizálási módszer, amelyet elsősorban egészértékű programozási (IP) problémák megoldására fejlesztettek ki. A módszer a Branch and Bound és a Cutting Plane technikák kombinációja, és jelenleg az egyik legfontosabb algoritmus a vegyes egészértékű programozási (MILP) feladatok megoldására.

1. Bevezetés

Sok gyakorlati probléma — például útvonaltervezés, erőforrás-beosztás, ütemezés, hálózattervezés — csak egész megoldásokkal értelmezhető (pl. 3 gép, 1 teherautó, 0 vagy 1 döntés). Ezeket egészértékű programozási problémáknak nevezzük.

Mivel a klasszikus lineáris programozási (LP) technikák valós értékű megoldásokat adnak, a B&C módszer célja: 👉 olyan algoritmus létrehozása, amely garantáltan egész megoldást ad, és hatékonyan szűkíti a keresési teret.

2. Az alapötlet

A Branch and Cut két elvet ötvöz:

Branch and Bound (B&B) – a megoldási tartomány szisztematikus feldarabolása (ágaztatás), és alsó-felső korlátok használata a kizáráshoz.
Cutting Plane (CP) – lineáris egyenlőtlenségek (ún. vágások) hozzáadása a modellhez, hogy kizárjuk a nem-egész, de megengedett LP megoldásokat.

3. A módszer működése – áttekintés

Megoldjuk az LP-relaxációt (azaz elhagyjuk az egészértékűség feltételét).
Ha a megoldás egész, készen vagyunk.
Ha nem:
- Vágásokat generálunk (cutting planes), hogy kizárjuk ezt a nem-egész megoldást, de ne zárjunk ki egyetlen egész megoldást sem.
- Ha vágásokkal sem sikerül egészet találni, akkor:
  - Ágaztatunk (pl. ${\textstyle x_{i}\leq \lfloor x_{i}^{*}\rfloor }$ és ${\textstyle x_{i}\geq \lceil x_{i}^{*}\rceil }$ )
  - Rekurzívan alkalmazzuk a módszert az új résztartományokra.
A fastruktúrát (branching tree) járjuk be, miközben vágásokat is adunk hozzá minden csomópontban → ez a Branch and Cut.

4. Cutting Plane – részletezve

A cutting plane technika célja, hogy kizárja az LP relaxáció frakcionált (nem-egész) megoldását egy új egyenlőtlenséggel, amely:

Minden egész megoldásra teljesül
Az aktuális frakcionált megoldásra nem

Ezek a vágások (cuts) lehetnek:

Gomory-vágások
Cover inequalities
Clique cuts
Flow cover inequalities
Lift-and-project cuts

A vágások célja tehát: “megszorítani” a megoldásteret anélkül, hogy elveszítenénk a lehetséges egész megoldásokat.

5. Branching – részletezve

Ha a vágások sem hoztak egész megoldást, elágaztatunk egy változó szerint. Példa:

Ha ${\textstyle x_{3}=4.7}$ ${\textstyle x_{3}=4.7}$ az LP-ben, akkor két részproblémára bontunk:
1. ${\textstyle x_{3}\leq 4}$
2. ${\textstyle x_{3}\geq 5}$

Minden részproblémában újra alkalmazzuk a cutting plane módszert. Ezzel fokozatosan kizárjuk az összes nem-egész megoldást, miközben végül megtaláljuk az optimális egész értéket.

6. Algoritmus ábrája

               Root Node (LP relaxation)
                       ↓
                Frakcionált megoldás?
                  /           \
                igen           nem → kész
               /     
      Cutting plane-ek
       (új LP megoldás)
              |
        Frakcionált?
         /       \
       igen       nem → kész
       |
   Ágaztatás (Branch)
  /                \
Bal ág         Jobb ág
 ↓                ↓
Rekurzív B&C  Rekurzív B&C

7. Példa

0-1 hátizsák probléma (Knapsack problem):

Adott tárgyak: súly, érték
Kapacitás: 10
Cél: érték maximalizálása

LP-relaxáció eredménye lehet: ${\textstyle x_{1}=1,x_{2}=0.8,x_{3}=0}$ Mivel ${\textstyle x_{2}}$ nem bináris, vágással kizárjuk ezt. Ha vágás nem elég → ágaztatás: ${\textstyle x_{2}=0}$ és ${\textstyle x_{2}=1}$

8. Előnyök

✅ Nagy hatékonyság komplex IP/MILP problémákra ✅ Optimalitás garantált ✅ Használható sokféle ipari probléma esetén (pl. logisztika, hálózat, pénzügy) ✅ Rugalmas: vágások hozzáadása testreszabható

9. Hátrányok

⚠️ Bonyolult implementáció ⚠️ Vágások generálása nem mindig triviális ⚠️ Nagy számítási idő bizonyos esetekben (NP-nehéz problémák)

10. Szoftverek és megvalósítások

A legtöbb modern MILP-megoldó Branch and Cut algoritmust használ:

CPLEX
Gurobi
SCIP
GLPK
CBC (Coin-or)

Ezek belsőleg generálják a megfelelő vágásokat és kezelik az elágaztatási fát.

11. Kapcsolódó technikák

Branch and Bound – vágások nélkül, csak elágazással dolgozik
Cutting Plane Method – vágásokat használ, de nem ágaztat
Branch and Price – vágások helyett oszlopgenerálással dolgozik (pl. járműútvonal probléma)
Branch and Heuristic – közelítő megoldásokhoz

12. Összefoglalás

A Branch and Cut egy intelligens, kombinált algoritmus, amely képes nagy és bonyolult egészértékű optimalizálási problémák megoldására. Ez a módszer:

A valós LP-megoldások gyors kiszámítására épít,
Célzott vágásokkal szűkíti a megoldásteret,
És ágaztatással biztosítja, hogy minden lehetséges esetet lefedjen.

Ennek köszönhetően a B&C algoritmus a világ egyik legerősebb optimalizálási eszköze, amely szinte minden ipari területen használható a döntéshozatal támogatására.

További információk

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