cutting-plane method

Angol

Főnév

cutting-plane method (tsz. cutting-plane methods)

(informatika) A cutting-plane módszer egy klasszikus iteratív eljárás, amelyet egészértékű (integer) vagy vegyes egészértékű (mixed-integer) lineáris programozási feladatok megoldására használnak. Alapötlete az, hogy először megoldjuk a feladat relaxált (egészértékűségi feltételek nélküli) változatát lineáris programozással (LP), majd fokozatosan olyan síkokat („vágásokat”) adunk a megoldáshoz, amelyek kizárják a nem egész értékű megoldásokat, de az összes egész megoldást megtartják. Ezáltal szűkítjük a megoldási tartományt, amíg el nem érünk egy egészértékű optimális megoldást.

🧮 A módszer matematikai alapja

Legyen adott az alábbi lineáris program:

${\text{max/min }}c^{T}x$ ${\text{subject to }}Ax\leq b$ $x\in \mathbb {Z} _{+}^{n}$

Ahol:

${\textstyle x\in \mathbb {Z} _{+}^{n}}$ : az ismeretlenek nemnegatív egészek,
${\textstyle A}$ egy valós ${\textstyle m\times n}$ mátrix,
${\textstyle b\in \mathbb {R} ^{m}}$ , ${\textstyle c\in \mathbb {R} ^{n}}$ .

A relaxált változat:

$x\in \mathbb {R} _{+}^{n}$

📐 Lépések – Hogyan működik a Cutting-Plane módszer?

LP relaxáció megoldása: Megoldjuk az LP-t egész számok megkötése nélkül.
Megvizsgáljuk, hogy az optimális megoldás egész szám-e:
- Ha igen → vége.
- Ha nem → megyünk tovább.
Vágás (cut) generálása: Olyan lineáris egyenlőtlenséget konstruálunk, amelyet az aktuális nem egészértékű megoldás nem elégít ki, de az összes lehetséges egész megoldás igen.
Egyenlőtlenség hozzáadása a korlátozásokhoz: Az új korlátozással új LP-t kapunk.
Ismétlés: A fenti lépéseket ismételjük, amíg egész megoldást nem kapunk.

📏 Mi az a vágás?

A vágás olyan egyenlőtlenség, amely:

Kizárja a nem kívánt (nem egész) LP-megoldást.
Megőrzi az eredeti egész megoldásokat.
Formálisan: ha ${\textstyle P=\{x\in \mathbb {R} ^{n}:Ax\leq b\}}$ , és ${\textstyle P_{I}={\text{konvex burka}}\{x\in P:x\in \mathbb {Z} ^{n}\}}$ , akkor egy vágás olyan egyenlőtlenség, amely ${\textstyle x^{*}\notin P_{I}}$ , de minden egész ${\textstyle x\in P}$ esetén teljesül.

🧠 A legismertebb vágások: Gomory vágások

A Gomory-féle cutting-plane módszer az egyik legismertebb algoritmus. A simplex tábla alapján generál vágásokat, mikor a nem egész változók értékei frakciókat tartalmaznak.

Gomory-féle frakcionális vágás:

Megkeressük azt a sort a simplex táblában, ahol a jobboldali érték (bázismegoldás) nem egész.
Az ebből a sorból származtatott egyenlőtlenség kizárja az aktuális frakcionális megoldást.
Hozzáadjuk ezt az egyenlőtlenséget a korlátozásokhoz.

🛠️ Példa

Tegyük fel, hogy megoldottuk az LP-t, és a megoldás: ${\textstyle x_{1}=2.5,x_{2}=3}$

Ez nem elfogadható, mert ${\textstyle x_{1}}$ nem egész. A Gomory-vágás a simplex tábla alapján előállít egy olyan új feltételt (pl. ${\textstyle 0.5x_{1}+0.5x_{2}\leq 2}$ ), amely kizárja ezt az aktuális megoldást.

📚 Előnyök

Pontos módszer: ha végtelen számú vágás hozzáadását engednénk meg, az egész számú megoldáshoz konvergál.
LP-algoritmusokkal kompatibilis: a vágások után ismét LP-t oldunk meg.
Szemléletes geometria: a feasible régiót fokozatosan „levágjuk”.

🧱 Hátrányok

Numerikus instabilitás: frakcionális együtthatók miatt.
Lassú konvergencia: sok vágás szükséges lehet.
Nagy LP-táblák: minden új vágás új sor a mátrixban → nő a számítási idő.

🧮 Összevetés más módszerekkel

Módszer	Jellemzők
Cutting-plane	Geometriai levágások, LP újraszámítás
Branch and Bound	Teljes fa bejárás, részproblémák felosztása
Branch and Cut	Cutting-plane + Branch and Bound kombinációja
Heurisztikus módszerek	Gyors, de nem garantáltan optimális

🔧 Cutting-plane programozási megoldásban

A vágások számítása általában LP-szoftverekre (pl. CPLEX, Gurobi) van bízva. De manuálisan is kiszámolhatóak a frakcionális részek alapján.

# Egyszerű példa egy Gomory-vágásra
x1 = 2.5
vagas = x1 - int(x1)  # 0.5 → ez alapján készítjük a vágást

🧾 Összefoglalás

A cutting-plane módszer egy hatékony és elméletileg megalapozott technika az egészértékű programozásban. Bár a modern megoldók gyakran kombinálják más módszerekkel, például Branch and Bound-dal, a vágások szerepe továbbra is központi az optimalizálásban. A módszer lépésről lépésre pontosítja az LP-megoldást az egész megoldás felé, mindig megőrizve a lehetséges integer megoldásokat.

További információk

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