Inverz problémák a kombinatorikus optimalizálásban

Szakdolgozat

Írta: Jávor Bálint
Témavezető: Frank András

egyetemi tanár

Eötvös Loránd Tudományegyetem Természettudományi Kar

Tartalomjegyzék

Bevezetés 3

1. Inverz lineáris programozás 5 1.1. Az inverz probléma felírása . . . . . . . . . . . . . . . . . . . . 5 1.2. Inverz LP probléma L_{1} normában . . . . . . . . . . . . . . . . 6 1.3. Inverz LP probléma L_{∞} normában . . . . . . . . . . . . . . . 10

2. Hálózati inverz problémák 13 2.1. Minimális költségű út . . . . . . . . . . . . . . . . . . . . . . . 13 2.2. Minimális költségű teljes párosítás . . . . . . . . . . . . . . . . 14 2.3. Minimális költségű folyam . . . . . . . . . . . . . . . . . . . . 16

3. Inverz problémák matroidokon 18 3.1. Minimális súlyú bázis . . . . . . . . . . . . . . . . . . . . . . . 18 3.2. Súlyozott matroid metszet . . . . . . . . . . . . . . . . . . . . 19

4. Inverz szubmoduláris áram 22

5. Többoptimumos inverz problémák 28

5.1. Minimális abszolút összeg problémák . . . . . . . . . . . . . . 28 5.1.1. Minimális abszolút összegű potenciál . . . . . . . . . . 28 5.1.2. Minimális abszolút összegű áram . . . . . . . . . . . . 30

5.2. Minimális bázisok matroidban . . . . . . . . . . . . . . . . . . 31 5.3. Többoptimumos matroid metszet . . . . . . . . . . . . . . . . 31 5.4. Minimális költségű utak . . . . . . . . . . . . . . . . . . . . . 32

5.4.1. s—t utak . . . . . . . . . . . . . . . . . . . . . . . . . 32 5.4.2. Tetszőleges útrendszer . . . . . . . . . . . . . . . . . . 34

5.5. Minimális párosítások . . . . . . . . . . . . . . . . . . . . . . . 37

6. Paraméteres inverz problémák 39

Bevezetés

A címet elolvasva az ember első kérdése: mi az az inverz probléma? Az „inverz” szó jobbára valamiféle „megfordítást” jelent, de hogyan lehet értelmezni egy optimalizálási feladat megfordítását?

Egy optimalizálási feladat általában a következőképpen néz ki: adott egy halmaz (aminek az elemeit szokás megengedett megoldásoknak nevezni), a halmazon pedig valamilyen (sok esetben lineáris) függvény; a cél a halmaz egy olyan elemének megtalálása, amelyhez tartozó függvényérték minimális vagy éppen maximális, egyszóval optimális. Tegyük fel most, hogy adott a megengedett megoldások halmaza, de a célfüggvényt nem ismerjük pontosan, csak becslés áll a rendelkezésünkre (például valamilyen matematikai modell alapján), esetleg a függvényértékek mérések eredményei. Emellett valaki (orákulum, jó tündér stb.) mond nekünk egy vagy több optimális megoldást. Az így adódó inverz optimalizálási feladat az, hogy kitaláljuk a célfüggvény „valódi” értékeit, amik szerint az adott megoldás(ok) tényleg optimális(ak). Természetesnek látszik, hogy eközben törekedjünk arra is, hogy tetszetős becsléseink minél jobbnak bizonyuljanak, vagy hogy a mért és tényleges értékek közötti eltérés elég kicsi legyen ahhoz, hogy a műszerek pontatlanságára hivatkozhassunk.

Példa. Egy úthálózat használóinak utazási költsége függ a forgalomtól: minél többen használnak egyszerre egy útszakaszt, annál magasabbak a költségek (pl. időveszteség, több fogyasztás). Az autósok igyekeznek úgy megválasztani útvonalukat, hogy a lehető legkisebb költséggel érjenek el céljukhoz. Ideális körülmények között az úthálózatban így adódó folyam egy ún. egyensúlyi folyam, ahol egyik autós sem tudja csökkenteni a költségeit útvonalának egyoldalú megváltoztatásával. Ez az egyensúlyi folyam nem feltétlenül azonos az optimális folyammal, ami az egész hálózatra nézve minimalizálja az utazási költségeket. Ez esetben a feladat egyes útszakaszok költségeinek módosítása (útszélesítés, útdíjak bevezetése) úgy, hogy az egyensúlyi folyam egyúttal optimális is legyen, vagyis hogy az úthálózat a lehető legjobban legyen kihasználva.

Ez az inverz probléma fogalom alig több mint tíz éve létezik. Elsőként a geofizikai kutatásokkal kapcsolatban merült fel a kérdés, hogy hogyan lehetne korrigálni a mérések pontatlanságából adódó anomáliákat. Burton és Toint 1992-ben és 1994-ben megjelent cikkei [5, 6] már a matematikus körök érdeklődését is felkeltették: ők a földrengések okozta lökéshullámok mozgásával kapcsolatban felmerülő inverz legrövidebb út problémákkal foglalkoztak, kvadratikus programozási eszközökkel. 1995-től kezdve aztán egyre többen kezdtek el foglalkozni a témával, és azóta folyamatosan születtek a megoldások a különféle inverz matroid- és hálózati folyam problémákra.

Az első fejezetben a lineáris programozás alapvető technikáira támaszkodva vizsgáljuk az inverz LP problémákat. A kapott eredmények jól használhatók a hálózati inverz problémák megoldásainál; ilyen feladatokkal foglalkozunk a második fejezetben.

Az inverz probléma megoldásának egy másik lehetséges megközelítését ismerjük meg a harmadik fejezetben, ahol a matroidokon értelmezett optimalizálási problémák két legfontosabb képviselőjéről esik szó.

A negyedik fejezetben az egyik legáltalánosabb kombinatorikus probléma, a szubmoduláris áram inverzéről mutatjuk meg, hogy visszavezethető egy minimális költségű áram feladatra, és ezáltal erősen polinomiális időben megoldható.

Az ötödik fejezet az inverz problémák azon típusával foglalkozik, amikor több megoldást kell egyszerre optimálissá tenni a célfüggvény módosításával. A fejezet elején szerepel két önmagában is érdekes minimális abszolút összeg feladat megoldása is.

Az inverz probléma egy, az eddigiektől eltérő megközelítését, a paraméteres inverz problémát mutatjuk be röviden az utolsó fejezetben. Ebben az esetben az inverz feladat nem annyira optimalizálási problémaként jelentkezik, sokkal inkább a megoldás létezése az alapkérdés.

Ezúton is szeretnék köszönetet mondani témavezetőmnek, Frank Andrásnak, aki megismertetett a témakörrel, és iránymutatásával, ötleteivel segített e szakdolgozat megírásában.

1. fejezet

Inverz lineáris programozás

Nagyon sok optimalizálási probléma írható fel lineáris program alakban, ezért célszerűnek látszik, hogy áttekintsük: mit tudunk mondani egy (kellően általános) lineáris programozási feladat inverzéről. E fejezetben Ahuja és Orlin [2] nyomdokain járva a standard linearizálási és primál-duál technikák alkalmazásával vizsgáljuk néhány alapvető LP-típus inverzeit.

1.1. Az inverz probléma felírása

Tekintsük a következő lineáris programot:

\begin{matrix}min ∑_{j∈J} c_{j}x_{j} \\ ∑_{j∈J} a_{ij}x_{j} & ≥ b_{i} i ∈ I \end{matrix}  (LP)

Egyelőre megelégszünk a fenti alakú lineáris program vizsgálatával, ami nem jelent nagy megszorítást, hiszen az esetleg előforduló nemnegativitási kritériumok, korlátok, egyenlőségi feltételek mind beépíthetők a feltételi mátrixba.

Az (LP)-hez tartozó duális lineáris program:

\begin{matrix}max ∑_{i∈I} b_{i}π_{i} \\ ∑_{i∈I} a_{ij}π_{i} & = c_{j}  j ∈ J \\ π ≥ 0 \end{matrix}  (D)

A kiegészítő eltérések tétele alapján egy (x, π) megengedett megoldáspár pontosan akkor optimális, ha

∑_{j∈J} a_{ij}x_{j} > b_{i} ⇒ π_{i} = 0  (1.1)

fennáll.

Jelölje LP(d) illetve D(d) azokat a lineáris programokat, amiket LP-ből ill. D-ből kapunk úgy, hogy c helyére d-t írunk. Legyen ezek után x^{0} (LP) egy megengedett megoldása. (1.1) szerint x^{0} pontosan akkor lesz optimális megoldása LP(d)-nek, ha létezik D(d)-nek olyan megengedett π megoldása, hogy

∑_{j∈J} a_{ij}x_{j}^{0} > b_{i} ⇒ π_{i} = 0  (1.2)

Bevezetve a B = {i ∈ I : ∑_{j∈J} a_{ij}x_{j}^{0} = b_{i}} jelölést, felírhatjuk az inverz feladatot:

\begin{matrix}min ∑_{j∈J} ||d_{j} − c_{j}|| \\ ∑_{i∈B} a_{ij}π_{i} & = d_{j}  j ∈ J \\ π ≥ 0 \end{matrix}  (1.3)

Itt || · || valamilyen alkalmasan választott távolság (norma). Általános esetben (1.3) egy nemlineáris programozási feladat konvex célfüggvénnyel és lineáris feltételekkel. A továbbiakban c és d eltérését L_{1} illetve L_{∞} normában (valamint ezek súlyozott változatában) fogjuk tekinteni, amikoris az inverz feladat lineáris programmá alakítható.

1.2. Inverz LP probléma L_{1} normában

L_{1} norma esetén (1.3) célfüggvénye

min ∑_{j∈J} |d_{j} − c_{j}|

alakú. Ez nem lineáris, de könnyen azzá tehető. |d_{j} − c_{j}| minimalizálása ugyanis ekvivalens α_{j} + β_{j} minimalizálásával, ahol d_{j} − c_{j} = α_{j} − β_{j} és α_{j}, β_{j} ≥ 0. Ezt felhasználva az inverz lineáris programozási feladat a következő:

\begin{matrix}min ∑_{j∈J} α_{j} + ∑_{j∈J} β_{j} \\ ∑_{i∈I} a_{ij}π_{i} − α_{j} + β_{j} & = c_{j}  j ∈ J \\ π, α, β ≥ 0 \end{matrix}  (1.4)

Észrevétel. Ha α és β része (1.4) egy optimális megoldásának, akkor minden j ∈ J-re α_{j} és β_{j} közül legfeljebb az egyik lehet pozitív; ellenkező esetben ugyanis mindkét számból a kisebbiket levonva olyan megengedett megoldást kapnánk, amelyre a célfüggvény értéke szigorúan kisebb lenne az optimálisnál.

Egy tetszőleges π megengedett vektorhoz felírhatjuk a hozzá tartozó módosított költségfüggvényt:

c_{j}^{π} := c_{j} − ∑_{i∈B} a_{ij}π_{i}

Ezzel a jelöléssel (1.4) egyenlőségi feltétele

−α_{j} + β_{j} = c_{j}^{π}  (1.5)

alakban írható fel. Így ha π az (1.4) optimális megoldása, akkor az optimális d vektor előállítása:

d_{j} = c_{j} − c_{j}^{π}

Tekintsük ezek után (1.4) duálját:

\begin{matrix}min ∑_{j∈J} c_{j}y_{j} \\ ∑_{j∈J} a_{ij}y_{j} & ≥ 0 i ∈ B \\ −1 ≤ y_{j} ≤ 1 \end{matrix}  (1.6)

Ezt az alakot az (LP) 0-közepű duális inverz problémájának nevezzük. Az y vektor helyére x_{j} − x_{j}^{0}-t írva kapjuk:

min ∑_{j∈J} c_{j}x_{j} − ∑_{j∈J} c_{j}x_{j}^{0}

∑_{j∈J} a_{ij}x_{j} − ∑_{j∈J} a_{ij}x_{j}^{0} ≥ 0 i ∈ B
−1 ≤ x − x^{0} ≤ 1

Mivel ∑_{j∈J} c_{j}x_{j}^{0} konstans, továbbá minden i ∈ B esetén ∑_{j∈J} a_{ij}x_{j}^{0} = b_{i}, a fenti lineáris program egyenértékű az alábbi, úgynevezett x^{0}-közepű duális inverz problémával:

\begin{matrix}min ∑_{j∈J} c_{j}x_{j} \\ ∑_{j∈J} a_{ij}x_{j} & ≥ b_{i} i ∈ B \\ x^{0} − 1 ≤ x ≤ x^{0} + 1 \end{matrix}  (1.7)

Explicit korlátok

Eddig feltettük, hogy a változókra vonatkozó esetleges korlátok implicit voltak adva a feltételi mátrixban. Most ettől eltekintünk és az alábbi lineáris programot tekintjük:

\begin{aligned}min ∑_{j∈J} c_{j}x_{j} \\ ∑_{j∈J} a_{ij}x_{j} & ≥ b_{i} i ∈ I \\ l ≤ x & ≤ u \end{aligned}  (1.8)

Legyen ismét x^{0} az (1.8) egy adott megoldása, és vezessük be a következő jelöléseket:

B := {i ∈ I : ∑_{j∈J} a_{ij}x_{j}^{0} = b_{i}}
L := {j ∈ J : x_{j}^{0} = l_{j}}
U := {j ∈ J : x_{j}^{0} = u_{j}}
F := {j ∈ J : l_{j} < x_{j}^{0} < u_{j}}

A korábban látottak alapján az L_{1} norma szerinti inverz lineáris program:

\begin{aligned}max − ∑_{j∈J} α_{j} − ∑_{j∈J} β_{j} \\ ∑_{i∈I} a_{ij}π_{i} − α_{j} + β_{j} + λ_{j} & = c_{j}  j ∈ L \\ ∑_{i∈I} a_{ij}π_{i} − α_{j} + β_{j} − ϕ_{j} & = c_{j}  j ∈ U \\ ∑_{i∈I} a_{ij}π_{i} − α_{j} + β_{j} & = c_{j}  j ∈ F \\ π, α, β, λ, ϕ ≥ 0 \end{aligned}  (1.9)

Legyen (π, α, β, λ, ϕ) (1.9) optimális megoldása. A módosított költség, c_{j}^{π} = c_{j} − ∑_{i∈B} a_{ij}π_{i} előjele szerint három esetet vizsgálhatunk meg:

1. c_{j}^{π} > 0. Ha j ∈ L, akkor az optimalitás miatt λ_{j} = c_{j}^{π} és α_{j} = β_{j} = 0,
így d_{j} = c_{j}. j ∈ U ∪ F esetén α_{j} = ϕ_{j} = 0, β_{j} = c_{j}^{π},
tehát d_{j} = c_{j} − c_{j}^{π}.
2. c_{j}^{π} < 0. Ha j ∈ U, akkor ϕ_{j} = −c_{j}^{π} és α_{j} = β_{j} = 0, azaz d_{j} = c_{j}.
j ∈ L ∪ F esetén pedig β_{j} = λ_{j} = 0, α_{j} = −c_{j}^{π},
így d_{j} = c_{j} − c_{j}^{π}.
3. c_{j}^{π} = 0. Ekkor α_{j} = β_{j} = λ_{j} = ϕ_{j} = 0, amiből d_{j} = c_{j}.

A fentieket összefoglalva az optimális d vektor előállítása:

d_{j} = \{ \begin{matrix}c_{j} − |c_{j}^{π}| & , ha c_{j}^{π} > 0 és x_{j}^{0} > l_{j} \\ c_{j} + |c_{j}^{π}| & , ha c_{j}^{π} < 0 és x_{j}^{0} < u_{j} \\ c_{j} & , egyébként \end{matrix}  (1.10)

Ebben az esetben az x^{0}-közepű duális inverz probléma a

\begin{aligned}min ∑_{j∈J} c_{j}x_{j} \\ ∑_{j∈J} a_{ij}x_{j} & ≥ b_{i}  i ∈ B \\ l_{j} ≤ x_{j} & ≤ l_{j} + 1 j ∈ L \\ u_{j} − 1 ≤ x_{j} & ≤ u_{j}  j ∈ U \\ x_{j}^{0} − 1 ≤ x_{j} & ≤ x_{j}^{0} + 1 j ∈ F \end{aligned}  (1.11)

alakot ölti. Vegyük észre, hogy abban a fontos speciális esetben, amikor (1.8)- ban csupa egyenlőség áll, l azonosan 0, u azonosan 1 és a poliéder egész (ún. 0 − 1 LP), az x^{0}-közepű duális inverz probléma megegyezik az eredeti feladattal. Ez esetben ugyanis B = I, F = ∅, l_{j} = u_{j} −1 = 0 és l_{j} +1 = u_{j} = 1 minden j ∈ J-re.

Súlyozott változat

Az előbbinél némileg általánosabb feladathoz jutunk, ha feltesszük, hogy a c célfüggvény minden c_{j} koordinátájához tartozik egy w_{j} súly, mely azt fejezi ki, hogy a j-edik koordináta egy egységgel történő megváltoztatása mekkora költséggel jár. Ekkor persze a célunk a módosítások összköltségének minimalizálása (úgy hogy az előre megadott x^{0} megoldás optimális legyen). Formálisan ez esetben (1.3) célfüggvénye

∑_{j∈J} w_{j}|d_{j} − c_{j}|

alakú. Könnyen látható, hogy a súlyozatlan eset gondolatmenete egy az egyben alkalmazható itt is, a különbség csupán annyi, hogy (1.6)-ban −w ≤ y ≤ w, (1.7)-ben x^{0} − w ≤ x ≤ x^{0} + w írandó az utolsó sorba, (1.11) korlátai pedig

l_{j} ≤ x_{j} ≤ l_{j} + w_{j} j ∈ L
u_{j} − w_{j} ≤ x_{j} ≤ u_{j} j ∈ U
x_{j}^{0} − w_{j} ≤ x_{j} ≤ x_{j}^{0} + w_{j} j ∈ F

alakúak lesznek.

1.3. Inverz LP probléma L_{∞} normában

L_{∞} norma esetén (1.3) feladata max{|d_{j} − c_{j}|} minimalizálása. Szerencsére ez az alak is egyszerűen lineárissá alakítható. Az abszolútérték kiküszöbölése végett először is vezessük be az α és β nemnegatív változókat úgy, hogy d_{j} −c_{j} = α_{j} −β_{j} fennálljon. Legyen ezután θ olyan változó, amire α_{j} +β_{j} ≤ θ, minden j ∈ J index mellett. Ily módon az alábbi lineáris programhoz jutunk:

\begin{matrix}min θ \\ ∑_{i∈B} a_{ij}π_{i} − α_{j} + β_{j} & = c_{j}  j ∈ J \\ α_{j} + β_{j} − θ & ≤ 0 j ∈ J \\ α, β, π ≥ 0 \end{matrix}  (1.12)

Észrevétel. Optimális megoldásban minden j ∈ J-re α_{j} = 0 vagy β_{j} = 0.

Legyen (α, β, π) optimális megoldása (1.12)-nek, és jelölje ismét c_{j}^{π} := c_{j} − ∑ a_{ij}π_{i}. Ekkor az optimális d vektorra d = c − c^{π}. Az is látható, hogy ha valamely j-re c_{j}^{π} > 0, akkor α_{j} = 0 és így θ ≥ β_{j} = c_{j}^{π}. Hasonlóan c_{j}^{π} < 0 esetén −θ ≤ −α_{j} = c_{j}^{π}, míg c_{j}^{π} = 0 mellett α_{j} = β_{j} = 0 és a θ ≥ 0 feltétel automatikusan teljesül. Ennek alapján (1.12) a következő egyszerű alakba írható át:

\begin{matrix}min θ \\ −θ ≤ c_{j}^{π} & ≤ θ j ∈ J \end{matrix}  (1.13)

Duálja:

\begin{aligned}min ∑_{j∈J} c_{j}(y_{j}^{1} − y_{j}^{2}) \\ ∑_{j∈J} a_{ij}(y_{j}^{1} − y_{j}^{2}) & ≥ 0 i ∈ B \\ ∑_{j∈J}(y_{j}^{1} + y_{j}^{2}) & ≤ 1 \end{aligned}  (1.14)

y^{1} − y^{2} helyett y-t írva megkapjuk az ún. 0-közepű minimax duális inverz problémát:

\begin{aligned}min ∑_{j∈J} c_{j}y_{j} \\ ∑_{j∈J} a_{ij}y_{j} & ≥ 0 i ∈ B \\ ∑_{j∈J} |y_{j}| & ≤ 1 \end{aligned}  (1.15)

Az y = x − x^{0} helyettesítéssel pedig az x^{0}-közepű minimax duális inverz problémához jutunk:

\begin{aligned}min ∑_{j∈J} c_{j}x_{j} \\ ∑_{j∈J} a_{ij}x_{j} & ≥ b_{j}  i ∈ B \\ ∑_{j∈J} |x_{j} − x_{j}^{0}| & ≤ 1 \end{aligned}  (1.16)

Explicit korlátok

Ha a kezdeti lineáris program (1.8) alakú, az L_{1}-normánál látott gondolatmenetet alkalmazva kapjuk, hogy a minimax inverz probléma

\begin{aligned}min θ \\ c_{j}^{π} & ≤ θ j ∈ J \ L \\ −θ & ≤ c_{j}^{π}  j ∈ J \ U \end{aligned}  (1.17)

alakban áll elő, az optimális d vektort pedig (1.10) adja.

Súlyozott változat

A súlyozott minimax inverz feladatban max{w_{j}|d_{j} − c_{j}|}-t kell minimalizálni (w ≥ 0). Ez ugyanúgy linearizálható, mint a súlyozatlan eset célfüggvénye, és néhány értelemszerű eltéréstől eltekintve ugyanazokat a formulákat kapjuk, mint az előbb; például (1.13) feltételei −θ ≤ w_{j}c_{j}^{π} ≤ θ alakúak lesznek, (1.16) utolsó feltétele helyett pedig annak kell teljesülnie, hogy

∑_{j∈J:w_{j}≠0} \frac{|y_{j}|}{w_{j}} ≤ 1 és w_{j} = 0 ⇒ y_{j} = 0

Ebben a fejezetben tehát megmutattuk, hogy egy lineáris programozási feladat (súlyozott) L_{1} ill. L_{∞} norma szerinti inverze is LP-probléma. Az inverz lineáris program előáll az eredeti lineáris programból néhány feltétel elhagyásával és/vagy változókra vonatkozó korlátok hozzáadásával. Fontos speciális esetként pedig láttuk, hogy egy csak egyenlőségi feltételeket tartalmazó 0 − 1 egészértékű lineáris program inverze megegyezik az eredeti feladattal.

Hálózati inverz problémák

Az 1. fejezet alapján mondhatjuk, hogy egy lineáris programként felírható probléma inverze mindig megoldható, például ellipszoid módszerrel. Ha azonban az eredeti feladatra (akár több) hatékony kombinatorikus algoritmus is ismert, felmerül a kérdés: vajon az inverz probléma megoldható-e kombinatorikus eszközökkel, és ha igen, hogyan? A továbbiakban a leggyakrabban előforduló kombinatorikus problémák esetén keressük erre a választ.

2.1. Minimális költségű út

Legyen a G = (V, E) irányított gráf élein adva egy c : E → R konzervatív költségfüggvény (vagyis D-ben nincs negatív összsúlyú irányított kör). Jól ismert, hogy ekkor tetszőleges s, t ∈ V pontok esetén hatékonyan tudunk találni egy minimimális költségű s—t utat (ha egyáltalán van ilyen): c ≥ 0 esetén Dijkstra módszerével, egyébként például a FIFO távolságcímkéző algoritmussal [1]. Tekintsük most a következő inverz problémát: adott a P^{0} s-ből t-be vezető irányított út; módosítsuk az élek költségeit úgy, hogy a módosított kötségfüggvényre nézve P^{0} minimális költségű s—t út legyen, és emellett az egyes éleken történt változtatások abszolút értékben vett összege minimális legyen. Nézzük meg, hogyan írható fel ez formálisan, és hogyan oldható meg.

A minimális költségű út problémát felírhatjuk lineáris programként:

\begin{aligned}min ∑_{uv∈E} c(uv)x(uv) \\ ∑_{v:uv∈E} x(uv) − ∑_{v:vu∈E} x(vu) & = 0 u ∈ V \ \{s, t\} \\ ∑_{v:sv∈E} x(sv) − ∑_{v:vs∈E} x(vs) & = 1 \\ ∑_{v:tv∈E} x(tv) − ∑_{v:vt∈E} x(vt) & = −1 \\ 0 ≤ x ≤ 1 \end{aligned}  (2.1)

Ez egy 0−1 egészértékű lineáris program, melyben az összes feltétel egyenlőség. Az 1. fejezetben látottak szerint így az x^{0}-közepű duál inverz probléma megegyezik a direkt feladattal (x^{0} a P^{0} út karakterisztikus vektora). Az inverz feladat megoldása ezek után nagyon egyszerű: keressünk G-ben egy minimális c-költségű utat, legyen ez mondjuk P^{∗}. Tekintsük az ehhez tartozó π duál megoldást (potenciált). A c^{π} redukált költségről tudjuk, hogy nemnegatív, emellett minden P^{∗}-beli élen 0, így (1.10)-ből adódik, hogy az optimális költségfüggvény eléréséhez a P^{0} \ P^{∗}-beli éleken kell csökkentenünk c(e)-t, méghozzá éppen c^{π}(e)-vel.

Súlyozott változat

Ha az éleken adott még egy w ≥ 0 súlyfüggvény is, ami az egyes éleken a költségfüggvény értékének egy egységgel való módosításának az árát jelenti, az inverz feladat úgy fogalmazható, hogy a lehető legolcsóbban érjük el P^{0} optimalitását. Ezen súlyozott változat x^{0}-közepű duál inverz problémája lényegében (2.1), csupán a 0 ≤ x ≤ 1 feltétel helyett x^{0} − w ≤ x ≤ x^{0} + w lesz érvényben, ezáltal egy minimális költségű folyam problémához jutunk. Ebben negatív alsó kapacitások is szerepelhetnek, azonban standard átalakításokkal elérhető, hogy minden alsó korlát 0 legyen. (A kérdéses élek fordítottjainak kapacitását kell értelemszerűen megnövelni.)

2.2. Minimális költségű teljes párosítás

Legyen G = (A, B; E) adott páros gráf, |A| = |B|, c tetszőleges költség az éleken. Adott M_{0} teljes párosításhoz keresendő olyan c′ költség, amire nézve M_{0} minimális költségű teljes párosítás, és emellett ||c′ − c||_{L_{1}} is minimális.

Formálisan felírva a minimális költségű teljes párosítás problémát G-ben:

\begin{aligned}min ∑_{uv∈E} & c(uv)x(uv) \\ − ∑_{v:uv∈E} x(uv) & = −1 u ∈ A \\ ∑_{u:uv∈E} x(uv) & = 1 v ∈ B \\ 0 ≤ x & ≤ 1 \end{aligned}  (2.2)

Az 1. fejezetben látottak szerint ez esetben az M_{0}-közepű duális inverz feladat ugyanilyen alakú. Legyen tehát M^{∗} G-ben a c költség szerint minimális teljes párosítás, és jelölje c^{π} a hozzá tartozó módosított költséget (c^{π}(uv) = c(uv) − π(v) + π(u)). Ekkor az optimalitás miatt fennáll:

\begin{aligned}c^{π}(uv) & = 0 uv ∈ M^{∗} \\ c^{π}(uv) & ≥ 0 uv ∉ M^{∗} \end{aligned}  (2.3)

A keresett c′ költség pedig előáll:

c′(uv) = \{ \begin{matrix}c(uv) − c^{π}(uv) & , ha uv ∈ M_{0} \ M^{∗} \\ c(uv) & egyébként \end{matrix}

A fentiek alapján az inverz minimális költségű teljes párosítás problémára egyszerű algoritmust kaptunk: először keresünk egy, az eredeti c költségre minimális teljes párosítást, majd M_{0} élein csökkentjük c-t az eltolt költséggel. (Vegyük észre, hogy ilyenkor c ténylegesen csak M_{0} \ M^{∗}-beli éleken változhat.)

Súlyozott változat

Ha a G gráf élein adott még egy w súlyozás is, és c′ keresésekor a c-től való eltérést súlyozott L_{1}-normában tekintjük (vagyis a célunk ∑ w(uv)|c′(uv) − c(uv)| minimalizálása), az inverz probléma

\begin{aligned}min ∑_{uv∈E} & c(uv)x(uv) \\ − ∑_{v:uv∈E} x(uv) & = −1 u ∈ A \\ ∑_{u:uv∈E} x(uv) & = 1 v ∈ B \\ x^{0} − w ≤ x & ≤ x^{0} + w \end{aligned}  (2.4)

alakú lesz, ahol x^{0} az M_{0} karakterisztikus vektora. Vagyis egy minimális költségű folyam problémához jutunk, amely könnyen megoldható valamelyik jól ismert algoritmussal.

2.3. Minimális költségű folyam

Adott a G = (V, E) irányított gráf, élein egy c költség- és egy g ≥ 0 kapacitásfüggvénnyel. Tekintsük G-n a minimális költségű folyam probléma egy általánosított változatát, amikoris minden v ∈ V pontra adott egy b(v) szám, amit a pont igényének hívunk, és ami azt fejezi ki, hogy a kérdéses pont milyen mértékben funkcionál forrásként ill. nyelőként. Formálisan:

\begin{matrix}min ∑_{uv∈E} c(uv)x(uv) \\ ∑_{v:vu∈E} x(vu) − ∑_{v:uv∈E} x(uv) & = b(uv) u ∈ V \\ 0 ≤ x ≤ g \end{matrix}  (2.5)

Az inverz minimális költségű folyam feladatban adott egy x^{0} megengedett megoldásunk, amit optimálissá szeretnénk tenni a c költségfüggvény (kismértékű) megváltoztatásával. Először is bontsuk fel az E élhalmazt az L, U, F halmazok diszjunkt uniójára a következőképpen:

\begin{aligned}L & := \{uv ∈ E : x^{0}(uv) = 0\}, U := \{uv ∈ E : x^{0}(uv) = g(uv)\} \\ F & := E \ (L ∪ U) \end{aligned}

Az 1. fejezetben látottak alapján (2.5) 0-közepű duális inverzét így írhatjuk fel:

\begin{aligned}min ∑_{uv∈E} c(uv)y(uv) \\ ∑_{v:vu∈E} y(vu) − ∑_{v:uv∈E} y(uv) & = 0 u ∈ V \\ 0 ≤ y(uv) & ≤ 1 uv ∈ L \\ −1 ≤ y(uv) & ≤ 0 uv ∈ U \\ −1 ≤ y(uv) & ≤ 1 uv ∈ F \end{aligned}  (2.6)

Ez pedig nem más, mint egy minimális költségű áram feladat G-n, ami ráadásul nagyon egyszerűen átalakítható úgy, hogy minden alsó kapacitás 0, és minden felső kapacitás 1 legyen. Az ilyen speciális minimális költségű áram feladat pedig O(m(m + n log n)) időben megoldható (lásd pl. [1]).

Súlyozott változat

Az inverz minimális költségű folyam probléma súlyozott változatára alkalmazva a fent leírtakat, ugyancsak (2.6)-t kapjuk azzal a különbséggel, hogy az y-ra vonatkozó korlátok

\begin{aligned}0 ≤ y(uv) & ≤ w(uv) uv ∈ L \\ −w(uv) ≤ y(uv) & ≤ 0 uv ∈ U \\ −w(uv) ≤ y(uv) & ≤ w(uv) uv ∈ F \end{aligned}

alakúak lesznek. Ez megint csak egy minimális költségű áram feladat, de általában nem hozható olyan speciális alakúra, mint előbb, és így a megoldására is csak általánosabb algoritmusok vethetők be, de ezek között is vannak erősen polinomiálisak (pl. a minimális átlagú körök mentén javító O(n^{2}m^{3} log n)-es algoritmus).

Inverz problémák matroidokon

3.1. Minimális súlyú bázis

Legyen M egy matroid az S véges alaphalmazon, w tetszőleges súlyozás a pontokon. Adott B ⊆ S bázis esetén keresendő olyan w′ : S → R súlyozás, amire nézve B minimális súlyú bázis, emellett ∑ |w′(s) − w(s)| minimális. Általánosabb esetben feltesszük, hogy S-en adott még egy c nemnegatív költségfüggvény is, és ennek segítségével w′ és w eltérését ∑ c(s)|w′(s)−w(s)|-nek definiáljuk.

3.1.1. Lemma. w a B bázis elemein csak csökkenhet, S \ B elemein pedig csak nőhet.

Bizonyítás. Legyen w′ az inverz feladat optimális megoldása, és tegyük fel, hogy valamely s ∈ B-re w′(s) > w(s). Legyen w′′ az a súlyozás, amire w′′(z) = w′(z), ha z ≠ s, és w′′(s) = w(s). B nyilvánvalóan w′′-re nézve is minimális súlyú bázis, ugyanakkor w′′-nek w-től való (súlyozott) eltérése c(s)(w′(s) − w(s))-sel kisebb, mint w′ és w eltérése (ne feledjük, hogy c ≥ 0). z ∉ B és w′(z) < w(z) esetén hasonlóan ellentmondáshoz jutunk. □

A lemma szerint a keresett w′-höz létezik egy nemnegatív x vektor, amire

\begin{aligned}w′(s) & = w(s) − x(s) s ∈ B \\ w′(z) & = w(z) + x(z) z ∉ B \end{aligned}

Erre az x vektorra tehát |w′(s) − w(s)| = x(s), (s ∈ S).

A B bázis pontosan akkor minimális súlyú bázis w′-re nézve, ha tetszőleges z ∉ B elem B-re vonatkozó alapkörének minden s ∈ C(B, z) elemére w′(s) ≤ w′(z). Ennek alapján felírhatjuk az inverz minimális bázis probléma lineáris programját:

\begin{matrix}min ∑_{s∈S} c(s)x(s) \\ w(s) − x(s) & ≤ w(z) + x(z) z ∉ B, s ∈ C(B, z) \\ x ≥ 0 \end{matrix}  (3.1)

Jelölje P az előforduló (s, z) párok halmazát. Ezzel a jelöléssel (3.1) duálja:

\begin{matrix}min ∑_{(s,z)∈P}(w(z) − w(s))y(s, z) \\ ∑_{z:(s,z)∈P} y(s, z) & ≤ c(s) s ∈ B \\ ∑_{s:(s,z)∈P} y(s, z) & ≤ c(z) z ∉ B \\ y ≥ 0 \end{matrix}  (3.2)

Definiáljuk a G = (V, E) irányított gráfot a következőképpen: V := S ∪ {u, v}, E := P ∪{(u, s) : s ∈ B}∪{(z, v) : z ∉ B}. A P -beli (s, z) élek költsége legyen w(z) − w(s), a többi él költsége 0. Az (u, s) ill. (z, v) típusú élek felső kapacitása legyen c(s) ill. c(z), a P -beli éleké pedig +∞ (vagy ha úgy tetszik max{c(s) : s ∈ S}). Az alsó kapacitás legyen mindenütt 0. Könnyen látható, hogy (3.2) ekvivalens a G-n így definiált minimális költségű áram feladattal, következésképp megoldható erősen polinomiális algoritmussal.

3.2. Súlyozott matroid metszet

Legyenek M_{1} = (S, I_{1}) és M_{2} = (S, I_{2}) adott matroidok, w tetszőleges súlyozás, c pedig nemnegatív költség S-en. A feladat adott F k elemű közös független halmazhoz olyan w′ súlyozás keresése, amelyre F w′-minimális k elemű közös független, emellett ∑ c(s)|w′(s) − w(s)| minimális.

A 3.1.1 lemma értelemszerű módosítással itt is érvényes, vagyis

3.2.1. Lemma. w az F elemein csak csökkenhet, S \ F elemein pedig csak nőhet.

Tehát itt is létezik a keresett w′-höz olyan nemnegatív x vektor, melyre

\begin{aligned}w′(s) & = w(s) − x(s) s ∈ F \\ w′(z) & = w(z) + x(z) z ∉ F \end{aligned}  (3.3)

Ahhoz, hogy az inverz súlyozott matroid metszet problémát felírhassuk lineáris programként, szükségünk van az alábbi két lemmára:

3.2.2. Lemma. Adott M = (S, I) matroidra legyen I^{k} = {X ∈ I : |X| = k}. Az I ∈ I^{k} halmaz akkor és csak akkor w-minimális, ha

\begin{matrix}(1) & x ∉ I, I + x ∉ I, y ∈ C(I, x) ⇒ w(x) ≥ w(y) , és \\ (2) & x ∉ I, I + x ∈ I, y ∈ I ⇒ w(x) ≥ w(y), \end{matrix}

ahol C(I, x) az I + x-ben levő egyértelmű kört jelöli.

Bizonyítás. A lemma a mohó algoritmus érvényességével elvivalens. □

3.2.3. Lemma. I ∈ I_{1}^{k} ∩ I_{2}^{k} w-minimális ⟺ létezik S-nek két olyan w_{1}, w_{2} súlyozása, amelyekre w_{1} + w_{2} = w és I w_{i}-minimális I_{i}^{k}-ban (i = 1, 2).

Bizonyítás. Az állítás valójában Edmonds súlyozott matroid metszet tételének egyik alakja (lásd pl. [8]). □

Vezessük be a következő jelölést:

\begin{matrix}P_{i} := & \{(s, z) : s ∈ F, z ∉ F, s ∈ C_{i}(F, z)\} \\ ∪ \{(s, z) : s ∈ F, z ∉ F, z + B ∈ I_{i}\} (i = 1, 2) \end{matrix}

A két lemma alapján tehát F ∈ I_{1}^{k} ∩ I_{2}^{k} pontosan akkor w′-minimális, ha létezik w_{1}, w_{2}, amelyekre

\begin{aligned}w_{i}(z) − w_{i}(s) & ≥ 0 (s, z) ∈ P_{i}, i = 1, 2 \\ w′ & = w_{1} + w_{2} \end{aligned}  (3.4)

Az inverz súlyozott matroid metszet probléma (3.3) és (3.4) alapján így írható fel:

\begin{aligned}min ∑_{s∈S} c(s)x(s) \\ w_{i}(z) − w_{i}(s) & ≥ 0 (s, z) ∈ P_{i}, i = 1, 2 \\ w_{1}(s) + w_{2}(s) + x(s) & = w(s) s ∈ F \\ w_{1}(z) + w_{2}(z) − x(z) & = w(z) z ∉ F \\ x ≥ 0 \end{aligned}  (3.5)

(3.5) duálja:

\begin{aligned}max ∑_{s∈S} w(s)π(s) \\ − ∑_{z:(s,z)∈P_{i}} y_{i}(s, z) + π(s) & = 0 s ∈ F, i = 1, 2 \\ ∑_{s:(s,z)∈P_{i}} y_{i}(s, z) + π(z) & = 0 z ∉ F, i = 1, 2 \\ y_{1}, y_{2} & ≥ 0 \\ π(s) & ≤ c(s)  s ∈ F \\ π(z) & ≥ −c(z) z ∉ F \end{aligned}  (3.6)

y_{1} és y_{2} nemnegativitásából azonnal adódik, hogy π(s) ≥ 0, ha s ∈ F és π(z) ≤ 0, ha z ∉ F. A π S \ F -beli komponenseit negálva kapjuk (3.6) egy ekvivalens alakját:

\begin{aligned}max ∑_{s∈F} w(s)π(s) & − ∑_{z∉F} w(z)π(z) \\ ∑_{z:(s,z)∈P_{i}} y_{i}(s, z) & = π(s) s ∈ S, i = 1, 2 \\ y_{1}, y_{2} & ≥ 0 \\ 0 ≤ π(s) & ≤ c(s) s ∈ S \end{aligned}  (3.7)

Definiáljuk a G = (V, E) irányított gráfot az alábbi módon:

\begin{matrix}V := & \{s_{1}, s_{2} : s ∈ S\} \\ E := & \{(s_{1}, z_{2}) : (s, z) ∈ P_{1}\} ∪ \{(z_{1}, s_{2}) : (s, z) ∈ P_{2}\} ∪ \{(s_{2}, s_{1}) : s ∈ S\} \end{matrix}

E definíciójában az első halmaz felel meg y_{1}-nek, a második y_{2}-nek, a harmadik pedig π-nek. Az (s_{2}, s_{1}) típusú élek felső kapacitása legyen c(s), a költség pedig legyen −w(s), ha s ∈ F, ill. w(s), ha s ∉ F. A többi él költsége legyen 0, a felső kapacitásuk +∞. Az alsó kapacitást minden élen 0nak definiáljuk. Könnyen látható, hogy a G-ben így adódó minimális költségű áram feladat ekvivalens a (3.7) feladattal.

Inverz szubmoduláris áram

A szubmoduláris áram feladat az egyik legáltalánosabb kombinatorikus probléma, ezért is szentelünk neki külön fejezetet. Az alábbiakban Frank András [9] eredményeire támaszkodva, Yanjun Li [10] gondolatmenetét követve megmutatjuk, hogy az inverz szubmoduláris áram feladat visszavezethető egy minimális költségű áram feladatra, ennélfogva megoldható (erősen polinomiális) kombinatorikus algoritmussal.

Legyen G = (V, E) irányított gráf, élein a c súlyfüggvénnyel és az f alsó és g felső kapacitásokkal (f ≤ g). Legyen továbbá F ⊆ 2^{V} egy keresztező halmazrendszer, b pedig egy F-en értelmezett keresztező szubmoduláris függvény, b(∅) = 0. Tegyük fel, hogy x^{0} megengedett szubmoduláris áram, azaz

\begin{aligned}Ax^{0} & ≤ b \\ f ≤ x^{0} & ≤ g \end{aligned}  (4.1)

ahol A oszlopai az éleknek, sorai F elemeinek felenek meg, mégpedig tetszőleges S ∈ F és e ∈ E esetén

a_{S,e} = \{ \begin{matrix}1 & , ha e belép S-be \\ −1 & , ha e kilép S-ből \\ 0 & , egyébként \end{matrix}

Az inverz maximális szubmoduláris áram probléma a következő: módosítsuk c-t úgy, hogy a kapott c′-re nézve x^{0} maximális szubmoduláris áram legyen, emellett w|c′ − c| minimális legyen (w adott nemnegatív költségfüggvény az éleken).

4.1. Lemma (Lovász, Frank [9]). Jelölje

F′ := \{X ≠ ∅ : X = ∩X_{i}, X_{i} ∈ I, \overline{X_{i}} ∩ \overline{X_{j}} = ∅\} ∪ V

és legyen

b′(X) := min\{∑ b(X_{i}) : X = ∩X_{i}, \overline{X_{i}} ∩ \overline{X_{j}} = ∅\}, b′(V) := 0

(1) Ekkor F′ metsző halmazrendszer és b′ szubmoduláris F′ bármely két metsző elemén.

(2) {x : A′x ≤ b′, f ≤ x ≤ g} = {x : Ax ≤ b, f ≤ x ≤ g}, ahol A′ az A megfelelője F′-re nézve.

A lemma alapján a továbbiakban feltehető, hogy F metsző halmazrendszer és b metsző szubmoduláris függvény F-en.

Az inverz feladat duálja

\begin{matrix}min yb + lf − ug \\ l − u + yA & = c′ \\ l, u, y ≥ 0 \end{matrix}  (4.2)

Vezessük be az

\begin{aligned}E_{1} & = \{e ∈ E : f(e) < x^{0}(e) < g(e)\} \\ E_{2} & = \{e ∈ E : f(e) < x^{0}(e) = g(e)\} \\ E_{1} & = \{e ∈ E : f(e) = x^{0}(e) < g(e)\} \\ E_{4} & = \{e ∈ E : f(e) = g(e)\} \end{aligned}

jelöléseket. A kiegészítő eltérések tétele szerint x^{0} pontosan akkor c′-optimális szubmoduláris áram, ha létezik olyan y ≥ 0 vektor, melyre

\begin{aligned}ya_{e} & = c′(e) e ∈ E_{1} \\ ya_{e} & ≤ c′(e) e ∈ E_{2} \\ ya_{e} & ≥ c′(e) e ∈ E_{3} \\ y_{S} & = 0 a^{S}x^{0} < b(S) \end{aligned}  (4.3)

ahol a_{e} az A mátrix e-hez tartozó oszlopa, a^{S} pedig A S-nek megfelelő sora.

F egy S elemét nevezzük pontosnak, ha a^{S}x^{0} = b(S). Jelölje P (v) a v ∈ V pontot tartalmazó pontos halmazok metszetét (P (v) természetesen függ x^{0}- tól). b szubmodularitását használva könnyen igazolható az alábbi két lemma:

4.2. Lemma ([9]). Metsző pontos halmazok metszete és uniója is pontos.

4.3. Lemma ([9]). (1) P (v) a minimális v-t tartalmazó pontos halmaz. Továbbá P (v) = {u : nincs olyan pontos halmaz, ami tartalmazza v-t de nem tartalmazza u-t}.

(2) Ha pontos halmazok egy családja összefüggő hipergráfot alkot, akkor az uniójuk is pontos.

Egy p ∈ R^{V} vektort potenciálnak hívunk, ha

p(u) ≥ p(v) u ∈ P (v)  (4.4)

Egy p potenciálhoz, mely a p_{0} < p_{1} < ⋯ < p_{k}, (k > 0) értékeket veszi fel, definiáljuk a

V_{j} := {v ∈ V : p(v) ≥ p_{j}} j = 1, …, k

halmazokat. A 4.3 lemma és (4.4) alapján könnyen igazolható:

4.4. Lemma ([9]). Mindegyik V_{j} előáll pontos halmazok diszjunkt uniójaként.

Jelölje K(V_{j}) a {P (v) : v ∈ V_{j}} halmazrendszer mint hipergráf komponenseinek halmazát. S ∈ F esetén legyen

y_{S} := ∑_{j}{p_{j} − p_{j−1} : S ∈ K(V_{j})}  (4.5)

ahol az üres összeget nullának tekintjük. Ekkor nyilvánvaló, hogy y ≥ 0, és ha S ∈ F nem pontos, akkor y_{S} = 0.

4.5. Lemma ([9]). Minden e = uv ∈ E élre p(v) − p(u) = ya_{e}.

Bizonyítás. Jelölje t_{j} (s_{j}) azon K(V_{j})-beli halmazok számát, amelyekbe e belép (amelyekből kilép). Nyilván mindegyik t_{j} és s_{j} 0 vagy 1. Ekkor

ya_{e} = ∑_{S}(y_{S} : e belép S-be) − ∑_{S}(y_{S} : e kilép S-ből) =

= ∑_{S} (∑_{j}(p_{j} − p_{j−1} : S ∈ K(V_{j})) : e belép S-be) −

− ∑_{S} (∑_{j}(p_{j} − p_{j−1} : S ∈ K(V_{j})) : e kilép S-ből) =

= ∑_{j} t_{j}(p_{j} − p_{j−1}) − ∑_{j} s_{j}(p_{j} − p_{j−1}) =
= ∑_{j}(p_{j} − p_{j−1} : e belép V_{j}-be) − ∑_{j}(p_{j} − p_{j−1} : e kilép V_{j}-ből) =

= \{ \begin{matrix}p(v) − p(u) & , ha p(v) > p(u) \\ 0 & , ha p(v) = p(u) \\ −(p(u) − p(v)) & , ha p(v) < p(u) \end{matrix}

Itt kihasználtuk, hogy t_{j} = s_{j}, valahányszor u, v ∈ V_{j} vagy u, v ∉ V_{j}. Továbbá ha p(v) > p(u), akkor a második szumma üres, míg p(u) > p(v) esetén az első szumma üres. □

4.6. Tétel. x^{0} pontosan akkor c′-maximális szubmoduláris áram, ha létezik olyan p potenciál, melyre

\begin{aligned}p(v) − p(u) & = c′(e) e ∈ E_{1} \\ p(v) − p(u) & ≤ c′(e) e ∈ E_{2} \\ p(v) − p(u) & ≥ c′(e) e ∈ E_{3} \\ p(u) & ≥ p(v) u ∈ P (v), v ∈ V \end{aligned}  (4.6)

Bizonyítás. Ha létezik egy ilyen potenciál, akkor a fentiek alapján nyilvánvaló, hogy a (4.5) által definiált y ≥ 0 vektor kielégíti (4.3)-t, vagyis x^{0} c′-maximális.

Megfordítva, ha x^{0} c′-maximális, akkor létezik y ≥ 0, amire teljesülnek (4.3) feltételei. Jelölje

F′ := {S ∈ F : y_{S} > 0}

A kikeresztezési technikával elérhető, hogy F′ lamináris legyen. (Ha S_{1}, S_{2} ∈ F′ metsző halmazok és δ = min{y_{S_{1}}, y_{S_{2}}}, akkor y_{S_{1}}-et és y_{S_{2}}-t δ-val csökkentve, y_{S_{1}∪S_{2}}-t és y_{S_{1}∩S_{2}}-t pedig δ-val növelve az ya_{e} értékek nem vátoznak, tehát az új y ≥ 0 vektor is kielégíti (4.3)-t.) Definiáljuk p-t a következőképpen:

p(v) := ∑_{S∈F′:v∈S} y_{S} (v ∈ V)

Ekkor minden e = uv ∈ E élre

ya_{e} = ∑(y_{S} : e belép S-be) − (y_{S} : e kilép S-ből) =
= ∑(y_{S} : v ∈ S ∈ F′) − ∑(y_{S} : u ∈ S ∈ F′) = p(v) − p(u)

Mivel F′ elemei pontos halmazok, a 4.2 lemma alapján p(u) ≥ p(v) is teljesül minden v ∈ V, u ∈ P (v) esetén, tehát p eleget tesz (4.6) feltételeinek. □

w nemnegativitása miatt (4.6) második és harmadik sorából azonnal következik, hogy

\begin{aligned}c′(e) & ≥ c(e) e ∈ E_{2} \\ c′(e) & ≤ c(e) e ∈ E_{3} \end{aligned}  (4.7)

Az inverz maximális szubmoduláris áram feladat ezek után így fogalmazható meg:

\begin{aligned}max −( ∑_{e∈E_{1}∪E_{2}} w(e)z_{1}(e) & + ∑_{e∈E_{1}∪E_{3}} w(e)z_{2}(e)) \\ p(v) − p(u) − z_{1}(e) + z_{2}(e) & = c(e) e = uv ∈ E_{1} \\ p(v) − p(u) − z_{1}(e) & ≤ c(e) e = uv ∈ E_{2} \\ p(v) − p(u) + z_{2}(e) & ≥ c(e) e = uv ∈ E_{3} \\ p(v) − p(u) & ≤ 0 u ∈ P (v), v ∈ V \\ z_{1}(e) & ≥ 0 e ∈ E_{1} ∪ E_{2} \\ z_{2}(e) & ≥ 0 e ∈ E_{1} ∪ E_{3} \end{aligned}  (4.8)

Megjegyzés. (4.8) feltételeinek száma legfeljebb |V |^{2} + 3|E|, a változók száma pedig legfeljebb |V | + 2|E|. Mivel a feltételi mátrix minden eleme −1, 0 vagy 1, (4.8) egy kombinatorikus lineáris program.

Az alábbiakban megmutatjuk, hogy a probléma visszavezethető egy minimális költségű áram feladatra. Tekintsük (4.8) duálját:

\begin{aligned}min ∑_{e∈E_{1}∪E_{2}} c(e)y(e) − ∑_{e∈E_{3}} c(e)y(e) \\ ∑_{v:vu∈E_{1}∪E_{2}} y(vu) − ∑_{v:uv∈E_{1}∪E_{2}} y(uv) − ∑_{v:vu∈E_{3}} y(vu) + \\ + ∑_{v:uv∈E_{3}} y(uv) + ∑_{v∈P (u)} q(vu) − ∑_{v:u∈P (v)} q(uv) & = 0 u ∈ V \\ −1 ≤ y(e) & ≤ 1 e ∈ E_{1} \\ 0 ≤ y(e) & ≤ 1 e ∈ E_{2} ∪ E_{3} \\ q & ≥ 0 \end{aligned} (4.9)

Definiáljuk a G′ = (V′, E′) gráfot az alábbi módon:

\begin{matrix}V′ := & V \\ E′ := & \{uv : uv ∈ E_{1} ∪ E_{2}\} ∪ \{vu : uv ∈ E_{3}\} ∪ \{uv : u ∈ P (v)\} \end{matrix}

Könnyen látható, hogy (4.9) éppen egy minimális költségű áram feladat G′-n; az inverz szubmoduláris áram probléma tehát valóban megoldható erősen polinomiális algoritmussal.

Többoptimumos inverz problémák

Ebben a fejezetben olyan problémákkal foglalkozunk, melyeknél több megengedett megoldás van adva, és mindegyiket optimálissá szeretnénk tenni a költségfüggvény (lehetőleg nem túl nagy mértékű) megváltoztatásával. Elsőként azonban ismerkedjünk meg egy látszólag nem idevágó problémával, ami túl azon, hogy önmagában érdekes, az inverz minimális bázisok problémájánál is felbukkan.

5.1. Minimális abszolút összeg problémák

5.1.1. Minimális abszolút összegű potenciál

Adott egy G = (V, E) irányított gráf, az élein egy c költségfüggvénnyel. Keressünk olyan π megengedett potenciált, amelyre ∑_{v} |π(v)| minimális!

Hogy az abszolútértéktől megszabaduljunk, vezessük be az x_{1}, x_{2} nemnegatív változókat és helyettesítsük π-t x_{1} − x_{2}-vel. Így ∑ |π(v)| helyett ∑(x_{1} + x_{2})-t kell minimalizálnunk. Lineáris programként felírva tehát:

\begin{aligned}min ∑_{v∈V} x_{1}(v) + ∑_{v∈V} x_{2}(v) \\ x_{1}(v) − x_{1}(u) − x_{2}(v) + x_{2}(u) & ≤ c(uv) uv ∈ E \\ x_{1}, x_{2} & ≥ 0 \end{aligned}  (5.1)

5.1.1. Állítás. Az (5.1) által definiált poliéder egész.

Bizonyítás. (5.1) feltételi mátrixa (A, −A) alakú, ahol A a G gráf incidenciamátrixának transzponáltja (az oszlopok felelnek meg a csúcsoknak, a sorok az éleknek). A-ról tudjuk, hogy teljesen unimoduláris; belátjuk, hogy (A, −A) is az. Tekintsük ugyanis ennek egy négyzetes részmátrixát. Ha ez teljesen Aba vagy −A-ba esik, akkor ezen mátrixok TU-sága miatt kész vagyunk. Ha van olyan i, hogy A és −A i-edik oszlopa is szerepel a részmátrixban, akkor a kérdéses determináns 0. Ha pedig ilyen oszloppár nincs, úgy a −A-ba eső oszlopokat −1-gyel szorozva A-nak egy részmátrixát kapjuk, tehát a determináns így is csak ±1 vagy 0 lehet. □

Tekintsük ezek után (5.1) duálját:

\begin{aligned}min ∑_{uv∈E} c(uv)y(uv) \\ ∑_{v:vu∈E} y(vu) − ∑_{v:uv∈E} y(uv) & ≥ −1 u ∈ V \\ ∑_{v:uv∈E} y(uv) − ∑_{v:vu∈E} y(vu) & ≥ −1 u ∈ V \\ y & ≥ 0 \end{aligned}  (5.2)

A feltételeket összefoglalva kapjuk:

\begin{aligned}−1 ≤ ∑_{v:vu∈E} y(vu) − ∑_{v:uv∈E} y(uv) & ≤ 1 u ∈ V \\ y & ≥ 0 \end{aligned}  (5.2′)

Ez a feladat a minimális költségű áram probléma egyfajta általánosításának tekinthető, de egy egyszerű konstrukció segítségével igazolható, hogy valójában ekvivalens vele. Legyen ugyanis s egy új csúcs, és G minden csúcsából vezessünk s-be egy-egy élt. Egy új us élen legyen f(us) := −1, g(us) := 1 (az eredeti e ∈ E éleken f(e) = 0, g(e) = +∞ volt). Jelölje a kibővített élek halmazát E′. Tetszőleges y : E → R vektorhoz legyen y′ : E′ → R a következőképpen definiálva: y′(e′) := y(e′), ha e′ ∈ E, és y′(e′) := ∑ y(vu)−∑ y(uv), ha e′ = us(u ∈ V). Könnyen látható, hogy y pontosan akkor teljesíti (5.2′)-t ha y′ megengedett áram (V + s, E′)-ben.

Súlyozott változat

Ha a feladat ∑_{v} c(v)|π(v)| minimalizálása, ahol c ≥ 0 adott költségfüggvény, a fenti gondolatmenetet követve lényegében (5.2)-höz, illetve (5.2′)-höz jutunk, csak −1 és 1 helyett értelemszerűen mindenhol −w(u) és w(u) áll. A fenti konstrukcióban ennek megfelelően kell beállítani az új élek kapacitását.

5.1.2. Minimális abszolút összegű áram

Legyen G = (V, E) adott irányított gráf, f, g : E → R alsó és felső kapacitás az éleken, f ≤ g. Keressünk megengedett áramot, melynek ∑ |x(e)| abszolút összege minimális!

Induljunk ki egy tetszőleges x megengedett megoldásból (f ≤ x ≤ g). Célunk ennek a megoldásnak a javítása, vagyis olyan x′ megengedett megoldás keresése, melyre ∑ |x′(e)| > ∑ |x(e)|, vagy annak igazolása, hogy x optimális. Készítsük el a V ponthalmazon a H_{x} = (V, E′) segédgráfot a következőképpen: uv legyen előre-él, ha uv ∈ E és x(uv) < g(uv); vu pedig hátra-él, ha uv ∈ E és x(uv) > f(uv). A továbbiakban egy E′-beli él előjelén az x-nek a kérdéses él E-beli eredetijén felvett értékének előjelét értjük; egy E′-beli uv él kapacitásán pedig g(uv) − x(uv)-t illetőleg x(uv) − f(uv)-t.

Ismert, hogy ha H_{x}-ben létezik egy C irányított kör, akkor a megfelelő Ebeli éleken tudjuk x-et úgy módosítani, hogy egy megengedett x′ megoldást kapjunk: x′(uv) := x(uv) + δ, ha uv előre-él, és x′(uv) := x(uv) − δ, ha vu hátra-él. Itt δ legfeljebb a minimális kapacitás C élein; tegyük azonban fel még azt is, hogy

δ ≤ min({|x(uv)| : uv negatív előre-él} ∪ {|x(uv)| : vu pozitív hátra-él})

Nézzük, hogyan változik az abszolút összeg egy ilyen módosítás során: a C-beli negatív előre- és pozitív hátra-éleken „nyerünk” δ-t, a többin ugyanennyit „veszítünk”. Összességében tehát akkor járunk jól, ha C-ben fennáll:

neg. előre- és poz. hátra-élek száma >

> nemneg. előre- és nempoz. hátra-élek száma

(5.3)

Definiáljuk E′-n a következő költségfüggvényt:

c(uv) := \{ \begin{matrix}1 & , ha uv nemnegatív előre-él vagy nempozitív hátra-él \\ -1 & , ha uv negatív előre-él vagy pozitív hátra-él \end{matrix}

A c költségfüggvény segítségével az (5.3) feltétel egyszerűen így fogalmazható meg: c(C) < 0. Vagyis H_{x}-ben negatív kör mentén javítva jobb megoldáshoz jutunk, ha pedig H_{x}-ben nincs negatív kör, úgy x optimális megoldás.

5.2. Minimális bázisok matroidban

Legyen M adott matroid az S halmazon, w : S → R adott súlyfüggvény a pontokon. Emellett adottak a B_{1}, …, B_{k} bázisok. A feladat a súlyok módosítása úgy, hogy mind a k bázis minimális súlyú legyen az új súlyokra nézve. Azaz olyan x : s → R vektort keresünk, amelyre B_{1}, …, B_{k} w + x-minimálisak. Feltéve, hogy a pontokon adott még egy c ≥ 0 költségfüggvény is, ezt a módosítást úgy akarjuk végrehajtani, hogy a felmerülő c|x| = ∑ c(s)|x(s)| összköltség a lehető legkisebb legyen.

A bázisok minimalitását alapkörös feltételekkel tudjuk leírni a következőképpen: egy (s,z) pontpárra ha van olyan B_{i} bázis, hogy s ∈ B_{i}, z ∉ B_{i} és s eleme z alapkörének, akkor teljesülnie kell a (w + x)(s) ≤ (w + x)(z) feltételnek. Jelöljük az ilyen párok halmazát P -vel. A feltételeket átrendezve kapjuk:

x(s) − x(z) ≤ w(z) − w(s) (s, z) ∈ P

Ez nem más mint egy (súlyozott) minimális abszolút összegű potencál feladat az (S, P) gráfon, ahol egy (s, z) él költségét w(z) − w(s) -nek definiáljuk. Az előző pontban látottak szerint tehát egy minimális költségű áram problémához jutunk.

5.3. Többoptimumos matroid metszet

Legyen M_{1} = (S, I_{1}) és M_{2} = (S, I_{2}) két matroid az S halmazon, w tetszőleges súly-, c pedig nemnegatív költségfüggvény S-en. Ezúttal m darab k elemű közös független halmazt akarunk egyszerre minimális súlyúvá tenni w alkalmas megváltoztatásával.

Egy F_{j} ∈ I_{1}^{k}∩I_{2}^{k} (j = 1, …, m) halmaz pontosan akkor lesz w′-minimális, ha teljesülnek a 3.2.2 lemma feltételei. A 3.2.3 lemmát is figyelembe véve és bevezetve a

\begin{matrix}P_{i} := ⋃_{j=1}^{m} & (\{(s, z) : s ∈ F_{j}, z ∉ F_{j}, s ∈ C_{i}(F_{j}, z)\} ∪ \\ ∪ \{(s, z) : s ∈ F_{j}, z ∉ F_{j}, z + B ∈ I_{i}\}) (i = 1, 2) \end{matrix}

jelölést azt kapjuk, hogy F_{1}, …, F_{m} pontosan akkor lesznek w′-minimálisak I_{1}^{k} ∩ I_{2}^{k}-ban, ha léteznek w_{1}, w_{2} súlyozások, melyekre

\begin{aligned}w_{i}(s) & ≤ w_{i}(z) (s, z) ∈ P_{i}, i = 1, 2 \\ w_{1} + w_{2} & = w′ \end{aligned}  (5.4)

Ha most w′-t w + x alakban keresnénk, ∑ c(s)|x(s)|-et kellene minimalizálnunk, és most x előjeléről sajnos semmit nem tudunk mondani. Ezért inkább a w′ = w + x_{1} − x_{2}, x_{1}, x_{2} ≥ 0 előállítással próbálkozunk. Ekkor az inverz probléma a

\begin{matrix}min ∑_{s∈S} c(s)x_{1}(s) & + ∑_{s∈S} c(s)x_{2}(s) \\ w_{i}(z) − w_{i}(s) & ≥ 0  (s, z) ∈ P_{i}, i = 1, 2 \\ w_{1}(s) + w_{2}(s) − x_{1}(s) + x_{2}(s) & = w(s) s ∈ S \\ x_{1}, x_{2} ≥ 0 \end{matrix}  (5.5)

alakban áll elő. (5.5) duálja a

\begin{matrix}min ∑_{s∈S}(−w(s))π(s) \\ ∑_{z:(z,s)∈P_{i}} y_{i}(z, s) − ∑_{z:(s,z)∈P_{i}} y_{i}(s, z) + π(s) & = 0  s ∈ S, i = 1, 2 \\ −c(s) ≤ π(s) & ≤ c(s) s ∈ S \\ y_{1}, y_{2} ≥ 0 \end{matrix} (5.6)

lineáris program, ami nem más, mint egy minimális költségű áram feladat az alábbi G = (V, E) gráfban:

\begin{matrix}V := & \{s_{1}, s_{2} : s ∈ S\} \\ E := & \{(s_{1}, z_{1}) : (s, z) ∈ P_{1}\} ∪ \{(z_{2}, s_{2}) : (s, z) ∈ P_{2}\} ∪ \{(s_{1}, s_{2}) : s ∈ S\} \end{matrix}

Ezzel tehát az inverz minimális közös függetlenek problémáját visszavezettük egy minimális költségű áram feladatra, amit már erősen polinomiális időben meg tudunk oldani.

5.4. Minimális költségű utak

5.4.1. s—t utak

Legyen G = (V, E) irányított gráf, s, t ∈ V, c adott költségfüggvény az éleken. Célunk olyan c′ költségfüggvény keresése, melyre nézve az adott P_{1}, …, P_{k} s—t utak mind minimálisak, és emellett ∑ |c′(e) − c(e)| is minimális.

Jól ismert, hogy ha egyetlen P s—t utunk van, úgy ez pontosan akkor lesz c′-minimális valamely c′-re, ha létezik egy π c′-megengedett potenciál a csúcsokon, ami P minden élén pontos. Azaz:

\begin{aligned}π(v) − π(u) & ≤ c′(uv) uv ∈ E \\ π(v) − π(u) & = c′(uv) uv ∈ P \end{aligned}  (5.7)

5.4.1. Állítás. Ha P_{1}, …, P_{k} adott c′-minimális s—t utak, π olyan megengedett potenciál, amely P_{1} minden élén pontos, akkor π pontos P_{i} (i = 2, …, k) minden élén is.

Bizonyítás. Tetszőleges i = 2, …, k esetén P_{i} költségére a következőt kapjuk (felhasználva π megengedettségét):

\begin{aligned}c′(P_{i}) & = ∑_{uv∈P_{i}} c′(uv) ≥ ∑_{uv∈P_{i}}(π(v) − π(u)) = π(t) − π(s) = \\ & = ∑_{uv∈P_{1}}(π(v) − π(u)) = ∑_{uv∈P_{1}} c′(uv) = c′(P_{1}) \end{aligned}  (5.8)

Mivel c′(P_{1}) = c′(P_{i}), fent végig egyenlőség áll, ami éppen azt jelenti, hogy c′(uv) = π(v) − π(u) (uv ∈ P_{i}). □

Ezen állítás értelmében tehát a c′ költségfüggvényre nézve akkor lesz mind a k út minimális, ha létezik egy olyan megengedett potenciál, ami ⋃ P_{i} élein pontos. Ezek után már felírhatjuk az inverz probléma lineáris programját (c′-t c + x_{1} − x_{2} alakban keressük):

\begin{matrix}min ∑_{uv∈E}(x_{1}(uv) + x_{2}(uv)) \\ π(v) − π(u) − x_{1}(uv) + x_{2}(uv) & ≤ c(uv) uv ∈ E \ ⋃_{i=1}^{k} P_{i} \\ π(v) − π(u) − x_{1}(uv) + x_{2}(uv) & = c(uv) uv ∈ ⋃_{i=1}^{k} P_{i} \\ x_{1}, x_{2} ≥ 0 \end{matrix}  (5.9)

(5.9) duálja:

\begin{aligned}min ∑_{uv∈E} c(uv)y(uv) \\ ∑_{v:vu∈E} y(vu) − ∑_{v:uv∈E} y(uv) & = 0 u ∈ V \\ −1 ≤ y(uv) & ≤ 1 uv ∈ E \\ y(uv) & ≥ 0 uv ∈ E \ ⋃_{i=1}^{k} P_{i} \end{aligned}  (5.10)

Ez pedig nem más, mint egy egyszerű minimális költségű áram feladat G-n a c költségfüggvény mellett; a felső kapacitás minden élen 1, az alsó ⋃ P_{i} élein −1, a többin 0.

5.4.2. Tetszőleges útrendszer

Tekintsük most az általánosabb esetet, amikoris adottak az (s_{k}, t_{k}) pontpárok (k = 1, …, r), és mindegyikhez egy P_{k}(s_{k}, t_{k}) egyszerű út; a feladatunk a költségfüggvény módosítása úgy, hogy továbbra is nemnegatív maradjon és minden k-ra P_{k} legrövidebb s_{k}—t_{k} út legyen. Lineáris programként felírva:

\begin{matrix}min x^{1} + x^{2} \\ Q_{P_{k}^{j}}(c + x^{1} − x^{2}) & ≥ Q_{P_{k}}(c + x^{1} − x^{2}) j = 1, …, h_{k}, k = 1, …, r \\ x^{1}, x^{2} ≥ 0 \\ x^{2} ≤ c \end{matrix} (5.11)

ahol Q_{P} jelöli egy P egyszerű út karakterisztikus vektorát, {P_{k}^{1}, …, P_{k}^{h(k)}} pedig az összes s_{k}—t_{k} egyszerű utat (k = 1, …, r).

Az y_{kj} és y^{1} = (y_{1}, …, y_{m}) duálváltozókkal felírható (5.11) duálja:

\begin{matrix}max ∑_{k,j} c(Q_{P_{k}} − Q_{P_{k}^{j}})y_{kj} − cy^{1} \\ ∑_{k,j} y_{kj}(Q_{P_{k}^{j}} − Q_{P_{k}}) & ≤ 1 \\ − ∑_{k,j} y_{kj}(Q_{P_{k}^{j}} − Q_{P_{k}}) − y^{1} & ≤ 1 \\ y_{kj}, y^{1} ≥ 0 \end{matrix}  (5.12)

Az egyenlőtlenségek egyenlőséggé tételéhez vezessük be az

y^{2} = (y_{m+1}, …, y_{2m}) és y^{3} = (y_{2m+1}, …, y_{3m})

nemnegatív slack-változókat. Ekkor (5.12) átírható a következő alakba:

\begin{matrix}max ∑_{k,j} f_{kj}y_{kj} + ∑_{j=1}^{3m} c_{j}y_{j} \\ ∑_{k,j} a_{kj}y_{kj} + ∑_{j=1}^{3m} a_{j}y_{j} & = 1 \\ y, y_{kj} ≥ 0 \end{matrix}  (5.13)

ahol az eddig ismeretlen dolgok jelentése:

(a_{1}, …, a_{m}) = ( \begin{matrix}0_{m} \\ −I_{m} \end{matrix} )
(a_{m+1}, …, a_{2m}) = ( \begin{matrix}I_{m} \\ 0_{m} \end{matrix} )
(a_{2m+1}, …, a_{3m}) = ( \begin{matrix}0_{m} \\ I_{m} \end{matrix} )
(f_{1}, …, f_{m}) = (−c_{1}, …, −c_{m})
f_{j} = 0 (m + 1 ≤ j ≤ 3m)
f_{kj} = c(Q_{P_{k}} − Q_{P_{k}^{j}})
a_{kj} = ( \begin{matrix}Q_{P_{k}^{j}} − Q_{P_{k}} \\ Q_{P_{k}} − Q_{P_{k}^{j}} \end{matrix} )

(5.13) oszlopainak száma h_{1} + ⋯ + h_{r}, ami óriási szám lehet, vagyis az összes oszlop explicit előállítása algoritmikus szempontból nem járható út. Az alábbiakban ismertetésre kerülő oszlopgeneráló módszer [11] lényege, hogy a legtöbb oszlop csak implicit fog szerepelni a megoldás során.

Először is írjuk fel (5.13) egyfajta gyengítését, melyet a továbbiakban szubproblémának fogunk nevezni.

\begin{matrix}max ∑_{j=1}^{3m} f_{j}y_{j} \\ ∑_{j=1}^{3m} a_{j}y_{j} & = 1 \\ y ≥ 0 \end{matrix}  (5.14)

A szubproblémának nyilvánvalóan bázismegoldása lesz az

y_{1} = ⋯ = y_{m} = 0, y_{m+1} = ⋯ = y_{3m} = 1

vektor (a bázis B = I_{2m}, emellett f_{B} = 0). Valójában ez optimális megoldás is, hiszen a duálváltozókra π = f_{B}B^{−1} = 0, a redukált költségekre pedig

z_{j} = πa_{j} − f_{j} = −f_{j} = \{ \begin{matrix}c_{j} & , j = 1, …, m \\ 0 & , j = m + 1, …, 3m \end{matrix}

Egészítsük ki ezt az y-t y_{kj} = 0-kal! Ahhoz, hogy az így kapott vektor (5.13) optimális megoldása legyen, annak kell fennállnia, hogy

z_{kj} = πa_{kj} − f_{kj} = c(Q_{P_{k}^{j}} − Q_{P_{k}}) ≥ 0

Azaz:

cQ_{P_{k}^{j}} ≥ cQ_{P_{k}}

ami éppen azt jelenti, hogy minden k-ra P_{k} c-legrövidebb s_{k} −t_{k} út. Ezt r darab legrövidebb út kereséssel ellenőrizhetjük. Ha mindegyik P_{k} út legrövidebb út, kész vagyunk (nem kellett c-t módosítani).

Tegyük fel, hogy valamely 1 ≤ k_{0} ≤ r-re azt kapjuk, hogy nem az eredetileg adott P_{k_{0}} út a legrövidebb:

cQ_{P_{k_{0}}^{j_{0}}} < Q_{P_{k_{0}}}

Ekkor az y_{k_{0}j_{0}} változót bevesszük a szubproblémába, vagyis hozzáadjuk az

( \begin{matrix}f_{k_{0}j_{0}} \\ a_{k_{0}j_{0}} \end{matrix} )

oszlopot, így kapunk egy ún. megszorított alapproblémát (restricted master problem, RMP).

Tegyük fel most, hogy már megoldottunk egy RMP-t valahány y_{kj} változóval. Jelölje most is B az optimális bázist; a duálváltozókra ekkor π = (π^{1}, π^{2}) = f_{B}B^{−1}. Ez esetben azt kell ellenőrizni, hogy

z_{kj} = πa_{kj} − f_{kj} = (π^{1}, π^{2}) ( \begin{matrix}Q_{P_{k}^{j}} − Q_{P_{k}} \\ Q_{P_{k}} − Q_{P_{k}^{j}} \end{matrix} ) − c(Q_{P_{k}} − Q_{P_{k}^{j}}) =
= (c + π^{1} − π^{2})(Q_{P_{k}^{j}} − Q_{P_{k}}) ≥ 0

Azaz ( c̃ = c + π^{1} − π^{2} jelöléssel):

c̃Q_{P_{k}^{j}} ≥ c̃Q_{P_{k}} ∀k ∀j

vagyis hogy minden k-ra P_{k} c̃-legrövidebb s_{k}—t_{k} út.

Megjegyzés. A módszer teljes mértékben heurisztikus: mindig az elsőként megtalált sértő feltételt veszi hozzá a megoldandó feladathoz, és semmi sem garantálja, hogy nem kell majd nagy méretű RMP-ket megoldani. A gyakorlatban azonban meglepően jól használható ez az algoritmus (lásd [11]).

5.5. Minimális párosítások

Legyen G = (A, B; E) páros gráf, élein egy c költségfüggvénnyel, és legyenek M_{1}, …, M_{k} adott teljes párosítások. A feladat c (minél kisebb mértékű) módosítása úgy, hogy mind a k párosítás minimális legyen.

Tudjuk, hogy egy teljes párosítás pontosan akkor minimális költségű, ha létezik olyan megengedett potenciál, ami a párosítás éleken pontos. (A megengedettség itt is azt jelenti, hogy minden uv ∈ E élre π(v) − π(u) ≤ c(uv).)

5.5.1. Állítás. Ha M_{1}, …, M_{k} c′-minimális teljes párosítások, és π olyan megengedett potenciál, amely M_{1} minden élén pontos, akkor π M_{i} (i = 2, …, k) élein is pontos.

Bizonyítás. Tetszőleges i = 2, …, k esetén M_{i} költségére a következőt kapjuk (felhasználva π megengedettségét):

\begin{aligned}c′(M_{i}) & = ∑_{uv∈M_{i}} c′(uv) ≥ ∑_{uv∈M_{i}}(π(v) − π(u)) = ∑_{v∈B} π(v) − ∑_{u∈A} π(u) = \\ & = ∑_{uv∈M_{1}}(π(v) − π(u)) = ∑_{uv∈M_{1}} c′(uv) = c′(M_{1}) \end{aligned} (5.15)

Mivel c′(M_{1}) = c′(M_{i}), fent végig egyenlőség áll, ami éppen azt jelenti, hogy c′(uv) = π(v) − π(u) (uv ∈ M_{i}). □

Ezek szerint az inverz probléma ugyanúgy írható fel, mint a minimális költségű utak esetében, vagyis itt is egy minimális költségű áram feladathoz jutunk.

Paraméteres inverz problémák

Paraméteres optimalizálási problémáról akkor beszélünk, amikor a feladat célfüggvénye a változók mellett még valamilyen paramétertől vagy paraméterektől is függ. Az ilyen problémák központi kérdése, hogy az optimális megoldások halmazát hogyan befolyásolja a paraméter értékének (általában folytonos) változása. A témával részletesebben foglalkozik Jüttner Alpár szakdolgozata (1998).

A paraméteres inverz probléma a következőképpen értelmezhető: legyen P adott paraméteres optimalizálási probléma, melynek célfüggvénye λC alakú, ahol λ ∈ R_{+}^{k} a paraméter, C pedig k × n-es költségmátrix (n a változók száma). Legyen x^{0} adott megengedett megoldása P -nek; keresendő a λ paraméternek olyan értéke, amire x^{0} λC-optimális megoldás. Annak érdekében, hogy a triviálisan adódó λ = 0 megoldást kizárjuk, még valamit fel kell tennünk a paraméterről, például, hogy ∑ λ_{j} = 1. E megkötés mellett így is fogalmazhatunk: adottak a c_{1}, …, c_{k} költségfüggvények és keressük ezeknek olyan olyan c konvex kombinációját, amire x^{0} c-optimális.

A fenti definicióból látszik, hogy a paraméteres inverz probléma alapvetően nem optimalizálási feladat: mindegy, hogy a paraméter „jó” értékei közül melyiket találjuk meg. Ily módon a paraméteres inverz feladat nehezen hasonlítható össze az eddig tárgyalt inverz fogalommal, egyikről sem mondható, hogy általánosítása a másiknak.

Példaként tekintsük az inverz paraméteres legrövidebb út problémát a G = (V, E) irányított gráfban. Jól ismert, hogy egy adott P_{0} s—t út pontosan akkor minimális költségű a λC költségvektorra nézve, ha létezik olyan π λCmegengedett potenciál, ami P_{0} minden élén pontos. Ennek alapján olyan λ-t keresünk, melyre fennáll:

\begin{aligned}λC(uv) − π(v) + π(u) & = 0 uv ∈ P_{0} \\ λC(uv) − π(v) + π(u) & ≥ 0 uv ∉ P_{0} \\ ∑_{j=1}^{k} λ_{j} & = 1 \\ λ ≥ 0 \end{aligned}  (6.1)

A Farkas-lemma szerint (6.1) pontosan akkor oldható meg, ha nem létezik olyan y és μ, melyekre

\begin{aligned}c_{j}y + μ & ≤ 0 j = 1, …, k \\ ∑_{v:uv∈E} y(uv) − ∑_{v:vu∈E} y(vu) & = 0 u ∈ V \\ y(uv) & ≥ 0 uv ∉ P_{0} \\ μ & > 0 \end{aligned}  (6.2)

ahol c_{j} a C mátrix j-edik sora. Vagyis pontosan akkor található jó paraméter, ha nem létezik olyan áram G-ben, ami az E \ P_{0}-beli éleken nemnegatív és mindegyik c_{j}-re nézve negatív költségű.

Irodalomjegyzék

[1] R. K. Ahuja, T. L. Magnanti, J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.

[2] R. K. Ahuja, J. B. Orlin. Inverse Optimization, Part I: Linear Programming and General Problem. MIT Working Paper SWP# 4002, 1998.

[3] R. K. Ahuja, J. B. Orlin. Inverse Optimization, Part II: Network Flow Problems. MIT Working Paper SWP# 4003, 1998.

[4] R. K. Ahuja, J. B. Orlin. Combinatorial Algorithms for Inverse Network Flow Problems. MIT Working Paper SWP# 4004, 1998.

[5] D. Burton, Ph. L. Thoint. On an instance of the inverse shortest paths problem. Mathematical Programming 53, 45-61, 1992.

[6] D. Burton, Ph. L. Thoint. On the use of an inverse shortest paths algorithm for recovering linearly correlated costs. Mathematical Programming 63, 1-22, 1994.

[7] J. Edmonds, R. Giles. A min-max relation for submodular functions on graphs. Annals of Discrete Mathematics 1, 185-204, 1977.

[8] A. Frank. A weighted matroid intersection algorithm. J. Algorithms bf 2, 328-336, 1981.

[9] A. Frank. An algorithm for submodular functions on graphs. Annals of Discrete Mathematics 16, 97-120, 1982.

[10] Y. Li. Inverse Combinatorial Optimization Problems and Connected Factor Problems. Doktori disszertáció, Institute of Systems Science, Chinese Academy of Sciences, Beijing, 1996.

[11] J. Zhang, Z. Ma, C. Yang. A Column Generation Method for Inverse Shortest Path Problems. ZOR 41, 347-358, 1995.