A Balas-féle elágazás és vágás algoritmus

Farkas Gyula

Témavezető: Vizvári Béla docens

Contents

1 Bevezetés 3 1.1 Optimalizálási feladatok . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Megoldási módszerek, terminológia . . . . . . . . . . . . . . . . . . . 4

2 Lineáris egyenlőtlenségek R^{n}-en 7 2.1 Konvex halmazok, konvex burok . . . . . . . . . . . . . . . . . . . . . 7 2.2 Poliéderek, kúpok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Merőleges vetítés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3 Projekció és konvexifikáció 11 3.1 A szekvenciális konvexifikáció . . . . . . . . . . . . . . . . . . . . . . 11 3.2 A Lovász-Schrijver konstrukció . . . . . . . . . . . . . . . . . . . . . 14 3.3 A Sherali-Adams konstrukció . . . . . . . . . . . . . . . . . . . . . . 15 3.4 Kapcsolat a diszjunktív programozással . . . . . . . . . . . . . . . . . 16 3.5 Alkalmazás kombinatorikus problémára . . . . . . . . . . . . . . . . . 21

4 Vágás típusú algoritmusok 25 4.1 Az általános eljárás . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2 A végesség bizonyítása . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.3 Vágások a bázis inverzéből . . . . . . . . . . . . . . . . . . . . . . . . 30 4.4 Vágások élesítése . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

5 A Branch-and-Cut algoritmus 37 5.1 Branch-and-Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.2 Az elágazás és vágás algoritmus . . . . . . . . . . . . . . . . . . . . . 39 5.3 Vágások generálása, felemelése . . . . . . . . . . . . . . . . . . . . . . 41 5.4 Az “Elágazás vagy vágás?” probléma . . . . . . . . . . . . . . . . . . 48 5.5 Leszámlálási stratégiák . . . . . . . . . . . . . . . . . . . . . . . . . . 50 5.6 Konklúzió . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

Irodalomjegyzék 54

Chapter 1

Bevezetés

A dolgozat célja, hogy bemutasson egy új algoritmust, mely képes megoldani az egyik legnehezebben kezelhető optimalizálási problémát, nevezetesen a vegyes programozási feladatot. Az ismertetendő algoritmus úgynevezett vágás típusú algoritmus.

A célunk eléréséhez megvizsgálnunk bizonyos lineáris egyenlőtlenség-rendszerrel leírt R^{n}-beli ponthalmazokat, majd megadunk egy eljárást, mely alkalmas halmazok konvex burkának meghatározására. Az eljárás során kapott egyenlőtlenségeket használjuk majd, mint vágó síkokat. Ezek után már megfogalmazhatjuk az új vágás típusú algoritmust, melyről belátjuk, hogy véges sok lépés után befejeződik.

Megmutatjuk még, hogy az általunk ismertett vágásokat hogyan építhetjük be az úgynevezett Branch-and-Bound algoritmus keretei közé. Így egy igen hatékony algoritmust nyerhetünk a vegyes programozási feladat megoldására.

1.1 Optimalizálási feladatok

Nagyon sok gyakorlati probléma vezet a matematikai modellezés után valamilyen optimalizálási feladatra. Ha a kapott feltételek lineárisak, az optimalizálni kívánt célfüggvény is lineáris, valamint minden változó folytonosan változhat, tehát lineáris programozási feladatról van szó, akkor a jól ismert elmélet szerint a megoldást gyorsan megkaphatjuk. Abban az esetben viszont, amikor egy lineáris programozási feladatban szereplő változók némelyikére egészértékűségi feltételeket teszünk, akkor a megoldás megtalálása nehéz probléma.

Az optimalizálási feladatok egyik legáltalánosabb alakja a következő:

min f(x)  (1)
x ∈ D,

ahol f : R^{n} ⟶ R adott függvény, D ⊆ R^{n} adott halmaz. Az f függvényt \underline{célfüggvény}nek hívjuk, az x ∈ D pontok neve pedig \underline{megengedett megoldás}. Itt és a továbbiakban mindig minimalizálni szeretnénk a célfüggvényt, de megemlítjük, hogy ez nem jelenti az általánosság megszorítását, hiszen f maximalizálása ekvivalens −f minimalizálásával.

Mi a vegyes programozási feladatot fogjuk vizsgálni, azaz a problémánk a következő:

min{cx : Ax ≥ b, x ≥ 0, x_{j} ∈ {0, 1}, j = 1, …, p},  (2)

ahol c egy adott R^{n}-beli vektor, A egy n × m-es mátrix, b pedig egy R^{m}-beli vektor. Itt tehát az f egy lineáris függvény és a D halmazt is lineáris egyenlőtlenségek definiálják, viszont az első p koordináta csak 0 vagy 1 lehet, ahol persze p < n. Ha p = n, akkor egészértékű vagy diszkrét programozási feladatról beszélünk. A diszkrét illetve vegyes programozási feladatokban a nehézséget az jelenti, hogy a megengedett megoldások halmazát nehezen tudjuk előállítani. Ha valahogy ez mégis sikerülne, lényegében megoldanánk a problémát. Számos módszer ismert diszkrét programozási feladatok egzakt megoldására. Mivel mindkét probléma NP-teljes, a módszerek mindegyike valamilyen értelemben leszámlálási módszer. Ezekről ad jó összefoglalást a [12] jegyzet, illetve a [10] könyv. A következő szakaszban röviden összefoglaljuk a szokásos terminológiát és megoldási módszereket.

1.2 Megoldási módszerek, terminológia

Előzetesen kijelenthetjük, hogy minden külön nem jelölt vektort R^{n}-belinek tekintünk. Ahogy az előző szakaszban is említettük, a diszkrét illetve általánosabban a vegyes programozási feladat megoldásának nehézségét a megengedett megoldások leírásának nehézsége okozza. Ezért egy járható út az, hogy a megengedett megoldások halmazánál nagyobb halmazon végezzük el először a célfüggvényünk minimalizálását, ami lényegesen könnyebb feladat, ha okosan választjuk a nagyobb halmazt. Ezt az eljárást relaxációnak nevezik. Ha az így nyert megoldás megengedett az eredeti feladatban is, akkor azt meg is oldottuk. Ha viszont nem megengedett, akkor választhatjuk azt a lehetőséget, hogy a nagyobb halmazt, azaz a relaxációt szűkítjük oly módon, hogy az előbb nyert megoldás már ne legyen benne ebben a szűkebb halmazban, de viszont úgy, hogy ezt a szűkebb halmazt is könnyen tudjuk kezelni.

Gyakran használt relaxáció a lineáris programozási (röviden LP) relaxáció. Ekkor a nehezen kezelhető halmazt egy poliéderbe tesszük, így ezen a nagyobb halmazon történő optimalizálás egy LP-feladatra redukálódik. Egy matemetikai példán világítjuk meg az elmondottakat. Legyen a megoldandó diszkrét programozási feladatunk a következő:

min{cx : Ax ≥ b, x ∈ {0, 1}^{n}}.

A legnyilvánvalóbb relaxációnak az {x : Ax ≥ b, 0 ≤ x ≤ 1} adódik, ahol 0 az R^{n}-beli nullvektor, 1 pedig az a vektor, melynek minden koordinátája 1. A később ismertetendő algoritmusoknál nehézséget okozna, ha a relaxációban fekvő megengedett megoldások konvex burka nem lenne poliéder. Ilyen eset elő is fordulhat, például irracionális A esetén. Ezért a továbbiakban mindig feltesszük, hogy az adataink racionálisak, ami már garantálni fogja, hogy a megengedett megoldások konvex burka poliéder lesz. E feltevéssel azért sem vesztünk túl sokat, mert a számítógép is csak racionális számokat képes tárolni. A most ismertetett probléma részletesebb tárgyalása megtalálható a [12] jegyzetben.

Visszatérve a relaxációhoz, ha az LP megoldása során nyert megoldás nem megengedett az eredeti problémánkban, akkor a relaxációt úgy kell szűkíteni, hogy a kapott új feladat még mindig LP, azaz viszonylag gyorsan megoldható maradjon. Az egyik legrégebbi módszer szerint egy járható út az, hogy keresünk egy olyan hipersíkot, melynek egyik oldalára esik az aktuálisan nyert megoldás, a másik oldalára pedig ez eredeti feladat összes megengedett megoldása. Ha ezt a félteret meghatározó egyenlőtlenséget a relaxációban használt poliédert definiáló egyenlőtlenségekhez csatoljuk, megkapjuk a kívánt szűkebb relaxációt. A fenti módszerre alapozható olyan algoritmus, mely megoldja a diszkrét programozási feladatot. Az ilyen algoritmus neve: vágás típusú algoritmus, utalva arra, hogy a hipersíkkal “levágjuk” azt az aktuális megoldást, mely nem megengedett az eredeti feladatban, de persze úgy, hogy megtartjuk az összes megengedett megoldást.

Hasonló elvet követő algoritmust fogunk megfogalmazni a nehezebb vegyes programozási feladatra. Az itt használt vágásokat beépítjük a Branch-and-Bound algoritmusba, ezáltal egy igen hatékony, úgynevezett elágazás és vágás (Branch-and-Cut) algoritmust nyerünk. A diszkrét programozásban igen kifizetődően alkalmazott Branch-and-Bound algoritmust majd az 5. fejezetben tárgyaljuk.

Lineáris egyenlőtlenségek R^{n}-en

Ebben a fejezetben összefoglaljuk azokat a szükséges és alapvető definíciókat, tételeket, eredményeket, amelyeket fel fogunk használni a továbbiakban. Teljes bizonyításra csak olyan állítások esetében törekszünk, amelyeket a szokásos szakirodalom nem tárgyal.

2.1 Konvex halmazok, konvex burok

Vizsgálódásunk tárgya egy speciális R^{n}-beli részhalmaz lesz.

2.1. Definíció. Egy K ⊆ R^{n} halmaz \underline{konvex}, ha λx+(1−λ)y ∈ K minden λ ∈ [0, 1] és x, y ∈ K választással.

Nem nehéz megmutatni, hogy akárhány konvex halmaz metszete is konvex. Könynyen látható az is, hogy tetszőleges altér, sőt altér tetszőleges eltoltja is konvex. Az ilyen típusú halmazok közül különösen fontos lesz a következő.

2.2. Definíció. Egy H ⊆ R^{n} halmaz \underline{hipersík}, ha H = \{x ∈ R^{n} : αx = β\} alkalmas α ∈ R^{n} és β ∈ R választassal. Ekkor az F := {x ∈ R^{n} : αx ≥ β} halmaz neve \underline{féltér} és H az F \underline{határoló} hipersíkja.

Ha egy R^{n}-beli S részhalmaz az F féltérben fekszik, akkor azt mondjuk, hogy az F félteret definiáló αx ≥ β egyenlőtlenség \underline{érvényes} S-re.

CHAPTER 2. LINEÁRIS EGYENLŐTLENSÉGEK R^{N}-EN 8

Ha egy halmaz nem konvex, akkor érdekes lehet az őt tartalmazó legkisebb konvex halmaz. 2.3. Definíció. Az S ⊆ R^{n} halmaz \underline{konvex burka} az S-et tartalmazó konvex halmazok metszete, jelölésben conv(S).

A konvex burok karakterizációja számos, a témával foglalkozó könyvben, például [10]-ben, megtalálható. Ezért nem bizonyítjuk a következő lemmát. 2.1. Lemma. Tetszőleges S ⊆ R^{n} halmazra:

conv(S) = {x ∈ R^{n} : x = ∑_{i∈T} y^{i}λ_{i}, y^{i} ∈ S, λ_{i} ≥ 0, ∑_{i∈T} λ_{i} = 1, |T | < ∞}.

Triviális, hogy a konvex burok konvex halmaz lesz. Megemlítünk két egyszerű állítást, amelyeket felhasználunk majd. 2.2. Tétel. Legyen S ⊆ R^{n}, H = {x ∈ R^{n} : αx = β} egy hipersík, és tetszőleges x ∈ S vektorra teljesüljön az αx ≥ β egyenlőtlenség, azaz S ⊆ F teljesüljön a 2.2. Definícióbeli F -fel. Ekkor H ∩ conv(S) = conv(H ∩ S). Bizonyítás. A 2.1. Lemma és a feltételek alapján x ∈ H ∩ conv(S) ekvivalens azzal, hogy αx = β és x = ∑_{i∈T} y^{i}λ_{i}, ahol y^{i} ∈ S, λ_{i} ≥ 0, ∑_{i∈T} λ_{i} = 1, és T véges. De αy^{i} ≥ β minden y^{i}-re, így αx = β pontosan akkor áll, ha αy^{i} = β minden i-re, ez viszont azzal ekvivalens, hogy x ∈ conv(H ∩ S). □ 2.3. Tétel. Legyenek S, T ⊆ R^{n} tetszőleges halmazok. Ekkor a következő egyenlőség teljesül: conv(conv(S) ∪ conv(T)) = conv(S ∪ T). Bizonyítás. Könnyen látható, hogy conv(conv(S) ∪ conv(T)) ⊇ conv(S ∪ T), hiszen teljesül a conv(S) ∪ conv(T) ⊇ S ∪ T tartalmazás. Viszont az is triviális, hogy conv(S ∪ T) ⊇ conv(S) ∪ conv(T), tehát ez utóbbi halmazt lefedi egy konvex halmaz, azaz a konvex burka nem lehet bővebb: conv(conv(S) ∪ conv(T)) ⊆ conv(S ∪ T). Ezzel az állítást beláttuk. □

Konvex halmazok bizonyos pontjai fontos szerepet fognak játszani. 2.4. Definíció. Legyen K ⊆ R^{n} konvex halmaz. Egy x ∈ S pont \underline{extremális} pontja S-nek, ha nincs olyan x-től különböző y_{1}, y_{2} ∈ S, λ ∈ (0, 1), hogy x = λy_{1} + (1 − λ)y_{2} teljesüljön. Más szavakkal: x nem lehet egy S-hez tartozó szakasz belső pontja.

2.4. Tétel. Legyenek P, Q ⊆ R^{n}, valamint teljesüljön a P ⊆ Q tartalmazás. Ekkor Q azon extremális pontjai, melyek benne vannak P -ben, extremális pontjai lesznek a P halmaznak is.

Bizonyítás. Legyen x a tételbeli feltételeket kielégítő pont. Azt kell belátni, hogy x nem belső pontja egyetlen P -hez tartozó szakasznak sem. Viszont minden ilyen szakasz Q-nak is része, tehát a feltételek szerint x nem belső pontja. Így az állítást beláttuk. □

2.2 Poliéderek, kúpok

Rögtön definiáljuk is a fejezet címében szereplő objektumokat.

2.5. Definíció. Egy K ⊆ R^{n} halmaz \underline{konvex poliéder}, ha K = \{x ∈ R^{n} : Ax ≥ b\} alakban áll elő, ahol A egy n × m-es mátrix, b pedig egy R^{m}-beli vektor.

Belátható, hogy a konvex poliéder konvex halmaz.

2.6. Definíció. Egy C ⊆ R^{n} halmaz \underline{kúp}, ha minden x ∈ C és λ ≥ 0 esetén λx ∈ C teljesül.

Különösen érdekesek lesznek azok a kúpok, melyek konvexek. Ezek közül is azok, melyek poliéderek is. Az ilyen kúpok neve: \underline{poliedrikus kúp}. Egy poliedrikus kúp, eltekintve a C = {0} esettől, példa olyan poliéderre, mely nem korlátos.

2.7. Definíció. A korlátos poliéderek neve: \underline{politóp}.

A nemkorlátos poliéderek illetve kúpok vizsgálatában az extremális pontokon kívül más jellemzők is fontosak. Erről szól a következő

2.8. Definíció. Az x ∈ C vektor a C kúp \underline{extremális iránya}, ha nem léteznek olyan x-től lineárisan független u, v ∈ C vektorok, hogy x az u és v vektorok nemtriviális lineáris kombinációja, azaz x nem áll elő x = λu + μv alakban, ahol λ ≠ 0 ≠ μ.

A dolgozat során poliéderekről és kúpokról csak olyan egyszerű állításokat fogunk felhasználni, melyek könnyen bizonyíthatóak, vagy megtalálhatók bármely a témával foglalkozó könyvben, például [10]-ben.

2.3 Merőleges vetítés

A merőleges vetítés fontos szerepet fog játszani abban az úgynevezett konvexifikációs eljárásban, mely alkalmas lesz halmazok konvex burkát előállítani. A vágás típusú algoritmus megfogalmazásában alapvető jelentőségű lesz, hogy a konvexifikációs eljárást gyorsan végre tudjuk hajtani, ugyanis az eljárás során nyert egyenlőtlenségeket akarjuk használni vágó síkoknak.

Merőleges vetítést csak altérre értelmezzük, de megjegyezzük, hogy további nehézségek nélkül értelmezhetnénk altér eltoltjára is. Legyen tehát a továbbiakban S ⊆ R^{n} mindig egy tetszőleges altér. Ha S dimenziója s, akkor S felfogható R^{s}-ként. S ortogonális kiegészítője az a T ⊆ R^{n} halmaz, melynek minden eleme merőleges S-re, természetesen R^{n}-en a szokásos skalárszorzatot véve. Ekkor T is altér lesz és T dimenzióját t-vel jelölve igaz lesz az s + t = n egyenlőség. Ez viszont azt jelenti, hogy T -t megfeleltetve R^{t}-vel az R^{n} = R^{s} × R^{t} előállítást nyerjük. 2.9. Definíció. Legyen a P poliéder a következő formulával definiálva:

P := {(x, y) ∈ R^{s} × R^{t} : Dx + By ≤ d},

ahol D illetve B m × s illetve m × t-s mátrixok, d pedig egy R^{m}-beli vektor. Ekkor P \underline{merőleges vetülete} az x-síkra (=S altérre) a

Proj_{x}(P) := {x ∈ R^{s} : ∃y ∈ R^{t}, melyre (x, y) ∈ P }

halmaz.

Röviden megmutatjuk, hogy hogyan lehet a fenti definícióban meghatározott P poliéder x-síkra, vagy, ami ugyanaz, az S altérre vett merőleges vetületét meghatározni. Ehhez szükségünk lesz az alábbi poliedrikus kúpra, melyet Proj_{x}(P) előállításában felhasználunk. Legyen

W := {u ∈ R^{n} : uB = 0, u ≥ 0}.

Ekkor Proj_{x}(P)-t a következőképpen állíthatjuk elő:

Proj_{x} = {x ∈ R^{s} : (uD)x ≤ (ud) minden u ∈ extr(W) esetén},

ahol extr(W) jelöli a W poliedrikus kúp extremális irányainak halmazát.

Projekció és konvexifikáció

Rátérünk most már olyan algoritmusok tárgyalására, melyek képesek előállítani a vegyes programozási feladat megengedett megoldásaiból álló halmaz konvex burkát. Ezért a továbbiakban a következő halmazokat fogjuk tüzetesebben megvizsgálni:

K := {x ∈ R^{n} : Ax ≥ b, x ≥ 0, x_{j} ≤ 1, j = 1, …, p}.

Ha az x-re vonatkozó nemnegativitási feltételt, valamint az első p koordinátára vonatkozó feltételeket az Ax ≥ b feltétellel összeolvasztjuk, akkor alkalmas Ā mátrixxal és b̄ vektorral K-t

K = {x ∈ R^{n} : Āx ≥ b̄}

alakban írhatjuk fel. Persze K nem a vegyes programozási feladat megengedett megoldásainak halmaza, hanem annak standard lineáris programozási relaxációja. A megengedett megoldások halmazát a továbbiakban K^{0} jelöli, azaz

K^{0} := {x ∈ K : x_{j} ∈ {0, 1}, j = 1, …, p}.

3.1 A szekvenciális konvexifikáció

Ebben a szakaszban és a 4. fejezetben a [3] cikk eredményeire fogunk támaszkodni. Induljunk ki tehát egy fent definiált K halmazból, és próbáljuk meg meghatározni conv(K^{0})-t. Hajtsuk végre a következő lépéseket:

1. Lépés: Válasszunk egy j ∈ {1, …, p} indexet.

2. Lépés: Szorozzuk az Āx ≥ b̄ rendszert 1 − x_{j}-vel, majd x_{j}-vel, így a következő nemlineáris rendszert kapjuk:

(1 − x_{j})(Āx − b̄) ≥ 0  (3)
x_{j}(Āx − b̄) ≥ 0.

3. Lépés: Linearizáljuk (3)-at úgy, hogy helyettesítjük x_{i}x_{j}-t y_{i}-vel, ha i = 1, …, n, i ≠ j teljesül, x_{j}^{2}-et pedig x_{j}-vel. Jelöljük a kapott egyenlőtlenség-rendszer által meghatározott poliédert M_{j}(K)-val.

4. Lépés: Vetítsük M_{j}(K)-t az x_{i}-k által kifeszített térre. Az így kapott poliédert jelöljük P_{j}(K)-val.

Először megvizsgáljuk, hogy a 3. Lépésben végrehajtott linearizáció milyen további egyenlőtlenségeket határoz meg a régi x_{k}, illetve az új y_{i} változók között.

3.1. Tétel. A 3. Lépés után a következő egyenlőtlenségek teljesülnek:

1. y_{i} ≥ 0

2. y_{i} ≤ x_{i}, ha i = 1, …, n

3. y_{i} ≤ x_{j}, ha i = 1, …, p

4. y_{i} ≥ x_{i} + x_{j} − 1, ha i = 1, …, p.

Bizonyítás. 1-2. triviális. 3. abból adódik, hogy i = 1, …, p esetén x_{i} ≤ 1. 4. biztosan teljesül, ha x_{j} = 1, ugyanis ekkor y_{i} = x_{i}. Ha x_{j} ≠ 1, akkor 4. x_{i}x_{j} ≥ x_{i} + x_{j} − 1, x_{i}(x_{j} − 1) ≥ x_{j} − 1 végül x_{i} ≥ 0 átalakításaiból látható az állítás. □

Megjegyezzük még, hogy ha a K-t definiáló rendszerben m feltétel és n változó sze-repel, akkor az M_{j}(K)-t definiáló rendszerben 2m feltétel és 2n − 1 változó fog szerepelni. A vetület meghatározását már láttuk a 2.3. szakaszban.

Beláthatnánk egyszerűen, hogy K^{0} ⊆ P_{j}(K) ⊆ K teljesül, de ehelyett egy általánosabb tételt fogalmazunk meg:

3.2. Tétel. P_{j}(K) = conv(K ∩ {x ∈ R^{n} : x_{j} ∈ {0, 1}}). Bizonyítás. (i) Belátjuk, hogy P_{j}(K) ⊆ conv(K ∩ {x : x_{j} ∈ {0, 1}}). Tegyük fel először, hogy K ∩{x : x_{j} = 0} = ∅. Ekkor valamilyen ε > 0 számmal K az x_{i}−ε ≥ 0 féltérben fekszik. Ebből az következik, hogy minden olyan x, mely kielégíti (3)-at, kielégíti az (1 − x_{j})(x_{j} − ε) ≥ 0-t is. Kicserélve x_{j}^{2}-t x_{j}-vel látható, hogy M_{j}(K) és P_{j}(K) is az x_{j} ≥ 1 féltérben fekszik. Ez, a P_{j}(K) ⊆ K-val a P_{j}(K) ⊆ K ∩ {x : x_{j} = 1} tartalmazást jelenti, így (i) bizonyított.

Hasonlóan látható be (i) a K ∩ {x : x_{j} = 1} = ∅ esetben, ekkor P_{j}(K) az x_{j} ≤ 0 féltérben fekszik, és ugyanúgy következik (i).

Tegyük fel most, hogy K ∩ {x : x_{j} = 0} ≠ ∅ és K ∩ {x : x_{j} = 1} ≠ ∅. Legyen αx ≥ β egy olyan féltér, melyben a conv(K ∩ {x : x_{j} ∈ {0, 1}}) halmaz fekszik. Mivel ekkor a K ∩ {x : x_{j} = 0} halmaz is itt fekszik, létezik λ ≥ 0 úgy, hogy az αx + λx_{j} ≥ β féltér tartalmazza K-t. Továbbá mivel a K ∩ {x : x_{j} = 1} halmaz is az αx ≥ β féltérben fekszik, létezik μ ≥ 0, amivel K az αx + μ(1 − x_{j}) ≥ β féltérben fekszik. Most mivel K mind az αx + λx_{j} − β ≥ 0, mind az αx + μ(1 − x_{j}) − β ≥ 0 félterekben benne van, ezért az (1−x_{j})(αx+λx_{j} −β) ≥ 0, x_{j}(αx+μ(1−x_{j})−β) ≥ 0 egyenlőtlenségeket kielégíti minden olyan x, mely kielégíti (3)-at. Összeadva ezt a két egyenlőtlenséget az αx + (λ + μ)(x_{j} − x_{j}^{2}) ≥ β-t nyerjük, majd miután végrehajtjuk az x_{j}^{2} = x_{j} helyettesítést, αx − β ≥ 0-t. Tehát M_{j}(K) és P_{j}(K) az αx ≥ β féltérben fekszik, ami ismét (i)-et bizonyítja.

(ii) Belátjuk, hogy conv(K ∩ {x : x_{j} ∈ {0, 1}}) ⊆ P_{j}(K). Legyen x̄ ∈ K ∩ {x : x_{j} ∈ {0, 1}}. Definiáljuk i ≠ j esetén ȳ_{i} := x̄_{i}x̄_{j}-t. Ekkor (x̄, ȳ) ∈ M_{j}(K), hiszen x̄_{j}^{2} = x̄_{j}, és így x̄ ∈ P_{j}(K). Tehát a tételt teljes egészében beláttuk. □ 3.1. Definíció. Legyen t ≥ 2. Ekkor P_{i_{1},...,i_{t}}(K) := P_{i_{t}}(P_{i_{t−1}}(⋯ (P_{i_{1}}(K)) ⋯), ahol i_{1}, …, i_{t} ∈ {1, …, p} különböző számok.

3.3. Tétel. Bármely t ∈ {1, …, p} esetén P_{i_{1},...,i_{t}}(K) = conv(K ∩ {x ∈ R^{n} : x_{j} ∈ {0, 1}, j = i_{1}, …, i_{t}}). Bizonyítás. Az egyszerűség kedvéért legyen {i_{1}, …, i_{t}} = {1, …, t}. Legyen t ∈ {1, …, t}-re F_{t} := {x : x_{j} ∈ {0, 1} ∀j = 1, …, t}. t-re vonatkozó indukcióval bizonyítunk. t = 1-re az előző tétel igazolja az állítást. Tegyük fel, hogy a tétel igaz t = 1, …, q − 1-re, és legyen t = q, ahol 2 ≤ q ≤ p. Ekkor

P_{1,...,q}(K) = P_{q}(conv(K ∩ F_{q−1})) = conv(conv(K ∩ F_{q−1}) ∩ {x : x_{q} ∈ {0, 1}}), ahol az első egyenlőség az indukciós feltétel, a második pedig az előző tétel miatt teljesül. Az utolsó kifejezést így is írhatjuk:

conv((conv(K ∩ F_{q−1}) ∩ {x; x_{q} = 0}) ∪ (conv(K ∩ F_{q−1}) ∩ {x : x_{q} = 1})). Alkalmazva a 2.2. és a 2.3. Tételt a fenti halmazra az alábbi egyenlőségeket kapjuk: P_{1,...,t} = conv((K ∩ F_{q−1} ∩ {x : x_{q} = 0}) ∪ (K ∩ F_{q−1} ∩ {x : x_{q} = 1})) = conv(K ∩ F_{q−1} ∩ {x : x_{q} ∈ {0, 1}}) = conv(K ∩ F_{q}). Vagyis a bizonyítást befejeztük. □ 3.4. Következmény. P_{1,...,p}(K) = conv(K^{0}). Bizonyítás. Egyszerű következménye az előző tételnek t = p választással. □ 3.5. Következmény. P_{i}(P_{j}(K)) = P_{j}(P_{i}(K)), minden olyan i, j párra, melyre i, j ∈ {1, … p}, i ≠ j teljesül. Bizonyítás. Hasonlóan azonnal adódik a 3.3. Tételből. □

3.2 A Lovász-Schrijver konstrukció

Az előző szakaszban ismertetett algoritmus helyett más lehetőségek is vannak. Egy ilyet írunk le most. Csak az eljárást ismertetjük, az eredeti bizonyítások megtalálhatók [8]-ban.

1. Lépés: Szorozzuk az Āx ≥ b̄ egyenlőtlenséget x_{j}-vel és 1 − x_{j}-vel minden j =

1, …, p érték esetén. A kapott nemlineáris rendszer:

(1 − x_{1})(Āx − b̄) ≥ 0
x_{1}(Āx − b̄) ≥ 0
(1 − x_{2})(Āx − b̄) ≥ 0
x_{2}(Āx − b̄) ≥ 0  (4)
⋮
(1 − x_{p})(Ā − b̄) ≥ 0
x_{p}(Ā − b̄) ≥ 0.

2. Lépés: Linearizáljuk (4)-et úgy, hogy y_{ij}-t írunk x_{i}x_{j} helyett i = 1, …, n, j = 1, …, p, i ≠ j esetén, persze ekkor y_{ij} = y_{ji}, és x_{j}^{2} helyett ebben az esetben is írjunk x_{j}-t. Jelöljük a kapott rendszer által definiált poliédert M(K)-val.

3. Lépés: Vetítsük M(K)-t az x_{i}-k által kifeszített térre. Legyen a kapott poliéder

N(K). Megjegyezzük, hogy ha a K-t definiáló rendszer m feltételt és n változót tartal-

maz, melyek közül p-re kötünk ki 0-1 feltételt K^{0}-ban, akkor az M(K)-t definiáló rendszernek 2pm feltétele lesz és pn + n − \frac{1}{2}p(p + 1) változója. Lovász és Schrijver megmutatta, hogy N(K) rendelkezik a következő tulajdonságokkal: 3.6. Tétel. N(K) ⊆ conv(K ∩ {x ∈ R^{n} : x_{j} ∈ {0, 1}}), j = 1, …, p. □

Legyen N^{1}(K) := N(K) és N^{t}(K) := N(N^{t−1}(K)), ha t ≥ 2. 3.7. Tétel. N^{p}(K) = conv(K^{0}). □

Más szavakkal ez azt jelenti, hogy ha a fenti eljárást p-szer megismételjük, akkor megkapjuk a konvex burkot.

3.3 A Sherali-Adams konstrukció

Valamivel a Lovász-Schrijver konstrukció előtt Sherali és Adams [11]-ben egy hasonló eljárást közölt. Ezt fogjuk most röviden ismertetni. Jelölje most is K és K^{0} a megfelelő halmazokat, valamint legyen t ∈ {1, …, p}. Hajtsuk végre a következő lépéseket:

1. Lépés: Szorozzuk az Āx ≥ b̄ egyenlőtlenséget a következő alakú szorzatok mindegyikével: [Π_{j∈J_{1}}x_{j}][Π_{j∈J_{2}}(1 − x_{j})], ahol J_{1} és J_{2} olyan diszjunkt részhalmazai az {1, …, p} halmaznak, melyekre |J_{1} ∪ J_{2}| = t. Jelölje a kapott nemlineáris rendszert (NL_{t}).

2. Lépés: Linearizáljuk (NL_{t})-t úgy, hogy x_{j}-t írunk x_{j}^{2} helyett, valamint w_{J}-t írunk Π_{j∈J}x_{j} helyett, ahol J ⊆ {1, …, p}, és v_{Jk}-t írunk x_{k}Π_{j∈J}x_{j} helyett, ahol J ⊆ {1, …, p} és k ∈ {p + 1, …, n}. Jelöljük a kapott rendszer által meghatározott poliédert X_{t}-vel.

3. Lépés: Vetítsük X_{t}-t az x-térre. Legyen az így nyert poliéder K_{t}.

Könnyen látható, hogy K^{0} ⊆ K_{p} ⊆ ⋯ ⊆ K_{1} ⊆ K. Sherali és Adams viszont ennél többet bizonyított.

3.8. Tétel. K_{p} = conv(K^{0}). □

Megmutatjuk, hogy a fenti tétel is következménye a 3.3. Tételnek. Pontosabban igaz a következő

3.9. Tétel. Tetszőleges t = 1, …, p-re K_{t} ⊆ P_{1,...,p}(K).

Bizonyítás. Legyen A^{j}x ≥ b^{j} az a minimális lineáris rendszer, amely P_{1,...,j}(K)-t írja le j = 1, …, t esetén. Legyen továbbá αx ≥ β egy tetszőleges egyenlőtlenség a P_{1,...,t}(K)-t definiálók közül. Ekkor αx ≥ β-t úgy kaphatjuk, hogy az (1 − x_{t})(A^{t−1}x − b^{t−1}) ≥ 0 és az x_{t}(A^{t−1}x − b^{t−1}) ≥ 0 rendszerek nemnegatív lineáris kombinációját vesszük olyan szorzókkal, melyek eltüntetik a nemlineáris tagokat (x_{i}x_{t}-t, i ≠ t-re), és persze x_{t}^{2} helyett x_{t}-t írunk. Hasonlóan az A^{t−1}x − b^{t−1} ≥ 0 rendszer minden egyenlőtlensége megkapható nemnegatív lineáris kombinációiként az (1 − x_{t−1})(A^{t−2}x − b^{t−2}) ≥ 0 és az x_{t−1}(A^{t−2}x − b^{t−2}) ≥ 0 egyenlőtlenségeknek, ami eltünteti az x_{i}x_{t−1}, i ≠ t−1 tagokat és persze itt x_{t−1}^{2} helyett írunk x_{t−1}-et. Ismételve a fenti eljárást azt kapjuk, hogy αx ≥ β előáll az (NL_{t})-beli egyenlőtlenségek segítségével úgy, hogy először helyettesítünk x_{j}-t x_{j}^{2} helyett j = 1, …, n esetén, azután elimináljuk a megmaradt nemlineáris tagokat olyan szorzók segítségével, melyeket az egyes lépésekben használtunk. Így azt kapjuk, hogy αx ≥ β érvényes lesz K_{t}-re, amiből a tétel állítása adódik. □

Felhasználva az eddigieket látható, hogy a 3.8. Tételt a 3.9. Tételből és a 3.4. Következményből kaphatjuk.

3.4 Kapcsolat a diszjunktív programozással

A 3.1. fejezetben elmondottak szoros kapcsolatban vannak egy korábbi eredménnyel, a diszjunktív programozással, azaz a poliéderek unióján definiált optimalizálási feladattal. Ezen eredmények bizonyításai megtalálhatók [1]-ben és [2]-ben, így itt csak az érdekesebb és később felhasználandó eredményeket közöljük. Az első ezek közül egy egyszerű, poliéderek uniójának konvex burkát karakterizáló tétel. 3.10. Tétel. Legyen Π_{i} := {x ∈ R^{n} : A^{i}x ≥ b^{i}}, i ∈ Q, |Q| < ∞, valamint legyenek a Π_{i} poliéderek nemüresek. Ekkor conv(∪_{i∈Q}Π_{i}) azon x ∈ R^{n} pontok halmaza, melyekhez léteznek y^{i} ∈ R^{n} vektorok, y_{0}^{i} ∈ R számok i ∈ Q esetén, amelyekre

x − ∑_{i∈Q} y^{i} = 0
A^{i}y^{i} − b^{i}y_{0}^{i} ≥ 0  (5)
y_{0}^{i} ≥ 0
∑_{i∈Q} y_{0}^{i} = 1

teljesül. □

A fenti tételben feltettük, hogy Π_{i} ≠ ∅ minden i ∈ Q esetén. Ha valamely k ∈ Q-ra Π_{k} = ∅, akkor a következő regularitási feltétel teljesülése esetén a tétel még mindig érvényes marad: A^{k}y^{k} ≥ 0-ból következik, hogy y^{k} = ∑_{i∈Q^{∗}} y^{i}, valamely Q^{∗} ⊆ Q\{k}-ra úgy, hogy minden i ∈ Q^{∗} esetén Π_{i} ≠ ∅ és A^{i}y^{i} ≥ 0. Megmutatjuk, hogy a 3.2. Tétel speciális esetként kapható az előbbi tételből. Legyen ugyanis |Q| = 2 és Π_{1} := K ∩ {x : x_{j} = 0}, Π_{2} := K ∩ {x : x_{j} = 1}. Ebben az esetben (5) alakja a következő:

x − z − y = 0
Āz − b̄z_{0} ≥ 0
z_{j} = 0  (6)
Āy − b̄y_{0} ≥ 0
y_{j} − y_{0} = 0
z_{0} + y_{0} = 1.

Sőt, a fenti regularitási feltétel is teljesül, ha legalább egy Π_{i} nemüres.

Másrészről viszont az M_{j}(K)-t definiáló rendszert (3)-ból a megfelelő helyettesítések végrehajtásával az alábbi alakban írhatjuk fel:

Āx − b̄ − Āy + b̄x_{j} ≥ 0  (7)

Āy − b̄x_{j} ≥ 0.

Most az y_{0} := x_{j}, z := x − y, z_{0} := 1 − x_{j} mennyiségeket definiálva (7) átírható (6)-tá, hiszen az z_{j} = 0 egyenlőség y_{j} = x_{j}, z_{j} = x_{j} − y_{j}-ből, az y_{j} = y_{0} egyenlet pedig y_{j} = x_{j} = y_{0}-ból következik. A 3.2. Tétel azt állítja, hogy conv(Π_{1} ∪ Π_{2})-t (6)-ból az x-térre vett vetítéssel kaphatjuk meg, ami viszont a 3.10. Tétel speciális esete.

Egy másik karakterizációt láthatunk a következő tételben poliéderek uniójának konvex burkára, ami majd fontos szerepet fog játszani a következő fejezetben, a vágás típusú algoritmus megfogalmazásában. Az általános tételt most mi csak a számunkra érdekes esetre, nevezetesen a P_{j}(K) = conv(Π_{1} ∪ Π_{2}) halmazra fogalmazzuk meg.

3.11. Tétel. P_{j}(K) = {x ∈ R^{n} : αx ≥ β ∀ (α, β) ∈ P_{j}^{∗}(K)}, ahol P_{j}^{∗}(K) azon (α, β), α ∈ R^{n}, β ∈ R párok halmaza, melyekhez léteznek olyan u, v ∈ R^{m+n+p} vektorok, u_{0}, v_{0} ∈ R számok, hogy

α − uĀ − u_{0}e_{j} = 0
α − vĀ − v_{0}e_{j} = 0
ub̄ = β  (8)
vb̄ + v_{0} = β
u, v ≥ 0,

ahol e_{j} a j-edik egységvektor R^{n}-ben. Továbbá, ha K teljes dimenziós poliéder és Π_{1} ≠ ∅ ≠ Π_{2}, akkor tetszőleges β_{0} ≠ 0 konstansra αx ≥ β_{0} pontosan akkor definiálja egy lapját P_{j}(K)-nak, ha α extremális pontja P_{j}^{∗}(K)_{β_{0}}-nak, azaz annak a poliédernek, melyet úgy kapunk P_{j}^{∗}(K)-ból, hogy β-t lerögzítjük β_{0}-ra. □

A elkövetkezőkben rátérünk a szekvenciális konvexifikációs eljárás átfogalmazására diszjunktív halmazokra. A \underline{diszjunktív halmaz} nem más, mint olyan pontok halmaza, melyek logikai operátorokkal összekapcsolt egyenlőtlenségeket elégítenek ki. A logikai kapcsolat az egyenlőtlenségek között lehet konjunkció (∧, “és”), diszjunkció (∨, “vagy”) és negáció (¬, “nem”). Egy diszjunktív halmaz különböző ekvivalens alakokban fejezhető ki. Számunkra az úgynevezett \underline{konjunktív normálforma} lesz fontos, ami olyan tagokat köt össze konjunkcióval, melyek már nem tartalmaznak több konjunkciót. Például, ha az egyenlőtlenségeket nagybetűkkel jelöljük, akkor a (B ∧ C) ∨ (B ∧ D ∧ E) diszjunktív halmaz, ami végül is két poliéder uniója, a B ∧ (C ∨ D) ∧ (C ∨ E) konjunktív normálformára hozható. Még általánosabban, ha Π egy poliéder, mely tartalmazza a Π_{i}, i ∈ Q poliédereket, akkor az S := ∪_{i∈Q}Π_{i} halmaz, mint diszjunktív halmaz, átírható az

S = {x ∈ Π : ∧_{h=1}^{q}(∨_{k∈Q_{h}}d^{k}x ≥ d_{0}^{k})}  (9)

konjunktív normálformára, ahol |Q_{h}| = |Q| minden h-ra, és minden konjunkcióban pontosan egy egyenlőtlenség található minden i-re a Π_{i}-t definiáló rendszerből.

Az S diszjunktív halmaz \underline{burkolt}, ha minden egyes d^{k}x ≥ d_{0}^{k}, k ∈ Q_{h}, h = 1, …, q egyenlőtlenség által meghatározott hipersík Π-nek lapjára illeszkedik.

A burkoltság fogalmának jobb megértése kedvéért lássunk egy példát. Legyen Π egy háromszög a síkon, pontosabban legyen Π := {x ∈ R : x_{1} ≥ 0, x_{2} ≥ 0, 1 − x_{1} − x_{2} ≥ 0}. Definiálunk még két poliédert, egy-egy szakaszt az x_{1} és az x_{2} tengelyen. Legyen Π_{1} := {x ∈ R : x_{1} ≥ 0, x_{1} ≤ 1, x_{2} ≥ 0, x_{2} ≤ 0} az x_{1} tengelyen lévő [0, 1] intervallum, valamint legyen Π_{2} := {x ∈ R : x_{2} ≥ 0, x_{2} ≤ 1, x_{1} ≥ 0, x_{1} ≤ 0} az x_{2} tengelyen fekvő [0, 1] szakasz. Könnyű látni, hogy mind a Π_{1}, mind a Π_{2} poliédert definiáló egyenlőtlenségek által meghatározott hipersík Π-nek lapjára illeszkedik. Így ebben az esetben az S diszjunktív halmaz burkolt.

Burkolt diszjunktív halmazokra kimondhatjuk a következő tételt: 3.12. Tétel. Legyen S a (9) formulával definiálva. Legyen ezen kívül S_{0} := Π és h = 1, …, q-ra

S_{h} := conv(S_{h−1} ∩ {x : ∨_{k∈Q_{h}}d^{k}x ≥ d_{0}^{k}}).

Ha S burkolt, akkor S_{q} = conv(S). □

Amikor S = K^{0}, vagyis amikor

S := {x ∈ K : x_{h} ≤ 0 ∨ x_{h} ≥ 1, h = 1, …, p}

alakban adott, akkor világos, hogy S burkolt, így a fenti tétel speciális eseteként adódik a 3.3. Tétel. Megjegyezzük, hogy míg a burkoltság elégséges feltétel a fenti tétel teljesüléséhez, korántsem szükséges. Egy szükséges feltétel megtalálható [5]-ben.

Legyen egy αx ≥ β egyenlőtlenség érvényes K^{0}-ra. Azt mondjuk ekkor, hogy az αx ≥ β egyenlőtlenség \underline{diszjunktív rangja} r, ha r az a legkisebb egész, melyhez létezik olyan {i_{1}, …, i_{r}} részhalmaza {1, …, p}-nek, hogy αx ≥ β érvényes P_{i_{1},...,i_{r}}(K)- ra. A tisztán 0-1 programozási feladat esetén érdekes lehet a diszjunktív rangot összehasonlítani az úgynevezett \underline{Chvátal ranggal}.

A Chátal rang pontos definícióját az alábbiakban adjuk meg. Jelölje P_{I} a P poliéderben fekvő egész vektorok konvex burkát. Ha H egy racionális féltér, azaz H = {x : cx ≤ δ} valamilyen c ∈ Q^{n} racionális vektorral és δ ∈ Q racionális számmal, és ha még c olyan nemnulla vektor, melynek koordinátái relatív prím egészek, akkor

H_{I} = {x : cx ≤ ⌊δ⌋},

ahol ⌊ ⌋ természetesen az alsó egészrészt jelöli. Szemléletesen úgy fogalmazhatjuk meg a fenti képletet, hogy H-t addig toljuk, míg nem tartalmaz egész vektort, és az így kapott féltér legyen H_{I}.

Legyen most P egy poliéder, és definiáljuk P′-t a következő módon:

P′ := ⋂_{H⊇P} H_{I},

ahol a metszetet az összes H racionális féltérre vesszük, melyekre H ⊇ P teljesül. Mivel P ⊆ H-ból következik, hogy P_{I} ⊆ H_{I}, ezért P_{I} ⊆ P′. Ha ezek után rekurzívan definiáljuk P′′, P′′′, …-t, akkor a P ⊇ P′ ⊇ P′′ ⊇ ⋯ ⊇ P_{I} láncot kapjuk. Belátható, hogy ha P racionális, azaz ha a P -t definiáló egyenlőtlenség-rendszerben minden együttható racionális, akkor P′ is poliéder lesz, sőt létezik olyan t természetes szám, hogy P^{(t)} = P_{I} teljesül. A bizonyítások megtalálhatók [10]-ben (Theorem 23.2.). Most már definiálhatjuk egy Ax ≤ b egyenlőtlenség Chvátal rangját, mint azt a legkisebb t természetes számot, melyre {x : Ax ≤ b}^{(t)} = {x : Ax ≤ b}_{I} teljesül. Definiálható Chvátal rang nem csak egyenlőtlenséghez, de mátrixhoz is. Vegyük most is azt a legkisebb t természetes számot, amivel a fenti egyenlőség teljesül minden b vektor esetén. Az A mátrix \underline{erős Chvátal rangja} az

( \begin{matrix}I \\ −I \\ A \\ −A \end{matrix} )

mátrix Chvátal rangja.

Az adott Chvátal ranggal rendelkező mátrixok karakterizálása nehéz probléma, csak 0-ra és 1-re ismertek eredmények, 1-nél nagyobb értékekre megoldatlan. Az ismert eredmények megtalálhatók [10] 23.4. szakaszában.

Visszatérve a diszjunktív rang és a Chvátal rang összehasonlításához, legyen

K := {x ∈ R^{2} : −2x_{1} + x_{2} ≤ 0, 2x_{1} + x_{2} ≤ 2, 0 ≤ x_{j} ≤ 1, j = 1, 2}.

A 3.2. Tételből azonnal következik, hogy az x_{2} ≤ 0 egyenlőtlenségnek a diszjunktív rangja 1, viszont nem nehéz ellenőrizni, hogy Chvátal rangja 2. A diszjunktív rang a 3.3. Tétel alapján nem lehet nagyobb, mint a változók száma, továbbá hasonló felső becslés nem ismert a Chvátal rangra, így azt várhatnánk, hogy a diszjunktív rang mindig kisebb, vagy egyenlő, mint a Chvátal rang. A következő szakaszból viszont kiderül, hogy sajnos ez általában nem teljesül.

3.5 Alkalmazás kombinatorikus problémára

Egy G = (V, E) gráfban az S ⊆ V halmazt \underline{stabil halmaznak}, vagy független halmaznak hívjuk, ha nincs két szomszédos csúcs S-ben. Legyen a csúcsok száma G-ben n, azaz |V | = n. A \underline{stabil halmaz politópot} a G-beli stabil halmazok karakterisztikusvektorainak konvex burkaként definiáljuk és S(G)-vel jelöljük, azaz

S(G) := conv(x ∈ {0, 1}^{n} : x_{i} + x_{j} ≤ 1, ∀(i, j) ∈ E).

S(G) lineáris programozási relaxációját jelöljük F S(G)-vel, tehát

F S(G) := {x ∈ R_{+}^{n} : x_{i} + x_{j} ≤ 1, ∀(i, j) ∈ E).

Tudjuk, hogy S(G) szigorú részhalmaza F S(G)-nek, ha G nem páros gráf. Azon egyenlőtlenségek között, melyek érvényesek S(G)-re, de F S(G)-re nem, megtalálhatók az úgynevezett páratlan kör- és klikk-egyenlőtlenségek. Egy W ⊆ V halmazra jelölje G\W a V \W által generált G-beli részgráfot. Egy v ∈ V csúcsra legyen Γ(v) a v-vel szomszédos csúcsok halmaza. Ezek után, ha az adott G gráfot a G\\{v\}-vel helyettesítjük, akkor azt mondjuk, hogy ez utóbbi gráf G-ből a v \underline{törlésével} keletkezett. Ha G-t a G\(\{v\} ∪ Γ(v)) gráffal helyettesítjük, akkor a v \underline{összehúzásáról} beszélünk. Világos, hogy ezek a műveletek megfelelnek az S(G)-beli x_{v} változó x_{v} = 0 illetve x_{v} = 1 megszorításainak.

Ha az ax ≤ b egyenlőtlenség érvényes S(G)-re, akkor azt mondjuk, hogy a

∑_{j∈V \{v}} a_{j}x_{j} ≤ b és a ∑_{j∈V \({v}∪Γ(v))} a_{j}x_{j} ≤ b − a_{v}

egyenlőtlenségek ax ≤ b-ből a v \underline{törlésével} illetve v \underline{összehúzásával} keletkeztek.

A következő két tulajdonságot Lovász és Schrijver bizonyította N(F S(G))-re [3]- ban. Itt most belátjuk, hogy igazak a nagyobb P_{j}(F S(G)) halmazra is. 3.13. Tétel. Ha ax ≤ b érvényes egyenlőtlenség S(G)-re és létezik j ∈ V, hogy azok az egyenlőtlenségek, melyek ax ≤ b-ből a j törlésével illetve j összehúzásával keletkeznek érvényesek F S(G\{j})-re illetve F S(G\({j} ∪ Γ(j)))-re, akkor ax ≤ b érvényes lesz P_{j}(F S(G))-re. Bizonyítás. A 3.2. Tétel alapján P_{j}(F S(G)) = conv(F S(G) ∩ {x : x_{j} ∈ {0, 1}}). Ebből viszont már adódik az állítás. □ 3.14. Tétel. Legyen C ⊆ V, mely egy páratlan kört határoz meg G-ben. Ekkor a páratlan kör-egyenlőtlenség, azaz

∑_{i∈C} x_{i} ≤ \frac{|C| − 1}{2},

érvényes lesz P_{j}(F S(G))-re bármely j ∈ C-re. Bizonyítás. Legyen j ∈ C. Ekkor azok az egyenlőtlenségek, melyek a páratlan köregyenlőtlenségből kaphatók a j törlésével illetve összehúzásával, érvényesek lesznek F S(C\{j})-re illetve F S(C\({j}∪Γ(j)))-re, hiszen a C\{j} és a C\({j}∪Γ(j))) által indukált G-beli részgráfok mindegyike páros. Így az előző tétel alapján a páratlan kör-egyenlőtlenség érvényes lesz P_{j}(F S(G))-re. □

Tehát azt kapjuk, hogy a páratlan kör-egyenlőtlenségnek, melynek Chvátal rangja 1, diszjunktív rangja szintén 1. 3.15. Következmény. Az összes páratlan kör-egyenlőtlenség érvényes a következő poliéderre:

P (F S(G)) := ⋂_{j∈V} P_{j}(F S(G)).

Bizonyítás. Közvetlenül adódik az előző tételből. □

Mint említettük, az N(K) Lovász-Schrijver relaxáció erősebb lehet a P_{j}(K) relaxációnál. Itt ez az N(F S(G)) ⊆ P (F S(G)) tartalmazás szigorú voltát vonná maga után. Viszont nem ez helyzet, hiszen most a két relaxáció megegyezik. Lovász és Schrijver [3]-ban karakterizálta N(F S(G))-t, mint az F S(G)-t definiáló egyenlőtlenségek, valamint a páratlan kör-egyenlőtlenségek által meghatározott poliédert. 3.16. Tétel. P (F S(G)) = N(F S(G)). Bizonyítás. Az N(F S(G)) ⊆ P (F S(G)) tartalmazást már tárgyaltuk. Az ellenkező irányú P (F S(G)) ⊆ N(F S(G)) tartalmazás pedig a 3.15. Következményből, valamint Lovász és Schrijver fent említett erdményéből adódik. □

Egy másik jól ismert osztálya a stabil halmaz poliéderre érvényes egyenlőtlenségeknek az úgynevezett klikk-egyenlőtlenségek. Egy gráfban \underline{klikknek} nevezzük a páronként szomszédos csúcsokból álló halmazt.

\underline{Klikk-egyenlőtlenségnek} nevezzük a

∑_{j∈K} x_{j} ≤ 1

alakú egyenlőtlenségeket, ahol K ⊆ V egy klikk G-ben. Ismert tény, hogy a fenti klikk-egyenlőtlenség pontosan akkor definiálja az S(G) egy lapját, ha a K klikk a tartalmazásra nézve maximális. A klikk-egyenlőtlenségek Chvátal rangja ismert: ⌈log_{2}(|K| − 1)⌉, ahol ⌈ ⌉ a felső egészrészt jelöli. 3.17. Tétel. Bármely K klikkre a ∑_{i∈K} x_{i} ≤ 1 klikk-egyenlőtlenség diszjunktív rangja |K| − 2. Bizonyítás. Először indukcióval belátjuk, hogy ∑_{i∈K} x_{i} ≤ 1 diszjunktív rangja legfeljebb |K| − 2. |K| = 3-ra mindez a 3.14. Tételből következik. Tegyük fel most, hogy minden olyan K klikkre tudjuk az állítást, melyre |K| ≤ k. Legyen K′ egy k + 1 elemű klikk. Legyen ezen kívül j ∈ K′ és K = K′\{j}. Az indukciós feltétel alapján a ∑_{i∈K} x_{i} ≤ 1 egyenlőtlenség rangja, ami a ∑_{i∈K′} x_{i} ≤ 1 egyenlőtlenségből j törlésével áll elő, legfeljebb k, azaz létezik {i_{1}, …, i_{k}} ⊆ V, hogy az egyenlőtlenség érvényes P_{i_{1},...,i_{k}}(F S(G))-re. És mivel a ∑_{i∈K′} x_{i} ≤ 1-ből j összehúzásával adódó egyenlőtlenség nem más, mint 0 ≤ 0, triviálisan érvényes P_{i_{1},...,i_{k}}(F S(G))-re. Így a 3.2. Tétel alapján ∑_{i∈K′} x_{i} ≤ 1 érvényes lesz P_{i_{1},...,i_{k},j}(F S(G))-re és így ∑_{i∈K′} x_{i} ≤ 1 diszjunktív rangja legfeljebb k + 1 = |K′|.

Ahhoz, hogy belássuk, hogy ∑_{i∈K} x_{i} ≤ 1 diszjunktív rangja pontosan |K| − 2, tegyük fel indirekten, hogy csak s, ahol s ≤ |K| − 3. Ekkor létezik {i_{1}, …, i_{s}} ⊆ V, hogy az egyenlőtlenség érvényes P_{i_{1},...,i_{s}}(F S(G))-re. Ekkor a 3.2. Tétel alapján kapjuk, hogy akár i_{s} ∈ K, akár i_{s} ∉ K, az

∑_{i∈K\{i_{s}}} x_{i} ≤ 1

egyenlőtlenség érvényes P_{i_{1},...,i_{s−1}}(F S(G\{i_{s}}))-re. Alkalmazzuk ezt az eredményt K\{i_{s}}-re, K\{i_{s}, i_{s−1}}-re, stb. Ekkor azt kapjuk, hogy a

∑_{i∈K\{i_{1},...,i_{s}}} x_{i} ≤ 1

egyenlőtlenség érvényes lesz F S(G\{i_{1}, …, i_{s}})-re. Ez viszont |K\{1, …, s}| ≥ 3 miatt ellentmondás. □

Vagyis teljesítettük az előző szakaszban ígért eredményt, miszerint mutatunk olyan egyenlőtlenséget, melynek diszjunktív rangja nagyobb, mint a Chvátal rangja. Látható ugyanis, hogy az olyan klikk-egyenlőtlenségnél, melynek mérete nagyobb, mint 4, épp ez teljesül.

Vágás típusú algoritmusok

Eljutottunk ahhoz a ponthoz, hogy az eddigi ismeretek alapján megfogalmazhatunk vágás típusú algoritmusokat. Vágó síkoknak az előző szakaszokban behatóan vizsgált konvexifikációban lényeges szerepet betöltő egyenlőtlenségeket választjuk.

4.1 Az általános eljárás

A fenti vágó síkokra vonatkozó megállapítást pontosítva azt mondhatjuk, hogy vágó síkoknak a P_{j}(K) poliéder oldalait akarjuk használni. Ehhez először generálunk egy αx ≥ β egyenőtlenséget úgy, hogy (α, β) extremális iránya legyen a 3.11. Tételben szereplő P_{j}^{∗}(K) kúpnak. Ezt könnyen megtehetjük a

max{aα + bβ : (α, β) ∈ P_{j}^{∗}(K) ∩ S}  (10)

lineáris programozási feladat megoldásával, ahol az (a, b) ∈ R^{n+1} vektor valamilyen értelemben a vágás irányát határozza meg, az S pedig a P_{j}^{∗}(K) kúp “normalizációja”, ami ahhoz szükséges, hogy a maximalizálás korlátos halmazon történjen. A fentiek alapján már felírhatjuk a legdurvább formáját az algoritmusunknak.

1. Algoritmus

0. Lépés: t := 1, K^{1} := {x ∈ R^{n} : Āx ≥ b̄}.

1. Lépés: Legyen cx^{t} := min{cx : x ∈ K^{t}}. Ha j = 1, …, p-re x_{j}^{t} ∈ {0, 1}, akkor STOP.

2. Lépés: Az összes j ∈ {1, …, p} indexre, melyre 0 < x_{j}^{t} < 1 teljesül, legyen

a^{t}α^{j} + b^{t}β^{j} := max{a^{t}α + b^{t}β : (α, β) ∈ P_{j}^{∗}(K^{t}) ∩ S}.

3. Lépés: Definiáljuk K^{t+1}-et K^{t}-ből úgy, hogy a K^{t}-t definiáló egyenlőtlenségekhez csatoljuk a 2. Lépésben generált egyenlőtlenségeket.

4. Lépés: Legyen t := t + 1 és ugorjunk az 1. Lépésre.

A fenti algoritmus csak egy váz, hiszen többféle módon választhatjuk meg az S halmazt és az (a^{t}, b^{t}) vektort a 2. Lépésben. Azt mondjuk, hogy az (α, β) ∈ P_{j}^{∗}(K^{t}) a legmélyebb vágást definiálja, ha az x^{t} és az αx = β hipersík (Euklideszi) távolsága maximális.

Maximalizálni a távolságot x^{t} és αx = β között ugyanaz, mint maximalizálni a távolságot x^{t} és x^{t} αx = β-ra vett merőleges vetülete között, ami viszont nem más, mint x̃ = x^{t}+λα valamilyen λ > 0-ra. Mivel az αx = β sík ugyanaz, mint a λαx = λβ sík, az általánosság megszorítása nélkül feltehetjük, hogy λ = 1. Így x̃ − x^{t} = α. Sőt, β − αx^{t} = αx̃ − αx^{t} = αα miatt a legmélyebb vágás az (a^{t}, b^{t}) = (−x^{t}, 1) vektornál és az S := {(α, β) : β − αx^{t} = αα} halmaznál adódik. Az így nyert (10) rendszer nem lesz lineáris programozási feladat, hiszen az S-et definiáló egyenlet másodfokú. Ezért kénytelenek leszünk más normalizációkkal dolgozni a fenti “optimális” helyett. Továbbra is az (a^{t}, b^{t}) = (−x^{t}, 1) választással élünk, csak az S normalizáló halmaz megválasztására mutatunk be alternatívákat.

1. Normalizáció. Egyszerűen megkövetelhetjük, hogy β = 1 vagy β = −1 teljesüljön. Ekkor S = {(α, β) : β = 1} vagy S = {(α, β) : β = −1}. Sok probléma olyan, hogy könnyen eldönthetjük, hogy olyan αx ≥ β síkkal vágjunk, melyre β > 0, vagy olyannal, melyre β < 0. Ez a megközelítés egyrészt előnyös, ugyanis a (10) lineáris programozási feladat mérete redukálható ebben az esetben ha elimináljuk az α_{i} változókat i = 1, …, n esetén a P_{j}^{∗}(K)-t definiáló (8) rendszerből. Így mind a β = 1, mind a β = −1 esetben (10) a következő alakú lesz:

min u(Āx^{t}) + u_{0}x_{j}^{t}

uĀ − vĀ + (u_{0} − v_{0})e_{j} = 0
ub̄ = β  (11)
vb̄ + v_{0} = β
u, v ≥ 0.

Másrészről viszont a hátránya az, hogy nem garantálja az optimális megoldás létezését.

Hogy ezt a megállapítást pontosabban kifejtsük, tekintsük a β = −1 esetet. A következő tételt lehet bebizonyítani.

4.1. Tétel. A (11) feladat nemkorlátos, ha λx^{t} ∉ P_{j}(K) bármely λ > 0 számra.

Bizonyítás. A feltételt átfogalmazva azt mondhatjuk, hogy minden λ > 0 számhoz létezik (α^{λ}, −1) ∈ P_{j}^{∗}(K) úgy, hogy λα^{λ}x^{t} < −1. A P_{j}^{∗}(K)-t definiáló rendszer első egyenletét x^{t}-vel szorozva adódik, hogy α^{λ}x^{t} = u^{λ}Āx^{t} + u_{0}^{λ}x_{j}^{t}, ahol u^{λ}, u_{0}^{λ} az (α^{λ}, −1) vektorhoz tartozik. Vegyük még az előző vektorhoz tartozó v^{λ}, v_{0}^{λ} értékeket is, ekkor könnyen látható, hogy (11) egy megengedett megoldásához jutunk. Az első megállapítás alapján az ehhez tartozó célfüggvényérték α^{λ}x^{t}, amire viszont α^{λ}x^{t} < −1/λ teljesül, ebből viszont λ → 0 választással adódik a tétel állítása. □

A következő két normalizáció garantálja a (10) feladat véges optimumának létezését.

2. Normalizáció. Megköveteljük, hogy ∥α∥_{∞} ≤ 1 teljesüljön, azaz S-et így definiáljuk:

S := {(α, β) : −1 ≤ α_{i} ≤ 1, i = 1, … n}.

3. Normalizáció. Most azt követeljük meg, hogy ∥α∥_{1} ≤ 1 teljesüljön, azaz S-et most így definiáljuk:

S := {(α, β) : ∑_{i=1}^{n} |α_{i}| ≤ 1} .

Az abszolút értéktől könnyen megszabadulhatunk és így lineárissá tehetjük a normalizációnkat. Vezessünk be e célból 2n új változót, jelöljük ezeket α_{i}^{+}, α_{i}^{−}-szal i = 1, …, n esetén. A fenti képletből α-t kiküszöbölve kapjuk S-re az alábbi, immár lineáris előállítást:

S := {(α, β) : α = α^{+} − α^{−}; α^{+}, α^{−} ≥ 0, ∑_{i=1}^{n}(α_{i}^{+} + α_{i}^{−}) ≤ 1} .

Megjegyezzük, hogy habár az 1. Normalizáció mindig a P_{j}^{∗}(K) kúp extremális irányát adja, a 2. és 3. Normalizáció általában nem. Viszont ha P_{j}^{∗}(K) az R^{n+1} tér egy ortánsában fekszik, ami például teljesül, ha az összes α_{i}-nek azonos az előjele, akkor a 3. Normalizáció a P_{j}^{∗}(K) extremális irányát adja.

4.2 A végesség bizonyítása

Amíg több véges algoritmus ismert tisztán egészértékű programozási feladatra, a vegyes programozási feladat esetében sokkal nehezebb végességet garantálni.

Az első vágás típusú algoritmus vegyes programozási feladatra Gomory nevéhez fűződik [6]. Végességet viszont az algoritmus csak akkor tud garantálni, ha a célfüggvény-együtthatók egészek. Ennek a feltételnek a vizsgálata, illetve példa nemvégességre megtalálható a [13] munkában.

Az első véges vágás típusú algoritmust vegyes programozási feladatra Jeroslow adta [7]. Ebben a szakaszban az 1. Algoritmus egy speciális változatáról bizonyítunk végességet. Habár a bizonyításunk egyszerűbb lesz, mint Jeroslowé, ugyanazt az ötletet használjuk.

Megjegyezzük, hogy az előző szakaszban ismertetett legáltalánosabb algoritmus nem minden megvalósítása lesz véges. A végesség biztosítása miatt tovább kell pontosítanunk az általános keretet. E célból először néhány jelöléssel kezdjük. Az általános algoritmusban szereplő aktuális K^{t} poliédert az Āx ≥ b̄ rendszer definiálja néhány vágással együtt. Egy j ∈ {1, …, p}-re a K^{t}-t leíró rendszerben szereplő vágást \underline{j-vágásnak} nevezünk, ha mint vágást valamilyen P_{j}(·)-ben generáltunk, vagyis ha az x_{j} = 0 ∨ x_{j} = 1 diszjunkcióból keletkezett. Legyen K_{j}^{t} az a poliéder, melyet az Āx ≥ b̄ rendszer és az összes i-vágás definiál i = 1, …, j esetén. Legyen továbbá K_{0}^{t} := K. Megjegyezzük, hogy ezzel a jelöléssel K_{p}^{t} = K^{t} és K_{j}^{t} ⊆ K_{i}^{t} minden olyan i, j párra, melyre 0 ≤ i < j ≤ p.

Legyen még P_{j}^{∗}(K)_{S} := P_{j}^{∗}(K) ∩ S, ahol S a 2. vagy a 3. Normalizáció, illetve, ha alkalmazható a probléma természete alapján, az 1. Normalizáció által definiált halmaz.

2. Algoritmus

0. Lépés: t := 1, K^{1} := K = {x ∈ R^{n} : Āx ≥ b̄}.

1. Lépés: Legyen cx^{t} := min{cx : x ∈ K^{t}}. Ha x_{j}^{t} ∈ {0, 1} j = 1, …, p-re, akkor STOP.

2. Lépés: Legyen j ∈ {1, …, p} az a legnagyobb index, melyre 0 < x_{j}^{t} < 1. Generáljunk egy α^{j}x ≥ β^{j} j-vágást úgy, hogy megoldjuk a

max{β − αx^{t} : (α, β) ∈ P_{j}^{∗}(K_{j−1}^{t})_{S}}

lineáris programozási feladatot.

3. Lépés: Definiáljuk K^{t+1}-et K^{t}-ből úgy, hogy a K^{t}-t definiáló egyenlőtlenségekhez csatoljuk az α^{j}x ≥ β^{j} j-vágást.

4. Lépés: Legyen t := t + 1 és ugorjunk az 1. Lépésre.

4.2. Tétel. A 2. Algoritmus véges sok lépés alatt eljut a vegyes programozási feladat optimális megoldásához.

Bizonyítás. Lényegében két állítást elegendő belátnunk. Ezek a következők: (i) A 2. Lépésben generált α^{j}x ≥ β^{j} egyenlőtlenség levágja x^{t}-t. (ii) Minden j = 1, …, p-re az algoritmus által generált j-vágások száma véges.

(i) bizonyításához először megmutatjuk, hogy x^{t}, ami K^{t} (= K_{p}^{t}) extremális pontja, extremális pontja K_{j}^{t}-nek is. Ha j = p, akkor ez triviálisan igaz, ezért feltehetjük, hogy j < p. Mivel x_{p}^{t} ∈ {0, 1}, következik, hogy x^{t} ∈ K_{p−1}^{t} ∩ {x ∈ R^{n} : x_{p} = x_{p}^{t}} ⊆ P_{p}(K_{p−1}^{t}) ⊆ K_{p}^{t}. Az első tartalmazás és a 2.4. Tétel miatt x^{t} extremális pontja K_{p−1}^{t}∩{x ∈ R^{n} : x_{p} = x_{p}^{t}}-nek is, és így persze K_{p−1}^{t}-nek is, hiszen K_{p−1}^{t}∩{x ∈ R^{n} : x_{p} = x_{p}^{t}} egy lapja K_{p−1}^{t}-nek. Innen indukcióval, x_{k}^{t} ∈ {0, 1} k = p, p − 1, …, j + 1 miatt, könnyen látható, hogy x^{t} extremális pontja K_{p−1}^{t}, K_{p−2}^{t}, …, K_{j}^{t}-nek is.

Másodszor megmutatjuk, hogy x^{t} ∉ P_{j}(K_{j−1}^{t}). Mivel P_{j}(K_{j−1}^{t}) ⊆ K_{j}^{t}, ha x^{t} ∈ P_{j}(K_{j−1}^{t}) teljesülne, akkor x^{t} extremális pontja lenne P_{j}(K_{j−1}^{t})-nak is. Viszont P_{j}(K_{j−1}^{t}) minden extremális pontjának j-edik koordinátája 0 vagy 1, holott 0 < x_{j}^{t} < 1. Mivel x^{t} ∉ P_{j}(K_{j−1}^{t}), a 2. Lépésben generált α^{j}x ≥ β^{j} egyenlőtlenséget megsérti az x^{t}.

(ii)-t indukcióval bizonyítjuk. Az állítás igaz j = 1-re, ugyanis minden a 2. Lépésben generált 1-vágás P_{1}^{∗}(K_{0}^{t})_{S} = P_{1}^{∗}(K)_{S}-nek egy extremális pontjához tartozik, extremális pontokból viszont csak véges sok van, és ahogy (i)-ben láttuk, minden a 2. Lépésben generált 1-vágás levágja a korábban generált 1-vágásokat kielégítő x^{t}-t.

Tegyük fel most, hogy az állítás igaz minden i = 1, …, j − 1-re, és legyen i = j. Az indukciós hipotézis miatt a K_{j−1}^{t} halmazt az algoritmus 3. Lépésében csak véges sokszor definiáljuk újra (úgy, hogy a feltételekhez veszünk valamilyen i-vágást, i ∈ {1, …, j − 1} esetén). Bármely két ilyen átdefiniálás között csak véges sok j-vágás generálható a 2. Lépésben, mivel minden egyes j-vágás a P_{j}^{∗}(K_{j−1}^{t})_{S} egy extremális pontjához tartozik, amelyekből viszont csak véges sok van. Ezen kívül minden egyes j-vágás levágja a korábban generált j-vágásokat kielégítő x^{t}-t. Így az egész algoritmus során is csak véges sok j-vágás generálható, ami bizonyítja a tétel állítását. □

4.3 Vágások a bázis inverzéből

Legyen x^{t} a 2. Algoritmus t-edik iterációjában talalált megoldás, azaz cx^{t} = min{cx : x ∈ K^{t}}, K^{t} = {x ∈ R^{n} : Ā^{t}x ≥ b̄^{t}}. Általánosságban elmondható, hogy a (8) által definiált P_{j}^{∗}(K^{t})-beli αx ≥ β vágáshoz tartozó azon u_{i}, v_{i} változók lehetnek szigorúan pozitívak, amelyekhez tartozó ∑_{j=1}^{n} ā_{ij}^{t}x_{j} ≥ b̄_{i}^{t} egyenlőtlenséget nem egyenlőséggel elégíti ki x^{t}. Abban az esetben, amikor azt írjuk elő, hogy csak azon u_{i}, v_{i} változók lehetnek szigorúan pozitívak, melyekhez tartozó ∑_{j=1}^{n} ā_{ij}^{t}x_{j} ≥ b̄_{i}^{t} feltétel nem bázisbeli, a vágást generálhatjuk anélkül, hogy megoldanánk a lineáris programozási feladatot. Ezt mutatjuk be az alábbiakban.

Legyen B^{t} az a mátrix, amelyet úgy kapunk Ā^{t}-ből, hogy csak azokat a sorokat tartjuk meg, amelyekhez tartozó feltételhez rendelt slack változó nem bázisbeli. Feltehető, hogy B^{t} négyzetes mátrix. Legyen C := {x ∈ R^{n} : B^{t}x ≥ d^{t}} az a poliéder, melyet azok az Ā^{t}x ≥ b̄^{t} rendszerből származó egyenlőtlenségek definiálnak, melyek a B^{t} soraihoz tartoznak. Ekkor a 3.11. Tételt alkalmazva P_{j}(C)-re és eliminálva az α_{i} i = 1, …, n és β változókat a megfelelő (8) rendszerből, a következőt kapjuk:

(u^{B} − v^{B})B^{t} = (v_{0}^{B} − u_{0}^{B})e_{j}
(u^{B} − v^{B})d^{t} = v_{0}^{B}  (12)
u^{B}, v^{B} ≥ 0.

Mivel a B^{t} mátrix invertálható, adott v_{0}^{B} − u_{0}^{B} számhoz a z^{B} := u^{B} − v^{B} vektor egyértelműen meghatározott már (12) első n feltételéből. Sőt, (12) tetszőleges bázis megoldása kielégíti az u_{i}^{B} · v_{i}^{B} = 0 feltételt minden i-re, amiből viszont az következik, hogy u^{B} és v^{B} egyértelműen meghatározott z^{B}-ből, mint z^{B} pozitív és negatív részei. Pontosabban: u^{B} = max{z^{B}, 0}, v^{B} = max{−z^{B}, 0}, ahol két vektor maximuma a koordinátánként vett maximumokból álló vektor. Mindez arra ösztönöz minket, hogy egy új normalizációt vezessünk be. B^{t} invertálhatósága miatt feltehetjük, hogy v_{0}^{B} −u_{0}^{B} ≠ 0, hiszen csak ebben az esetben adódhat z^{B}-re, és így v^{B}-re illetve u^{B}-re is, nemtriviális eredmény. Ezek alapján az új normalizációhoz követeljük meg most és a továbbiakban v_{0}^{B} − u_{0}^{B} = 1 teljesülését. Ebből a normalizációból nyerhető vágások egyértelműen meghatározottak (12)-ből és az alábbi egyszerű formulákból αx ≥ β-ra:

u^{B} = max{(B^{t})_{j}^{−1}, 0}
v^{B} = max{−(B^{t})_{j}^{−1}, 0}
α_{i} = max{(B^{t})_{j}^{−1}, 0}B_{i}^{t}, i = 1, …, n, i ≠ j  (13)
α_{j} = max{(B^{t})_{j}^{−1}, 0}B_{j}^{t} + (B^{t})_{j}^{−1}d^{t} − 1
β = max{(B^{t})_{j}^{−1}, 0}d^{t},

ahol (B^{t})_{j}^{−1} a (B^{t})^{−1} mátrix j-edik sorát jelöli, valamint B_{i}^{t} a B^{t} mátrix i-edik oszlopa. Fontos megjegyezni, hogy a (B^{t})^{−1} mátrix j-edik sorát nem kell külön számolnunk, hiszen megtalálható az x^{t} megoldás által definiált szimplex táblában.

4.4 Vágások élesítése

A P_{j}^{∗}(K)-beli αx ≥ β vágás valamilyen j ∈ {1, …, n} esetén az x_{j} változó egészértékűségi feltételéből keletkezett. E vágás élesíthető, ha x_{j}-n kívül más változókra is megköveteljük az egészértékűséget. Az élesített vágás pontos fogalmát a későbbiekben ismertetni fogjuk.

Tekintsük a P_{j}^{∗}(K)-t definiáló (8) rendszert. Ha különválasztjuk a nemnegativitási feltételt a többitől, azaz ha Āx ≥ b̄-t az Ãx ≥ b̃, x ≥ 0 alakban írjuk fel, akkor (8) alakja a következő lesz:

α − ũÃ − u_{0}e_{j} ≥ 0
α − ṽÃ − v_{0}e_{j} ≥ 0
ũb̃ = β  (14)
ṽb̃ + v_{0} = β
ũ, ṽ ≥ 0.

Az αx ≥ β vágás együtthatóit pedig az alábbi módon határozhatjuk meg:

α_{k} = max{α_{k}^{1}, α_{k}^{2}}, k = 1, …, n,

ahol

α_{k}^{1} = ũÃ_{k}, α_{k}^{2} = ṽÃ_{k}, k = 1, … p, k ≠ p esetén,

valamint

α_{j}^{1} = ũÃ_{j} + u_{0}, α_{j}^{2} = ṽÃ_{j} + v_{0}

(itt Ã_{k} jelöli az Ã mátrix k-adik oszlopát) és

β = ũb̃ = ṽb̃ + v_{0}.

Egy olyan αx ≥ β vágó síkot, melyre β ≠ 0 teljesül, a |β|γx ≥ β vágó síkká élesíthetjük, ahol β-t úgy definiáljuk, mint fent, γ-t pedig az alábbi formulák alapján határozzuk meg:

γ_{k} = min \{\frac{1}{|β|}(α_{k}^{1} + u_{0}⌈m_{k}⌉), \frac{1}{|β|}(α_{k}^{2} − v_{0}⌊m_{k}⌋)\} k = 1, … p
γ_{k} = max \{\frac{1}{|β|}α_{k}^{1}, \frac{1}{|β|}α_{k}^{2}\} k = p + 1, … n,

ahol

m_{k} = \frac{α_{k}^{2} − α_{k}^{1}}{u_{0} + v_{0}} .

Megmutatjuk, hogy a fenti vágás élesítése az αx ≥ β-nak. Ehhez megfogalmazzuk, hogy pontosan mit értünk élesebb vágáson.

4.1. Definíció. Egy cx ≥ d vágás \underline{élesítése} az ax ≥ b vágásnak, ha c ≤ a és d ≥ b teljesül.

Azt kell tehát megmutatnunk, hogy |β|γ ≤ α teljesül. γ definíciója alapján |β|γ_{k} = α_{k} k = p + 1…. , n esetén, tehát elegendő foglalkoznunk a k = 1, …, p indexekkel. Így azt kell belátnunk, hogy

min{α_{k}^{1} + u_{0}⌈m_{k}⌉, α_{k}^{2} − v_{0}⌊m_{k}⌋} ≤ max{α_{k}^{1}, α_{k}^{2}}.

Esetszétválasztással könnyen célt érhetünk, csak egy esetet fogunk részletesen megmutatni, a többi hasonlóan bizonyítható. Tegyük fel tehát, hogy α_{k}^{2} > α_{k}^{1} teljesül. Az egyenlőség érdektelen eset, hiszen ekkor triviálisan igaz a kívánt egyenlőtlenség. Ebben az esetben elég azt megmutatni, hogy

α_{k}^{1} + u_{0}⌈m_{k}⌉ ≤ α_{k}^{2}.

Feltehető, hogy u_{0} ≠ 0, hiszen ellenkező esetben ismét triviálisan adódik az eredmény. Átrendezve a fenti egyenlőtlenséget és m_{k} értéket behelyettesítve adódik u_{0} > 0 esetén az

⌈\frac{α_{k}^{2} − α_{k}^{1}}{u_{0} + v_{0}} ⌉ ≤ \frac{α_{k}^{2} − α_{k}^{1}}{u_{0}} ,

ami v_{0} > 1 miatt igaz, u_{0} < 0 esetén pedig az

⌈\frac{α_{k}^{2} − α_{k}^{1}}{u_{0} + v_{0}} ⌉ ≥ \frac{α_{k}^{2} − α_{k}^{1}}{u_{0}} ,

ami v_{0} < 1 miatt teljesül. Mint említettük, a többi eset is hasonlóan bizonyítható.

Megmutatjuk azt is, hogy az így nyert vágás érvényes marad a vegyes programozási feladatra. A következő tétel bizonyítása L. Wolsey-tól származik, az alapötlet viszont megtalálható a [12] jegyzetben, a vegyes Gomory-vágás élesítésére adott eljárásban.

4.3. Tétel. A fent definiált |β|γx ≥ β vágás érvényes a vegyes programozási feladatra, azaz a vegyes programozási feladat minden megengedett megoldása kielégíti a |β|γx ≥ β egyenlőtlenséget.

Bizonyítás. Úgy fogjuk a tétel állítását megmutatni, hogy belátjuk, hogy a vágás a vegyes programozási feladatra érvényes diszjunkcióból származik. Tegyük fel, hogy a következő érvényes diszjunkciót használtuk vágásgenerálásra a −x_{j} ≥ 0 ∨ x_{j} ≥ 1 helyett:

−x_{j} + m̄x ≥ 0 ∨ x_{j} − m̄x ≥ 1,

ahol m̄ olyan egész vektor, melyre m̄_{k} = 0, k = p + 1, …, n esetén. Ekkor a vágás együtthatóira az új diszjunkcióból

γ_{k} = min \{\frac{1}{|β|}(α_{k}^{1} + u_{0}m̄_{k}), \frac{1}{|β|}(α_{k}^{2} − v_{0}m̄_{k})\} k = 1, …, p

γ_{k} = max \{\frac{1}{|β|}α_{k}^{1}, \frac{1}{|β|}α_{k}^{2}\} k = p + 1, …, n

adódik. Megválaszthatjuk az m̄_{k}, k = 1, …, p egész számokat úgy, hogy γ_{k}, k = 1, …, p olyan kicsi legyen, amilyen kicsi csak lehet. Könnyen látható, hogy ez épp akkor valósul meg, amikor m̄_{k} := ⌈m_{k}⌉ választással élünk. Ekkor

γ_{k} = min \{\frac{1}{|β|}(α_{k}^{1} + u_{0}⌈m_{k}⌉), \frac{1}{|β|}(α_{k}^{2} − v_{0}⌊m_{k}⌋)\} k = 1, …, p

γ_{k} = max \{\frac{1}{|β|}α_{k}^{1}, \frac{1}{|β|}α_{k}^{2}\} k = p + 1, …, n,

amiből a tétel állítása következik. □

Megjegyezzük, hogy ha m_{k} = 0, akkor a |β|γ_{k} együtthatók megegyeznek az α_{k}- kal. Megmutatható, hogy ez az eset fordul elő minden olyan k komponensre, melyre x_{t}^{k} = 1. Ha kicseréljük ebben az esetben az x_{k} változót a komplementerére, majd ezután ismét alkalmazzuk az élesítési eljárást, kaphatunk olyan m_{k}-t, mely nem 0. Ezt az elvet követve az algoritmus hatékonyabbá tehető.

Megjegyezzük azt is, hogy amíg az Āx ≥ b̄ rendszer olyan lineáris transzformációja, mely változatlanul hagyja K-t, P_{j}(K)-t és a lapjaikat, megváltoztathatja az élesítési eljárás hatását. Tegyük fel ugyanis, hogy ahelyett, hogy az x_{j} = 0 ∨ x_{j} = 1 diszjunkciót alkalmaznánk az Āx ≥ b̄ rendszerre, először megoldjuk a min{cx : Āx ≥ b̄} lineáris programozási feladatot, és így az Āx ≥ b̄ rendszerre a következő kifejezést nyerjük:

x_{i} = ā_{i0} + ∑_{k∈J} ā_{ik}(−x_{k}) i ∈ I  (15)
x_{k} ≥ 0, k ∈ I ∪ J,

ahol I a bázisbeli változók, J pedig a nembázisbeli változók indexei. Átírva (15)-öt, kapjuk az alábbi kifejezést:

− ∑_{k∈J} ā_{ik}x_{k} ≥ −ā_{i0}, i ∈ I  (16)
x_{k} ≥ 0, k ∈ J.

Tegyük fel, hogy j ∈ I. Ekkor az x_{j} = 0 ∨ x_{j} = 1 diszjunkciót a következő alakban írhatjuk fel:

∑_{k∈J} ā_{jk}x_{k} ≥ ā_{j0} ∨ − ∑_{k∈J} ā_{jk}x_{k} ≥ 1 − ā_{j0}.  (17)

Látható, hogy most a (16) és (17) által meghatározott vágások az x_{k}, k ∈ J változókkal vannak kifejezve. Sőt, habár ezek a vágások ekvivalensek azokkal, amelyeket az Āx ≥ b̄ rendszerből nyerhetünk az x_{j} = 0 ∨ x_{j} = 1 diszjunkció segítségével, az élesítési eljárást alkalmazva rájuk, a végeredmény a két esetben különbözhet. Mindenek előtt, az első esetben az élesítési eljárást minden α_{k}, k = 1, …, p együtthatóra alkalmazhatjuk, a másik esetben viszont csak azon α_{k} együtthatókra, melyekre k ∈ {1, …, p}∩J teljesül. Másodszor, az így nyert különböző számértékek különböző m_{k} paraméterekhez vezethetnek a két esetben.

Az ok, amiért érdemes a (16)-ból és (17)-ből nyerhető vágások élesítéseivel foglalkozni az az, hogy a [6]-ban szereplő Gomory-féle vegyes vágások ebbe a családba tartoznak. Azaz általánosan azt mondhatjuk, hogy bármely Gomory-féle vegyes vágáshoz van olyan vágás az általunk ismertettek közül, mely nem gyengébb. Ahhoz, hogy ezt belássuk, a fenti vágások általános alakját kell előállítanunk, majd az előállításukban szereplő szorzóknak kell speciális értékeket adnunk. Először a P_{j}^{∗}(K)-t meghatározó (14) rendszert alakítjuk át a (16)-ban és (17)-ben használt változók szerint. Ekkor (14) a következő alakú lesz:

α_{k} + ∑_{i∈I} u_{i}^{1}ā_{ik} − u_{0}ā_{jk} ≥ 0 ha k ∈ J
α_{k} + ∑_{i∈I} v_{i}^{1}ā_{ik} + v_{0}ā_{jk} ≥ 0 ha k ∈ J
− ∑_{i∈I} u_{i}^{1}ā_{i0} + u_{0}ā_{j0} = β
− ∑_{i∈I} v_{i}^{1}ā_{i0} + v_{0}(1 − ā_{j0}) = β.

Mint az előbb, most is előállítható az αx ≥ β vágás egy ekvivalens alakban, mégpedig α_{k} = max{α_{k}^{1}, α_{k}^{2}} alakban, ahol

α_{k}^{1} = − ∑_{i∈I} u_{i}^{1}ā_{ik} + u_{0}ā_{jk}, α_{k}^{2} = − ∑_{i∈I} v_{i}^{1}ā_{ik} + v_{0}ā_{jk}, ha k ∈ J,

és

β = − ∑_{i∈I} u_{i}^{1}ā_{i0} + u_{0}ā_{j0} = − ∑_{i∈I} v_{i}^{1}ā_{i0} + v_{0}(1 − ā_{j0}).

Az élesített vágás ekkor itt is |β|γx ≥ β, ahol γ_{k}-t és m_{k}-t ugyanúgy definiáljuk, mint az előző esetben. Most már beláthatjuk az ígért állítást. 4.4. Tétel. A Gomory-féle vegyes vágás |β|γx ≥ β alakú, ahol az együtthatókat a következő módon határozzuk meg:

u_{i}^{1} = 0, v_{i}^{1} = 0, i ∈ I
u_{0} = 1/ā_{j0}, v_{0} = 1/(1 − ā_{j0}).

Bizonyítás. A tételben definiált együtthatókat használva

α_{k}^{1} = ā_{jk}/ā_{j0}, α_{k}^{2} = −ā_{jk}/(1 − ā_{j0}), k ∈ J,

és β = 1 adódik. Ezeket helyettesítve a γ_{k}-t, m_{k}-t definiáló egyenletekbe, kapjuk, hogy m_{k} = −ā_{jk} és

γ_{k} = min \{\frac{ā_{jk} + ⌈−ā_{jk}⌉}{ā_{j0}}, \frac{−ā_{jk} − ⌊−ā_{jk}⌋}{(1 − ā_{j0})}\} ha k = 1, …, p

γ_{k} = max \{\frac{ā_{jk}}{ā_{j0}} , \frac{−ā_{jk}}{(1 − ā_{j0})}\} ha k = p + 1, …, n,

ami viszont épp a Gomory-féle vegyes vágás. □

A Branch-and-Cut algoritmus

Ebben a fejezetben a korábbiakban kidolgozott vágás típusú algoritmusban használt vágó síkokat illesztjük be az egészértékű programozásban gyakran és eredményesen alkalmazott Branch-and-Bound algoritmus keretei közé. Ezáltal még hatékonyabb algoritmust nyerünk a vegyes programozási feladatra. Először ismertetjük röviden a Branch-and-Bound algoritmust, majd bemutatjuk az elágazás és vágás algoritmus egy vázát, melyet a további szakaszokban pontosítunk, illetve megmutatjuk, hogyan használhatjuk az általunk vizsgált vágásokat. Így végül megkapjuk azt az elágazás és vágás, vagy Branch-and-Cut algoritmust, mely a [4]-ben közölt számítási tapasztalok alapján a leghatékonyabb a vegyes programozási feladatot megoldó eddig ismert algoritmusok közül.

5.1 Branch-and-Bound

A Branch-and-Bound, vagy magyarul korlátozás és szétválasztás algoritmus filozófiája a következő. Vegyük ebben az esetben is az eredeti feladat egy LP relaxációját. Oldjuk meg a relaxációt. Ha szerencsénk van, megengedett megoldáshoz jutunk és így megoldjuk az eredeti feladatunkat. Ha nem megengedett az LP feladat megoldása során nyert aktuális megoldás, akkor van olyan koordináta, legyen például az iedik, mely nem egész, holott egészértékűségi feltételt kell kielégítenie az eredeti problémában. Válasszuk szét ekkor a relaxált halmazt néhány részre úgy, hogy az egyes részekben a változó i-edik koordinátája csak egy adott egész értéket vehet fel. A kapott részekre ismét megoldva a megfelelő LP feladatot, tovább folytathatjuk a módszert. Lényegesen hatékonyabbá tehető a módszer, ha figyelembe vesszük azt a triviális megjegyzést, miszerint nem szükséges tovább vizsgálni azokat a részeket, melyekre a LP relaxáció nem ad jobb megoldást, mint az eddig ismert legjobb megengedett megoldás. Érdemes tehát egy változóban tárolni az eddig megtalált legjobb megengedett megoldást, és azon szétválasztott részeket kizárni a további vizsgálódásból, melyeken az LP ralaxáció nem talál jobbat. Matematikailag a következő módon írhatjuk le az algoritmust abban az esetben, amikor egy halmazt mindig csak két részre vágunk szét.

Tekintsük a következő egészértékű programozási feladatot:

min{cx : Ax ≤ b, x ∈ Z^{n}},

ahol Z^{n} jelöli az n dimenziós egészkoordinátájú vektorok halmazát. Legyen Π_{1} := {P }, ahol P := {x : Ax ≤ b}. Minden k-ra definiáljuk Π_{k}-t, mint poliéderek k elemű halmazát, mely kielégíti az alábbi két feltételt:

(i) Ha Π_{k} = {P_{1}, …, P_{k}}, akkor P_{1}, …, P_{k} páronként diszjunkt poliéderek R^{n}- ben.

(ii) Minden olyan csupa egész koordinátájú vektor, mely benne van P -ben, benne van P_{1} ∪ … ∪ P_{k}-ban is. A kiindulási Π_{1} halmaz triviálisan eleget tesz e két feltételnek. Ha van egy ilyen rendszerünk, akkor növelhetjük az elemek számát úgy, hogy a fenti két tulajdonságot megtartjuk. Legyen μ_{j} a j-edik poliéderhez tartozó LP feladat optimális megoldása, azaz legyen μ_{j} := min{cx : x ∈ P_{j}}, j = 1, …, k esetén. Válasszuk meg a j^{∗} indexet úgy, hogy μ_{j^{∗}} = min{μ_{j} : j = 1, …, k} teljesüljön. Legyen a j = j^{∗}-hoz tartozó optimális megoldás x^{∗} := (x_{1}^{∗}, …, x_{n}^{∗}). Két eset lehetséges:

1. eset: x^{∗}-nak nem minden koordinátája egész. Válasszunk ki ekkor egy nem egész koordinátát, például x_{i}^{∗}-ot, és definiáljuk a következő két poliédert:

Q_{1} := {x ∈ P_{j^{∗}} : x_{i} ≤ ⌊x_{i}^{∗}⌋}
Q_{2} := {x ∈ P_{j^{∗}} : x_{i} ≥ ⌈x_{i}^{∗}⌉}.

Legyen ezen kívül Π_{k+1} a következő módon definiálva:

Π_{k+1} := {P_{1}, …, P_{j^{∗}−1}, Q_{1}, Q_{2}, P_{j^{∗}+1}, …, P_{k}}.

Könnyen látható, hogy Π_{k+1} kielégíti az (i), (ii) feltételeket, azaz k := k + 1 értékadással folytathatjuk az eljárást.

2. eset: x^{∗}-nak minden koordinátája egész. Ekkor x^{∗} megengedett megoldása az egészértékű programozási feladatnak, és (ii) miatt optimális megoldása is.

A fenti eljárás csak egy keret, a konkrét megvalósításhoz és a végesség bizonyításához pontosítani kell.

Az algoritmus átfogóbb vizsgálata megtalálható a [12] jegyzetben, illetve a [10] könyvben.

5.2 Az elágazás és vágás algoritmus

Az algoritmus megfogalmazásához szükségünk lesz néhány jelölésre, elnevezésre. Hasonlóan az előző fejezetekhez, a vegyes programozási feladatot a következő formában tekintjük:

min{cx : Ax ≥ b, x ≥ 0, x_{j} ∈ {0, 1}, j = 1, …, p}.

Az elágazás és vágás algoritmus egy fontos lépése az lesz, amikor a standard lineáris programozási relaxációt, {x : Ax ≥ b, x ≥ 0, x_{j} ≤ 1, j = 1, …, p}-t, kibővítjük néhány olyan egyenlőtlenséggel, amely érvényes a vegyes programozási feladatra, miközben néhány 0-1 változót rögzítünk a felső vagy az alsó korlátján. Az algoritmus futása során az éppen aktuális, a vegyes programozási feladatra érvényes egyenlőtlenségek családját C-vel jelöljük. Feltesszük továbbá, hogy a C-t definiáló Mx ≥ d rendszer mindig tartalmazza az Ax ≥ b, x ≥ 0, x_{i} ≤ 1, i = 1, …, p egyenlőtlenségeket. F_{0}, F_{1} ⊆ {1, …, p} jelöli azokat a változókat, melyeket 0-n, illetve 1-en rögzítettünk. Legyen továbbá

K(C, F_{0}, F_{1}) := {x : Mx ≥ d, x_{i} = 0 ha i ∈ F_{0}, x_{i} = 1 ha i ∈ F_{1}},

és jelöljük LP(C, F_{0}, F_{1})-gyel a következő lineáris programozási feladatot:

min{cx : x ∈ K(C, F_{0}, F_{1})}.

Az (F_{0}, F_{1}) rendezett párokat egy S listában tároljuk, a lista elemeit csúcsoknak nevezzük. Az elnevezés onnan adódik, hogy az S lista egy fagráfot reprezentálhat, amit gyakran leszámlálási fának neveznek. Ebben a gráfban csúcsoknak felelnek meg az (F_{0}, F_{1}) rendezett párok. Tároljuk az UB változóban az aktuális felső korlátot, vagyis az eddig talált legjobb célfüggvényértékét a vegyes programozási feladatnak.

A fenti jelölések segítségével már megfogalmazhatjuk a Branch-and-Cut algoritmus vázát, amit aztán majd a következő szakaszokban konkrétabbá teszünk. Megjegyezzük, hogy a jelenlegi változatban C-ből nem hagyunk el egyenlőtlenséget, hanem fokozatosan feltöltjük. A továbbiakban javítunk majd ezen.

3. Algoritmus

0. Lépés: Inicializálás. Legyen kezdetben S := {(F_{0} = ∅, F_{1} = ∅)}, álljon C a standard lineáris programozási relaxációból, és legyen UB := ∞.

1. Lépés: Csúcs választás. Ha S = ∅, akkor STOP. Minden más esetben válasszunk egy (F_{0}, F_{1}) rendezett párt S-ből és töröljük is a listából.

2. Lépés: Korlátozás. Oldjuk meg az LP(C, F_{0}, F_{1}) lineáris programozási feladatot. Ha nincs megengedett megoldás, ugorjunk az 1. Lépésre. Ellenkező esetben jelöljük az optimális megoldást x̄-sal. Ha cx̄ ≥ UB, akkor ugorjunk az 1. Lépésre. Ha x̄_{j} ∈ {0, 1}, j = 1, …, p-re, akkor legyen x^{∗} := x̄, UB := cx̄, és ugorjunk szintén az 1. Lépésre.

3. Lépés: Elágazás vagy vágás? Generáljunk vágást? Ha igen, akkor ugorjunk a 4. Lépésre, ha nem, akkor az 5. Lépésre.

4. Lépés: Vágások generálása. Generáljunk egy αx ≥ β vágást, mely érvényes a vegyes programozási feladatra, de x̄-ra nem. Adjuk ezt az egyenlőtlenséget C-hez, majd ugorjunk a 2. Lépésre.

5. Lépés: Elágazás. Válasszunk egy indexet, melyre 0 < x̄_{j} < 1 teljesül. Generáljuk az (F_{0} ∪ {j}, F_{1}) és (F_{0}, F_{1} ∪ {j}) rendezett párokhoz tartozó részproblémákat, majd adjuk őket S-hez. Ugorjunk az 1. Lépésre.

Amikor az algoritmus befejeződik, ha UB < ∞, akkor x^{∗} optimális megoldása a vegyes programozási feladatnak. Minden más esetben a vegyes programozási feladatnak nincs megengedett megoldása.

Mint említettük, a fenti algoritmus csak egy váz. Ha pontosabbá akarjuk tenni, akkor a következő dolgokat kell tüzetesebben megvizsgálnunk. Nagyon fontos, hogy ha generálunk egy vágást a leszámlálási fa egy csúcsában, akkor ez a vágás érvényes legyen az összes többi csúcsra. Fontos megemlíteni azt is, hogy szükségünk lesz valamilyen módon “mérni” a vágásokat, hogy ki tudjuk választani a lehető legjobbat. Ezt a már korábban említett legmélyebb vágás keresésével érhetjük el. Természetesen egy konkrét algoritmus megvalósításához azt is el kell döntenünk pontosan, hogy a 3. Lépésben mikor generálunk vágást illetve mikor ágazunk el. Ha a döntésünk elágazás, akkor azt is pontosítanunk kell, hogy milyen stratégia alapján válasszuk ki azt a csúcsot a leszámlálási fából, ami szerint elágazunk.

Az első kivételével ezekre a kérdésekre nem adható szabatos, teljes matematikai válasz. A következő szakaszokban inkább csak ismertetjük a lehetőségeket, variánsokat. Más-más variációt alkalmazva más-más algoritmus adódik, melyek hatékonyságát abszolút módon nem tudjuk összehasonlítani. Sokat számíthat például az, hogy milyen az aktuális, megoldandó problémánk szerkezete. Ettől függően lehet, hogy különböző variációk adnak hatékonyabb megoldási módszereket különböző feladatok esetén. Számítási tapasztolatokat közöl a fent említett problémákra a [4] cikk.

5.3 Vágások generálása, felemelése

Tegyük fel, hogy a 3. Lépésben vágás generálása mellett döntöttünk. Mint említettük, a korábban ismertetett vágásokat szeretnénk felhasználni. A 4. fejezetben a vágás típusú algoritmus megfogalmazásához olyan síkokat generáltunk, amelyekben minden változó szabad változó volt abban az értelemben, hogy nem rögzítettük egy változó értékét sem. Ha be akarjuk építeni ezeket a vágásokat a Branch-and-Bound algoritmusba, akkor először azt kell megmutatnunk, hogy hogyan tudunk olyan vágást generálni, melyben néhány változó rögzített.

Ismét a P_{j}(K)-t definiáló egyenlőtlenségeket határozzuk meg, most azonban egy kicsit általánosabb formában. Legyen K := K(C, F_{0}, F_{1}) és F := {1, …, n}\(F_{0} ∪ F_{1}) a szabad változók halmaza az (F_{0}, F_{1}) csúcsban. Feltehetjük az általánosság megszorítása nélkül, hogy F_{1} = ∅, ugyanis ha F_{1} ≠ ∅ állna, akkor az összes F_{1}-beli x_{k} változót helyettesíthetnénk 1 − x_{k}-val. Ekkor a ∑_{i∈F} α_{i}x_{i} ≥ β, vagy rövid jelöléssel az α^{F} x^{F} ≥ β egyenlőtlenség pontosan akkor érvényes P_{j}(K)-ra, ha léteznek u^{F} , v^{F} vektorok és u_{0}, v_{0} valós számok, melyekre

α^{F} − u^{F} M^{F} − u_{0}e_{j}^{F} ≥ 0
α^{F} − v^{F} M^{F} − v_{0}e_{j}^{F} ≥ 0
u^{F} d^{F} = β  (18)
v^{F} d^{F} + v_{0} = β
u^{F} , v^{F} ≥ 0,

ahol e_{j}^{F} a j-edik egységvektor R^{|F |}-ben, M^{F} az a mátrix, melyet úgy kapunk M-ből, hogy töröljük az M_{i}, i ∈ F_{0} oszlopokat és azokat a sorokat, melyek az x_{i} ≥ 0, i = 1, …, n illetve a −x_{i} ≥ −1, i ∈ {1, …, p}∩F_{0} egyenlőtlenséghez tartoznak, d^{F} pedig úgy adódik d-ből, hogy azokat a komponenseket töröljük, melyek az M-ből törölt sorokhoz tartoznak.

Legyen x̄ az LP(C, F_{0}, F_{1}) feladat optimális megoldása. Tegyük fel, hogy x̄ nem megengedett megoldása a vegyes programozási feladatnak és legyen j ≤ p egy olyan index, melyre 0 < x̄_{j} < 1, azaz amelyre a 0-1 feltétel sérül. Abból a célból, hogy egy olyan P_{j}(K)-ra érvényes egyenlőtlenséget találjunk, amely levágja x̄-t, meg kell oldanunk a következő lineáris programozási feladatot:

max{β − α^{F} x̄^{F} : (α^{F} , β) kielégíti (18)-at és (α^{F} , β) ∈ S},

ahol S a szokásos normalizációk egyike. Mint ahogy az ezzel analóg lineáris programozási feladat optimális megoldását, az itteni optimumot is a legmélyebb vágásnak nevezzük. Megjegyezzük azonban, hogy ez a vágás csak az aktuális csúcsra érvényes, hiszen azon változók, melyek indexe eleme F_{0}-nak, eltűntek a vágásból. A továbbiakban megmutatjuk, hogy hogyan lehet egy ilyen vágást érvényessé tenni az egész leszámlálási fára. Ehhez egy még általánosabb vágásgeneráló lineáris programozási feladatot írunk fel.

Legyen R ⊆ {1, …, n} teszőleges részhalmaz, e_{j}^{R} legyen a j-edik egységvektor R^{|R|}-ben. Legyen ezen kívül M^{R} az a mátrix, melyet úgy kapunk M-ből, hogy töröljük az M_{i}, i ∉ R oszlopokat, valamint azokat a sorokat, melyek az x_{i} ≥ 0, i = 1, …, n és a −x_{i} ≥ −1, i ∈ {1, …, p}\R egyenlőtlenségekhez tartoznak. A d^{R} vektort úgy kapjuk d-ből, hogy töröljük azokat a komponenseket, melyek az M-ből törölt sorokhoz tartoznak. Jelöljük LP(R)-rel a következő lineáris programozási feladatot:

max β − α^{R}x̄^{R}
α^{R} − u^{R}M^{R} − u_{0}e_{j}^{R} ≥ 0
α^{R} − v^{R}M^{R} − v_{0}e_{j}^{R} ≥ 0
u^{R}d^{R} = β
v^{R}d^{R} + v_{0} = β
u^{R}, v^{R} ≥ 0
(α^{R}, β) ∈ S.

Megjegyezzük, hogy LP(R) minden optimális megoldására α_{i}^{R} = max{α_{i}^{1}, α_{i}^{2}} teljesül i ∈ R esetén, ahol

α^{1} = u^{R}M^{R} + u_{0}e_{j}^{R}, α^{2} = v^{R}M^{R} + v_{0}e_{j}^{R}.

Most már rátérünk a vágások felemelésére, vagyis arra a feladatra, hogy egy csúcsban generált vágást érvényessé tegyük az összes többi csúcsra. Általánosságban az mondható, hogy egy (F_{0}, F_{1}) csúcsban generált vágás csak akkor érvényes, ha azokat a változókat, melyeknek indexei az F_{0} ∪ F_{1} halmazba esnek, rögzítjük a megfelelő értékeiken. Így a vágás nem feltétlenül érvényes a vegyes programozási feladatra, tehát nem használhatjuk a leszámlálási fa más csúcsaiban. Számítástechnikai nézőpontból rendkívül fontos az, hogy a generált vágást érvényessé tegyük a leszámlálási fa összes csúcsára. Egyrészt ezáltal lecsökkentjük a szükséges memória méretét, másrészt a csúcsok korlátai is javulhatnak. Úgy teszünk érvényessé egy (F_{0}, F_{1}) csúcsban generált vágást az egész vegyes programozási feladatra, hogy kiszámoljuk a megfelelő együtthatóit azon x_{j} változóknak, melyek indexeire j ∈ F_{0} ∪ F_{1} teljesül. Ezt a műveletet nevezik a vágás felemelésének.

Legyen tehát x̄ az LP(C, F_{0}, F_{1}) lineáris programozási feladat optimális megoldása. Egy olyan x̄^{R} vektorral fogunk dolgozni a továbbiakban, melyet úgy kapunk x̄-ból, hogy legalább azokat a komponenseket megtarjuk, melyekre 0 < x̄_{j} < 1, j ≤ p és x̄_{i} > 0, i > p teljesül. Miután R-et rögzítettük, a vágásokat az x^{R} változók terében generáljuk, majd ezt emeljük fel az eredeti térbe. Az általánosság megszorítása nélkül feltehetjük, hogy ha i ∉ R, akkor x̄_{i} = 0, mivel az olyan i indexekre, melyekre x̄_{i} = 1 végrehajthatjuk a komplementerrel való helyettesítést. Legyen j ∈ {1, …, p} olyan index, melyre 0 < x̄_{j} < 1. Tekintsük azt az α^{R}x^{R} ≥ β egyenlőtlenséget, melyet az LP(R) lineáris programozási feladat megoldásával generáltunk. A következő tétel azt mutatja meg, hogy hogyan terjeszthetjük ki a fenti vágást egy αx ≥ β, az egész vegyes programozási feladatra érvényes vágássá. 5.1. Tétel. Legyen (α^{R}, β) az LP(R) feladat optimális megoldása, ahol R ⊇ {i ∈ {1, …, p} : 0 < x̄_{i} < 1} ∪ {i ∈ {p + 1, …, n} : x̄_{i} > 0}. Az általánosság megszorítása nélkül feltehetjük, hogy {i ∈ {1, …, p} : x̄_{i} = 1} = ∅. Ekkor az alábbi αx ≥ β egyenlőtlenség érvényes a vegyes programozási feladatra és levágja x̄-t:

α_{i} = \{ \begin{matrix}α_{i}^{R} & ha i ∈ R, \\ max\{α_{i}^{1}, α_{i}^{2}\} & ha i ∉ R, \end{matrix}

ahol M_{i} az M i-edik oszlopa, α_{i}^{1} = u^{R}M_{i}^{R}, α_{i}^{2} = v^{R}M_{i}^{R} és M_{i}^{R} jelöli azt a részvektorát M_{i}-nek, melynek azonosak a sorindexei M^{R} sorindexeivel. Bizonyítás. Mivel i ∉ R-ből x̄_{i} = 0 következik, világos, hogy a fent definiált αx ≥ β vágás levágja x̄-t, így elég azt megmutatnunk, hogy αx ≥ β érvényes a vegyes programozási feladatra. Ehhez elég azt megmutatnunk, hogy (α^{N}, β) := (α, β) megengedett megoldása az LP(N) lineáris programozási feladatnak, ahol N = {1, …, n}. Az LP(R) és az LP(N) lineáris programozási feladatok abban térnek el egymástól, hogy az LP(N) feladat több változót és több feltételt tartalmaz, nevezetesen az

α_{i}^{N} − u^{N}M_{i}^{N} ≥ 0 i ∈ N\R

α_{i}^{N} − v^{N}M_{i}^{N} ≥ 0 i ∈ N\R

feltételeket és az u_{i}, v_{i} változókat, melyek azokhoz a −x_{i} ≥ −1, i ∈ N\R feltételekhez tartoznak, amelyeket töröltünk az M^{N}x ≥ d^{N} rendszerből. A fentiek alapján könnyen nyerhetünk megengedett megoldást az LP(N) feladatra az LP(R) feladat egy megengedett megoldásából. Legyenek ugyanis az új u_{i}, v_{i} változók mindegyike 0 és ha α_{i}-t i ∈ N\R esetén a tétel állításának megfelelően definiáljuk, akkor az új feltételek is teljesülnek, vagyis megengedett megoldást nyertünk az LP(N) feladatra. □

Ezek után azt mutatjuk meg, hogy ha az 1. Normalizációt alkalmazzuk, akkor az előző tétel során nyert vágás ugyanaz, mint amit az LP(N) feladat megoldásával nyernénk. Azt mondhatjuk tehát, hogy az 1. Normalizáció alkalmazása esetén a vágást “optimálisan” emelhetjük fel, hiszen nem csak megengedett megoldást, hanem optimális megoldást nyerünk az LP(N) feladatra.

Tekintsük tehát a (11) lineáris programozási feladatot. Emlékeztetve a korábbiakra, a (11) feladat a vágásgeneráló LP méretének redukálásával nyerhető. A könnyebb követhetőség kedvéért az új jelölésekkel ismét felírjuk a (11) feladatot.

min u(Mx̄) + u_{0}x̄_{j}
uM − vM + (u_{0} − v_{0})e_{j} = 0
ud = β  (19)
vd + v_{0} = β
u, v ≥ 0,

ahol természetesen β = 1 vagy β = −1. Most már felírhatjuk (19) új alakját, amelyből csak az aktuális csúcsra érvényes vágást nyerhetjük.

min ∑_{k∈R} uM_{k}^{R}x̄_{k} + u_{0}x̄_{j}

uM_{k}^{R} − vM_{k}^{R} = 0, k ∈ R\{j}
uM_{j}^{R} − vM_{j}^{R} + u_{0} − v_{0} = 0

ud^{R} = β  (20)
vd^{R} + v_{0} = β
u, v ≥ 0,

ahol R, d^{R}, M^{R} definíciója megegyezik a korábbiakkal.

Megjegyezzük, hogy néhány olyan változó és feltétel, amely megtalálható volt (19)-ben hiányzik (20)-ból. A hiányzó feltételek a következők:

uM_{k} − vM_{k} = 0 k ∉ R,

míg a hiányzó változók u_{m+i}, v_{m+i}, i ∉ R esetén és u_{m+n+i}, v_{m+n+i}, i ∈ {1, …, p}, i ∉ R esetén. Itt az m + 1, …, m + n indexek az x_{h} ≥ 0, h = 1, …, n feltételekhez, az m + n + 1, …, m + n + p indexek pedig a −x_{h} ≥ −1, h = 1, …, p feltételekhez tartoznak. A következő tétel azt állítja, hogy (20) egy optimális megoldását ki lehet terjeszteni (19) egy optimális megoldásává.

5.2. Tétel. Legyen w^{R} := (u^{R}, u_{0}^{R}; v^{R}, v_{0}^{R}) (20) egy optimális megoldása. Terjesszük ki w^{R}-t a w̄ := (ū, ū_{0}; v̄, v̄_{0}) vektorrá a következő módon. Legyen

ū_{0} := u_{0}^{R}
v̄_{0} := v_{0}^{R}
ū_{i} := u_{i}^{R} ha i = 1, …, m
v̄_{i} := v_{i}^{R} ha i = 1, …, m
ū_{m+i} := \{ \begin{matrix}(v^{R} − u^{R})M_{i}^{R} & ha v^{R}M_{i}^{R} > u^{R}M_{i}^{R} és i ∉ R \\ 0 & egyébként, ha i ∉ R \end{matrix}
v̄_{m+i} := \{ \begin{matrix}(u^{R} − v^{R})M_{i}^{R} & ha u^{R}M_{i}^{R} > v^{R}M_{i}^{R} és i ∉ R \\ 0 & egyébként, ha i ∉ R \end{matrix}
ū_{m+n+i} := v̄_{m+n+i} := 0  ha i ∈ {1, …, p} és i ∉ R.

Ekkor w̄ optimális megoldása lesz (20)-nak.

Bizonyítás. A konstrukcióból azonnal látható, hogy a hiányzó feltételeket kielégíti w̄, míg a régi feltételek teljesülésére nincsenek hatással az új változók értékei. Más szavakkal w̄ megengedett megoldása (19)-nek.

Belátjuk, hogy w̄ optimális megoldás. Legyen z^{R} (20) duáljának optimális megoldása. Terjesszük ki z^{R}-t (19) duáljának optimális megoldásává úgy, hogy minden olyan komponensnek, amelyek a (20)-ból hiányzó (19)-beli feltételekhez tartoznak, adjunk 0 értéket. Ekkor (20) redukált költsége változatlan marad (19)-ben. Megvizsgáljuk, hogy hogyan változtak meg azon (19)-beli változók költségei, amelyek hiányoznak (20)-ból.

Az ū_{m+n+i} változó redukált költsége i ∈ {1, …, p}, i ∉ R esetén

−x̄_{i} − (−z_{0u}^{R}) = z_{0u}^{R} (mivel x̄_{i} = 0),

ahol z_{0u}^{R} az a duál változó, amely (20) ud^{R} = β feltételéhez tartozik.

A v̄_{m+n+i} változók redukált költsége i ∈ {1, …, p}, i ∉ R esetén

0 − (−z_{0v}^{R}) = z_{0v}^{R},

ahol z_{0v}^{R} az a duálváltozó, amely (20) vd^{R} + v_{0} = β feltételéhez tartozik. Az ū_{m+i} változók redukált költsége i ∈ {1, …, n}, i ∉ R esetén

x̄_{i} − (−0) = 0 (mivel x̄_{i} = 0)

és végül a v̄_{m+i} változók redukált költsége i ∈ {1, …, n}, i ∉ R esetén

0 − (0) = 0.

Most, hogy ha (20) első |R| feltételéhez tartozó duál változókat z_{k}^{R}-rel jelöljük k ∈ R esetén, akkor (20) duáljában megtalálhatók lesznek a következő feltételek: −z_{j}^{R} − z_{0u}^{R} ≤ −x̄_{j}, z_{j}^{R} ≤ x̄_{j}, z_{j}^{R} − z_{0v}^{R} ≤ 0, −z_{j}^{R} ≤ 0. Így z_{0u}^{R} ≥ 0 és z_{0v}^{R} ≥ 0 adódik, vagyis minden redukált költség nemnegatív, amiből viszont egyből kapjuk, hogy w̄ optimális megoldása (19)-nek. □

Az előző tétellel analóg állítást nem lehet megfogalmazni a 2. illetve a 3. Normalizációra. Ellenben az alábbi normalizációkat használva analóg tétel bizonyítható.

4. Normalizáció. S := {(α, β) : −1 ≤ α_{i} ≤ 1 ha i ∈ R}.

5. Normalizáció. S := {(α, β) : ∑_{i∈R} |α_{i}| ≤ 1}.

Azt is meg lehet mutatni, hogy a 2. Algoritmus végességének bizonyítása módosítható arra az esetre, amikor a fenti két normalizáció egyikét használjuk, tehát nem befolyásolja az algoritmus végességét, ha a fentiek valamelyikére változtatjuk a normalizációt.

A felemelési eljárás számítástechnikai szempontból olcsó, ugyanis minden egyes együtthatót meg lehet kapni O(M^{R} sorainak száma) idő alatt. Összefoglalásképp elmondhatjuk, hogy egyrészt az 5.1. Tétel olyan R választással, melyre R∩(F_{0}∪F_{1}) = ∅, egyszerű és hatékony módszert ad arra, hogy egy vágást érvényessé tegyünk az egész vegyes programozási feladatra. Másrészről a megoldandó vágásgeneráló lineáris programozási feladat méretét jól kézben tudjuk tartani, ha R-et olyan kicsire választjuk, amilyen kicsire csak lehet. Ezért a továbbiakban az R := {i ∈ {1, …, p} : 0 < x̄_{i} < 1} ∪ {i ∈ {p + 1, …, n} : x̄_{i} > 0} választással élünk.

5.4 Az “Elágazás vagy vágás?” probléma

Az előző szakaszban nem hangsúlyoztuk, de számítástechnikai szempontból mindenképp hasznos, hogy ha vágást generálunk, akkor érdemes egyszerre többet generálnunk. A ráfordított idő rögzített csúcs esetén nem számottevő, viszont az algoritmus hatékonyságát nagymértékben növelheti. Elöljáróban tehát annyit jegyzünk meg, hogy vágásgenerálásnál adott számú vágást generálunk egyszerre. A generálandó vágások számát a MAXROUND változó mutatja.

Az egyik legfontosabb döntés, melyet az algoritmus futása során hoznunk kell a 3. Lépésben található. Itt ugyanis azt kell eldöntenünk, hogy vágást érdemes-e generálnunk, vagy jobban megéri elágaznunk. Mint említettük, szabatos, matematikai választ nem remélhetünk erre a kérdésre. Megpróbáljuk azonban összegyűjteni azokat a szokásos eljárásokat, módszereket, amelyeket e kérdés eldöntésében leggyakrabban alkalmaznak.

Először ismertetjük az úgynevezett \underline{fix stratégiát}. Rögzítsünk egy k természetes számot. Generáljunk vágást minden k-adik csúcs esetén. A [4]-ben közölt számítási tapasztalatok alapján a következőket mondhatjuk el a fix stratégiáról. Számos probléma esetén még viszonylag nagy k választása esetén is hatékonyabbá tette az algoritmust a vágások generálása, mint ha csak a Branch-and-Bound algoritmust futtatuk volna. Sőt, a legtöbb probléma esetén már néhány vágás generálásával sikerült elérni azt, hogy viszonylag hamar véget érjen az algoritmus futása, míg ha csak a Branch-and-Bound algoritmust futtatuk volna, túlléptük volna az időkorlátot. Másrészről viszont azt mondhatjuk, hogy ha k-t kicsire választjuk, azaz ha gyakran generálunk vágást, akkor a futási idő szintén megnőhet. E két szélsőséges eset között kell megtalálni az optimumot. Újra csak a számítási tapasztalatokra hivatkozva ez az optimum, a feladatok széles skáláját véve mintául, a k = 16 választásnál valósul meg.

Rátérünk az úgynevezett \underline{automatikus stratégia} ismertetésére. Ebben az esetben k-t automatikusan választjuk meg az algoritmus elején az adott feladatnak megfelelően. Ezután ezzel a k-val úgy folytatjuk az algoritmust, mintha a fix stratégiát követnénk. Először a kiindulási csúcsban vágásokat generálunk. Ezután kiszámoljuk az átlagos távolságot a levágott aktuális optimumok és a vágó hipersíkok között. Jelöljük a kapott számot d-vel. Ez a paraméter fontos szerepet fog játszani a k faktor automatikus meghatározásában. A számítási tapasztalatok azt mutatják ugyanis, hogy d nagyjából egyenlő az egész leszámlálási fán generált vágások és a levágott aktuális optimális megoldások távolságainak átlagával. Megjegyezzük azt is, hogy még a probléma mérete is befolyásolhatja az optimális k értékét. Megállapíthato ugyanis, hogy k-t egyre kisebbre kell választani, ahogy növeljük a 0-1 változók számát. A fentiek alapján az optimális k-ra az alábbi tapasztalati képlet nyerhető:

k = min \{KMAX, ⌈\frac{MAXROUND}{cd log_{10} p} ⌉\} ,

ahol KMAX és c konstansok. A [4]-ben közölt számítási eredményeket KMAX = 32 és c = 5 választással érték el.

Végül megemlítjük az úgynevezett \underline{adaptív stratégiát}. Ekkor k értékét szabadon változtatjuk az algoritmus futása során a generált vágások mélysége szerint. Ha az elért mélység valamilyen értelemben nagy, akkor gyakrabban generálunk vágást, azaz k értékét csökkentjük, ha a mélység kicsi, akkor ritkábban generálunk vágást, azaz k értékét növeljük. Habár az adaptív stratégia tűnik a legkifinomultabb eljárásnak, eddig még nem sikerült egy olyan konkrét megvalósítását adni, amely jobb számítási eredményeket produkált volna minden esetben a fent ismertetett automatikus stratégiánál. Néhány egyszerű javítást azonban végre lehet hajtani az automatikus stratégián. Ha a d paramétert dinamikusan mindig újra számoljuk, akkor k értékét is meghatározhatjuk akár minden vágásgenerálás után.

A kezdeti negatív eredmények ellenére talán a jövőben sikerül egy olyan adaptív stratégiát kidolgozni, amely lényegesen növeli majd az algoritmus hatékonyságát.

5.5 Leszámlálási stratégiák

Az ismertetendő leszámlálási stratégia az úgynevezett “legjobb korlát” szabályon alapszik, ezért először ezzel foglalkozunk. Szervezzük a csúcsokat egy listába úgy, hogy a csúcsokhoz tartozó célfüggvényértékek növekvő sorrendben legyenek. Ezek után a csúcs kiválasztása egyszerű, vegyük ugyanis ki mindig az első csúcsot a listából. Fontos megjegyezni, hogy ezt a sorrendet akkor határozzuk meg, amikor a csúcsot generáljuk, és nem módosítjuk akkor, amikor új vágást generálunk. Ebből következően a fenti sorrend csak közelítőleg adja a legjobb korlát sorrendet általában.

Ha az aktuális csúcs a fenti sorrendben az első helyen áll, akkor ki kell választani azt a változót, amely szerint elágazunk. A [9]-ben közölt módszert fogjuk követni, miszerint ezt a változót a következő egyszerű kriterium alapján választhatjuk ki. Először meghatározzuk az x̄_{j} ≤ 1/2 feltételnek eleget tevő koordináták maximumát, majd az x̄_{j} ≥ 1/2 feltételnek eleget tevő koordináták minimumát. Jelöljük az így kapott értékeket f_{0}-lal illetve f_{1}-el. Az elágazás szempontjából szóba jöhető változók halmazát az

I := \{i ∈ \{1, …, p\} : \frac{f_{0}}{2} ≤ x̄_{i} ≤ \frac{1 + f_{1}}{2} \}

képlettel definiáljuk. Válasszuk ki ebből a halmazból azt az indexet, amelyhez tartozó célfüggvény együttható abszolút értékben a legnagyobb. E szerint a változó szerint elágazva kaphatók a [4]-ben közölt számítási eredmények.

A Branch-and-Cut algoritmus sikeres megvalósításához foglalkoznunk kell azon vágások kezelésével, amelyeket az algoritmus futása során generálunk. Ha minden vágás aktív marad az egész algoritmus során, akkor az LP(C, F_{0}, F_{1}) lineáris programozási feladat mérete akkorára is megnőhet, hogy nem tudjuk megoldani az időkorláton belül. Hogy elkerüljük ezt, szintén a [9]-ben leírt eljárást követjük. Tároljuk a vágásokat két diszjunkt listában. Az egyik lista neve aktív lista, a másiké inktív lista. Az aktív lista tartalmazza azokat a vágásokat, amelyeket felhasználunk az aktuális formulában, míg a többit az inaktív listában tároljuk. A konkrét megvalósítást az alábbiakban ismertetjük. Kezdetben mindkét lista üres. Miután először generáltunk vágásokat, mind hozzáadjuk az aktív listához. Ezután periódikusan töröljük az inaktívvá vált vágásokat az aktív listából és adjuk hozzá őket az inaktív listához. Másrészről, ha egyszer egy csúcsot választunk a csúcsok listájából, akkor az inaktív listából megpróbálunk kikeresni egy olyan vágást, amely levágja az ehhez a csúcshoz tartozó optimális megoldást. Ha találunk ilyeneket, akkor ezeket hozzáadjuk az aktív listához, majd töröljük őket az inaktív listából. Ekkor a kapott LP feladatot megoldjuk, majd folytatjuk az algoritmust. Ha az inaktív listában szereplő egyenlőtlenségek száma meghalad egy előre megadott határt, akkor azokat az egyenlőtlenségeket, melyek inaktívak minden csúcsban töröljük a listából, hogy helyet csináljunk a további vágásoknak. A [4]-ben elért számítási eredményekhez használt algoritmusban ezt a felső határt 500-nak választották.

5.6 Konklúzió

Általánosságban azt mondhatjuk el, hogy az eddig tárgyalt pontosításokkal egy olyan algoritmushoz jutottunk, mely hatékonyabb és általánosabb körülmények között használható az eddig ismert vegyes programozási feladatokra kidolgozott algoritmusoknál.

A korábban ismertetett vágásokat eredményesen építettük be a Branch-and-Bound algoritmusba, kihasználva a vágások “mérésére” vonatkozó korábbi eredményeinket. Felhasználtuk ugyanis, hogy a megfelelő LP feladat megoldása során a legmélyebb vágás állítható elő. A számítási tapasztalatokra hivatkozva megállapítottuk, hogy érdemesebb egyszerre több vágást generálni. Ellentétben a széles körben elterjedt tévhittel, érdemes akár általános vágásokat is beépíteni a Branch-and-Bound algoritmusba, ahol általános vágáson olyan vágást értünk, amelyet nem a megoldandó probléma valamilyen egyedi tulajdonságából generáltunk.

Az egyik legfontosabb döntés, amelyet az algoritmus futása során hoznunk kell, az “Elágazás vagy vágás?” problémából adódik. Fontos megtalálni az egyensúlyt a vágások és az elágazások mennyisége között. Erre a problémára, mint említettük, nem várható teljes, szabatos matematikai válasz. Az általunk közölt viszonylag egyszerűen megvalósítható automatikus stratégia hatásosnak bizonyult a legtöbb esetben.

A fő előnye az általunk bemutatott algoritmusnak talán mégis az, hogy példák széles körében alkalmazható, sőt, néha még az olyan algoritmusoknál is jobb számítási eredményt produkál, amelyek nagyban kihasználják az adott probléma speciális tulajdonságait.

Bibliography

[1] E. Balas, “Disjunctive Programming,” Annals of Discrete Mathematics 5 (1979) 3–51.

[2] E. Balas, “Disjunctive Programming: Properties of the convex hull of feasible points,” MSRR No. 348, Carnegie Mellon University (Pittsburgh, PA, 1974).

[3] E. Balas, S. Ceria, G. Cornuéjols, “A lift-and-project cutting plane algorithm for mixed 0-1 programs,” Mathematical Programming 58 (1993) 295–324.

[4] E. Balas, S. Ceria, G. Cornuéjols, “Mixed 0-1 programming by lift-and-project in a Branch-and-Bound framework,” Management Science 42 (1996) 1229–1246.

[5] E. Balas, J. Tama, J. Tind, “Sequential convexification in reverse convex and disjunctive programming,” Mathematical Programming 44 (1989) 337–350.

[6] R. Gomory, “An algorithm for the mixed integer problem,” RM-2597, The Rand Corporation (Santa Monica, CA, 1960).

[7] R. Jeroslow, “A cutting plane game for facial disjunctive programs,” SIAM Journal on Control and Optimization 18(3) (1980) 264–280.

[8] L. Lovász, A. Schrijver, “Cones of matrices and set-functions and 0-1 optimization,” SIAM Journal on Optimization 1(2) (1991) 166–190.

[9] M. Padberg, G. Rinaldi, “A Branch-and-Cut algorithm for the resolution of large-scale symmetric traveling salesman problems,” SIAM Review, 33 (1991), 60–100.

[10] A. Schrijver, Theory of Linear and Integer Programming, (John Wiley & Sons, Chichester, New York, Brisbane, Toronto, Singapore, 1986).

[11] H. Sherali, W. Adams, “A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems,” SIAM Journal on Discrete Mathematics 3(3) (1990) 411–430.

[12] Vizvári Béla, Egészértékű programozás, ELTE jegyzet (Tankönyvkiadó, Budapest, 1989).

[13] W. White, “On Gomory’s mixed integer algorithm,” Senior Thesis, Department of Mathematics, Princeton University (Princeton, NJ, 1961).