Paraméteres problémák a kombinatorikus optimalizálásban és ezek távközlési alkalmazásai A doktori értekezés tézisei
Alpár Jüttner Matematika Doktori Iskola
vezet®je: Laczkovich Miklós akadémikus Alkalmazott Matematika Doktori Program
vezet®je: Prékopa András akadémikus
Témavezet®: Frank András
tanszékvezet® egyetemi tanár,
a metemetikai tudomány doktora
Eötvös Loránd Tudományegyetem
2006.
1.
Célkit¶zések
Az értekezés gyakorlati alkalmazásokkal bíró matematikai problémákat vizsgál a kombinatorikus optimalizálás területér®l. Ami összekapcsolja ezeket a feladatokat, az az, hogy a diszkrét kombinatorikus problémákat egy- vagy többváltozós paraméteres problémák vagyis folytonos optimalizálási feladatok megoldására vezetjük vissza. A megfelel® folytonos optimalizálási feladatok megoldására több megközelítést is bemutatunk. Az els® alkalmazott módszer a N. Megiddo által kifejlesztett paraméteres keresés. Ezt az elegáns módszert az értekezés részletesen ismerteti, hisszük ugyanis, hogy e módszer még sok új alkalmazásra találhat a kombinatorikus optimalizálás terülétén. Ezen kívül több példát is mutatunk arra, hogy a folytonos optimalizásió alapvet® közelít® eljárásai mint például a Newton approximáció vagy a szubgradiens módszer segítségével hogyan kaphatunk diszkrét optimalizációs feladatok optimális vagy közel optimális megoldását véges vagy akár er®sen polinomiális id®ben. Mint már említettük, az értekezés nagy hangsúlyt fektet a gyakorlati alkalmazásokra. Fontos célunk bemutatni valós alkalmazásokból származó olyan összetett optimalizálási feladatokat, amelyekre nemtriviális matematikai módszerek és megfontolások segítségével tudunk gyakorlatban is használható megoldást adni. A bemutatott alkalmazott kutatások legnagyobb részét az Ericsson magyarországi kutatóintézete, a
Tra c Analysis and Net-
work Performance Laboratory keretein belül végeztük, így az alkalmazott problémak nagy
része a távközlés területér®l származik. A kapott megoldások gyakorlati felhasználhatóságát a problémák kísérleti elemzésével is demonstráljuk.
2.
2.1.
Eredmények
Költségkorlátos optimalizáció
Legyen az alapproblémának nevezett kombinatorikus optimalizálási feladat az E alaphalmazon a következ® formában megadva: 1. De níció.
(1)
max{wx : x ∈ X},
ahol X ⊆ R a megengedett megoldások halmaza és w ∈ R a célfüggvény. Feltesszük még, hogy a megengedett megoldások P konvex burka egy (nem feltétlen korlátos) poliéder. Ekkor egy adott c : E −→ R költségfüggvény és B > 0 költégkorlát mellett az alapproblémához E
E
2
tartozó költségkorlátos optimalizálási feladaton a következ® érték (és az y optimumhely) kiszámítását értjük: ∗
(2)
α := min{max{(w − y)x : x ∈ X} : y ∈ RE , y ≥ 0, cy ≤ B} Az értekezésben bebizonyítjuk a következ® tételt.
Tegyük fel, hogy létezik egy T id®ben futó algoritmus, amely tetsz®leges u ∈ R vektorra megadja a
2. Tétel.
E
(3)
max{wx : x ∈ P : x ≤ u}
feladat primál és duál megoldását, emellett az algoritmus kielégíti az úgynevezett linearitási feltételt az u-ban (lásd kés®bb), akkor a (2) probléma megoldására létezik egy O(T ) id®ben futó algoritmus. 2
A fenti tételben megkonstruált algoritmus Megiddo paraméteres keresés nev¶ eljárásán alapul [Meg79]. Ezen eljárás alkalmazásához az alapfeladatot megoldó algoritmusra megkötéseket kell tennünk, ez az úgynevezett
linearitási feltétel. Az elnevezés talán némi-
leg félrevezet®: a megkötés nem a futásid®re vonatkozik, hanem arra, hogy az algoritmus
milyen m¶veleteket végezhet a bemenetével. Érdekes módon, bár a paraméteres keresést számos feladat megoldására felhasználták, a linearitási feltételt mindeddig csak intuitív módon de niálták. Mi az értekezésben megadjuk e feltétel formális de nícóját, és a paraméteres keresés egy általános (absztrakt) formáját is bemutatjuk. Maga a 2. Tétel sok ismert költségkorlátos feladatra azonnal megoldást szogláltat, így a [Ful59, AO95, Har77, FH75, FSO99, FSO98] cikkekben vizsgált feladatokra is. Ezek mellett az értekezés olyan új alkalmazásokat is bemutat, amelyekre eddig nem volt ismeretes er®sen polynomiális algoritmus. Az els® ilyen alkalmazás a
áramfeladat.
költségkorlátos minimális költég¶
3. Probléma (Költségkorlátos minimális súlyú áramfeladat).
Adott egy
G
=
irányított gráf, egy w : E −→ R súlyfüggvény, valamint l, u : E −→ R alsó és fels® korlátok. Ezen kívül adott még az élsúlyok változtatásának költségét leíró c : E −→ R függvény és egy B > 0 költségkorlát. Feladat a minimális súlyú áram súlyát élek súlyának megnövelésével minél jobban megnövelni az adott B költségkorlát betartása mellett. 4. Tétel. A költségkorlátos minimális súlyú áramfeladat er®sen polinomiális id®ben megoldható. (V, E)
3
A következ®
költségkorlátos matroid metszet probléma Frederickson és Solis-Oba maxi-
mális súlyú matroidokra vonatkozó eredményének [FSO98] kiterjesztése matroid metszetekre. Ez a probléma volt a fejezeben bemutatott kutatási eredmények f® motivációja.
Legyen adott az M = (E, I ) és az M = (E, I ) matroid a közös E alaphalmaz felett, a w : E −→ R súly-, a c : E −→ R költégfüggvény és a B > 0 költségkorlát. Feladat az M és M maximális súlyú közös bázisának súlyát az E elemeinek tetsz®leges csökkentésével jobban lecsökkenteni. Egy e ∈ E elem súlya α(e)-vel való csökkentésének költsége α(e)c(e), a csökkentések összköltsége a B költségkorlátot nem haladhatja meg. 6. Tétel. A költségkorlátos matroid metszet probléma er®sen polinomiális id®ben megoldható. A 3. és az 5. feladatok közös általánosítása a következ® költségkorlátos szubmoduláris folyamfeladat. 7. De níció (pl. [Fuj91]). Az F ⊆ 2 halmazrendszert keresztez® rendszernek hívjuk a V felett, ha minden keresztez® X, Y ∈ F párra (azaz ha X, Y ∈ F , X ∩Y 6= ∅, X\Y 6= ∅, Y \X 6= ∅, és X ∪ Y 6= V teljesül) X ∪ Y, X ∩ Y ∈ F teljesül. Egy b : F −→ R függvény keresztez®n szubmoduláris az F keresztez® rendszer felett, ha minden keresztez® X, Y ∈ F párra 5. Probléma (Költségkorlátos matroid metszet feladat). 1
2
1
2
1
2
V
b(X) + b(Y ) ≥ b(X ∪ Y ) + b(X ∩ Y )
teljesül.
(4)
Legyen adott a G = (V, E) irányított gráf, f, g : E −→ R ∪ {±∞} alsó és fels® capacitások az éleken és a w : E −→ R súlyfüggvény. Legyen F ⊆ 2 egy keresztez® rendszer, amire ∅, V ∈ F teljesül és legyen b : F −→ R egy keresztez® szubmoduláris függvény. Tegyük még fel, hogy b(∅) = b(V ) = 0. Ekkor a szubmoduláris folyamproblémán a következ® optimalizálási feladatot értjük. 8. De níció (pl. [Fuj91]).
V
wx
(5a)
f ≤ x ≤g
(5b)
max
minden X ⊆ V -re, (5c) ahol % (X) illetve δ (X) az x komponenseinek az X -be be- illetve az X -b®l kilép® éleken vett összege. %x (X) − δx (X) ≤ b(X)
x
x
4
Legyen adott egy szubmoduláris folyamfeladat a 8. De níció szerint, egy c : E −→ R költségfüggvény, és egy B költségkorlát. Ekkor a költségkorlátos szubmoduláris folyamfeladat a következ®: 9. Probléma (Költségkorlátos szubmoduláris folyamfeladat).
(6)
min{max{(w − y)x : x ∈ P} : y ≥ 0, cy ≤ B},
ahol
minden X ⊆ V -re}. (7) 10. Tétel. A költségkorlátos szubmoduláris folyamfeladat er®sen polinomiális id®ben megoldható. P := {x ∈ RE : f ≤ x ≤ g , %x (X) − δx (X) ≤ b(X)
A fejezetben közölt eredmények [Jüt03]-ban és [Jüt05a]-ban kerültek publikálásra. 2.2.
LP optimalizálás plusz változókkal és feltételekkel
Norton, Plotkin és Tardos [NPT92] bizonyította be a következ® két tételt.
Tegyük fel, hogy adott egy T id®ben futó algoritmus, ami legfeljebb q összehasonlítást végez, lineáris b-ben és tetsz®leges b-re megoldja a max{ax : Ax ≤ b} lineáris programozási feladatot. Ekkor minden rögzített d-re létezik egy O(T q ) id®ben futó algoritmus, ami tetsz®leges d oszlopú C mátrixra megoldja a max{ax + cz : Ax + Cz ≤ b} feladatot. 12. Tétel ([NPT92]). Tegyük fel, hogy adott egy T id®ben futó algoritmus, ami legfeljebb q összehasonlítást végez, lineáris a-ban és tetsz®leges a-ra megoldja a max{ax : Ax ≤ b} lineáris programozási feladatot. Ekkor minden rögzített d-re létezik egy O(T q ) id®ben futó algoritmus, ami tetsz®leges d sorú C mátrixra és c vektorra megoldja a max{ax : Ax ≤ b, Cx ≤ c} feladatot. 11. Tétel ([NPT92]).
d+1
d+1
Az értekezésben a fenti algotimusok futásidejét O(T q d )-re javítjuk. Egészen pontosan a következ® általánosabb tétel kerül bizonyításra:
Tegyük fel, hogy adott egy T id®ben futó algoritmus, ami legfeljebb q összehasonlítást végez, lineáris b-ben és tetsz®leges b-re megoldja a max{ax : Ax ≤ b} lineáris programozási feladatot. Tekintsük a következ® lineáris programozási feladatot: 13. Tétel.
max cx + dy 5
(8a)
Ax + By ≤ b,
Ly ≤ l, Ey = e. O (T + |L| + |E|) q dim R
(8b)
Ekkor a (8a)-(8b) feladat id®ben megoldható, ahol R := {y ∈ R : Ly ≤ l, Ey = e} és |L| illetve |E| az L és E mátrixok méretét jelöli. k
A fenti tétel [Jüt05c]-ben került publikálásra. 2.3.
Er®forráskorlátos optimalizálási feladatok
Tekintsünk egy E alaphalmazt, egy c : E −→ R+ költségfüggvényt és a következ® absztrakt optimalizálási feladatot:
X
min{
c(e) : P ∈ P},
(9)
e∈P
ahol P ⊆ 2 jelöli a megengedett megoldások halmazát. E
késleltetésnek nevezzük és a ∆ ∈ R késleltetés korlát. E jelölésekkel a (9) feladathoz tartozó er®forráskorlátos optimalizálási feladat a következ®: Legyen adott még a d : E −→ R+ függvény ennek értékeit +
X
min{
c(e) : P ∈ P,
X
d(e) ≤ ∆}.
(10)
e∈P
e∈P
Az ilyen típusú problémák még olyan egyszer¶en megoldható alapproblémák esetén is
N P -teljesek, mint például a legrövidebb út probléma vagy a minimális párosítás probléma páros gráfban (lásd pl. [GJ79]). Az e problémaosztályhoz tartozó feladatok közelít® megoldásának az egyik szokásos útja, hogy Lagrange relaxáció segítségével megszabadulunk a plusz feltételt®l. Így a feladat egy egyváltozós konkáv függvény maximalizálására redukálódik. A relaxált feladat megoldására több szerz® ([HZ80, BG96, JSMR01]) egymástól függetlenül kifejlesztett egy egyszer¶ módszert amit mi [HZ80] után
Handler-Zang eljárásnak nevezzük. Habár az eljá-
rás a gyakorlatban rendkívül hatékonynak bizonyult, az algoritmus pontos futásideje sokáig nem volt ismert. Az értekezésben a következ® két tételt bizonyítjuk be.
A Handler-Zang algoritmus O(|E| log |E|) iteráció után véget ér. 15. Tétel. Az er®forráskorlátos legrövidebb út probléma esetén a Handler-Zang algoritmus O(m log m) iteráció után véget ér, így az algoritmus teljes futásideje O(m log m + mn log m), ahol n illetve m a gráf pontjainak illetve éleinek a száma.
14. Tétel.
2
2
2
2
3
6
er®forráskorlátos legrövidebb út probléma fontos szerepet játszik útvonalválasztási problémák, különösen távközlési hálózatok szolgáltatásmin®ség-biztosítási (Quality of Service, QoS ) feladatainak megoldásakor. Ezekben az alkalmazásokban az algoritmusok gyaAz
korlati futásidejével szemben nagyon szigorú elvárások fogalmazódnak meg. Az érteke-
zésben ezért bemutatunk két módszert a Handler-Zang eljárás gyakorlati futásidejének csökkentésére. Végül empírikus módszerekkel bemutatjuk az eljárás és a javasolt javítások alkalmazhatóságát egy valós útvonalválasztási problémára és összevetjük a legfontosabb mások által javasolt eljárásokkal. A fenti algoritmus QoS útvonalválasztási feladatokra való adaptációját [JSMR01]-ben közöltük. Erre a cikkre számos, a távközlés területén publikáló szerz® hivatkozott és a témakörrel foglalkozó több áttekint® írás is idézi. Az algoritmus elméleti futásidejének analízise [Jüt05b]-ben található. 2.4.
Hányados-optimalizálási feladatok
Legyen X megengedett megoldások egy (véges) halmaza, c : X −→ R és w : X −→ R adott függvények. Tegyük fel, hogy minden x ∈ X -re w(x) > 0 teljesül és létezik x ∈ X , amire c(x) > 0. E jelölésekkel a
16. Probléma.
Keressük az
hányados-optimalizálási feladat a következ®.
α := max
értéket és egy maximalizáló x
∗
∈X
c(x) :x∈X w(x)
megoldást.
E problémaosztály megoldására T. Radzik javasolta a
(11)
Newton-Dinkelbach
eljá-
rást [Rad98], ami a függvények egy zérushelyének megkeresésére szolgáló Newton-eljárás egy adaptációja. Ez az algoritmus mind elméletileg, mint a gyakorlatban nagyon hatékonynak bizonyult. Az értekezésben bizonyított következ® tétel az algoritmus Radzik által bizonyított futásid® becslését [Rad98] javítja meg egy O(log n)-es faktorral.
Legyen E egy véges alaphalmaz n := |E| és X ⊆ {0, 1} . Tegyük fel, hogy c és w lineáris függvények, azaz a következ® alakban állnak el®: 17. Tétel.
E
c(x) :=
X e∈E
7
ce xe
(12)
és w(x) :=
X
(13)
we xe .
e∈E
Ekkor a Newton-Dinkelbach ejárás O(|E| log |E|) iteráció után véget ér. 2
A következ® tétel a szintén Radziktól származó, az irányított aciklikus gráfokban való hányados-legrövidebb út problémára vonatkozó futásid®-becslés [Rad98] általánosítása.
Legyen E egy véges alaphalmaz n := |E| és tegyük fel, hogy X ⊆ {0, 1} éppen a Q := {x ∈ R : Ax = b, x ≥ 0} poliéder csúcsainak halmaza, továbbá c és w a 17. Tételbeli alakú. Ekkor a Newton-Dinkelbach eljárás O(n log n) lépésben véget ér.
18. Tétel.
E
E
A fenti eredmények Tomasz Radzikkal közösek, publikálásuk folyamatban van.
2.5.
UMTS hozzáférési hálózatok tervezése
Tekintsük az UMTS (Universal Mobile Telecommunications System) hozzáférési hálózatok tervezése során felmerül® következ® tervezési problémát.
Adott a hálózati csomópontok egy N halmaza, és a következ® technológiaspeci kus paraméterek: az l , d , d ∈ N és a cost ∈ R konstansok, az R ⊆ N és az R ⊆ N csúcshalmazok úgy, hogy R ⊆ R , továbbá a c : N ×N ×{1, . . . , l } −→ R költségfüggvény. E bemenet mellett a tervezési feladat egy minimális költség¶ irányított G = (N, E) gráf keresése az N csúcshalmazon, úgy, hogy • E pontdiszjunkt gyökeres irányított fákból áll, amelyek összességében lefedik az N minden pontját. Minden él a megfelel® gyökér irányába mutat, • minden pont távolsága a hozzá tartozó gyökért®l legfeljebb l , • a gyökérpontok fokszáma legfeljebb d , • a többi pont be-foka legfeljebb d , • R ⊆ R ⊆ R , ahol R a gyökérpontok halmaza. 19. Probléma.
tree
RBS
RN C
P
RN C
R
P
+
link
tree
+
tree
RN C
RBS
R
P
8
R
A minimalizálandó költségfüggvény a következ®: |R| · costRN C +
X
clink u, v, lE (u) ,
(14)
(uv)∈E
ahol l
E
(u)
az u ∈ N pont szintje, azaz az u-nak a hozzá tartozó gyökért®l való távolsága.
Az értekezés több algoritmust is bemutat ennek a feladatnak a megoldására. El®ször egy heurisztikus eljárást ismertetünk, ami a Szimulált leh¶tés nev¶ metaheurisztikus eljárás és egy speciális b-párosítást megoldó szubrutin ötvözése. Bemutatunk továbbá egy technikát az algoritmus felgyorsítására, amivel már valóban képessé válik nagyméret¶ feladatok kezelésére. Ezután azt a speciális esetet vizsgáljuk, amikor egyetlen, rögzített gyöker¶ fa tervezése a feladat, vagyis amikor RR = RP = {r}. Erre az esetre ismertetünk egy algoritmust, ami közepes méret¶ feladatok esetén képes az optimális megoldás megtalálására. Az algorithmus a branch-and-bound eljáráson alapul, az eljáráshoz szükséges alsó becslést az egészérték¶ programozási feladatként történ® felírás egy nemtriviális Lagrange relaxációjával kapjuk. Bemutatunk egy heurisztikus eljárást is, ami a Lagrange relaxáció segítségével nagyobb méret¶ feladatokra is képes közel optimális megoldást szolgáltatni. Az el®z® speciális esetre adott egzakt algoritmus segítségével adunk egy lokális javító algoritmust is az általános esetre. Fontos jellemz®je ennek az eljárásnak, hogy más lokális keresést alkalmazó algoritmusokkal ellentétben az egyes iterációkban meglehet®sen bonyolult javításokat is lehet®vé tesz. Ezután, a javasolt algoritmusokat gyakorlati példákon teszteljük és bemutatjuk, hogy az eljárások valós méret¶ tervezési feladatokra közel optimális megoldásokat szolgáltatnak elfogadható futási id® mellett. Végül a teljesség kedvéért bebizonyítjuk a probléma N P -teljességét a rögzített csúcsú egyetlen fa keresésének speciális esetében, a valós eszközöknek megfelel® technológiaspeci kus paraméterek mellett:
Legyen G(V, E) egy irányítatlan teljes gráf, r ∈ V egy adott csúcs és d ∈ N . Ezen felül legyen adott egy c : E → R költségfüggvény az éleken. Ekkor a következ® feltételekkel rendelkez® és azon belül minimális költség¶ feszít®fa megtalálása N P -nehéz feladat: • Minden csúcs r-t®l való távolsága legfeljebb 3, 20. Tétel. +
RN C
+
9
-t®l eltekintve minden pont foka legfeljebb 3, • az r foka legfeljebb d . • r
RN C
Az e fejezetben bemutatott eredmények [JOF05]-ben kerültek publikálásra.
Hivatkozások
[AO95]
R.K. Ahuja and J.B. Orlin. A capacity scaling algorithm for the constrained maximum ow problem.
[BG96]
Networks, 25:8998, 1995.
David Blokh and George Gutin. An approximation algorithm for combinatorial optimization problems with two parameters. 164, 1996.
[FH75]
D.R. Fulkerson and G.C. Harding. Maximizing the minimum source-sink path subject to a budget constraint.
[FSO98]
Mathematical Programming, 13:116118, 1975.
G.N. Frederickson and R. Solis-Oba. Algorithms for measuring perturbability in matroid optimization.
[FSO99]
Australasian J. Combin., 14:157
Combinatorica, 18:503518, 1998.
G.N. Frederickson and R. Solis-Oba. Increasing the weight of minimum spanning
Journal of Algorithms, 33:244266, 1999. S. Fujishige. Submodular Functions and Optimization. Elsevier Science Publistrees.
[Fuj91]
hers B.V., 1991.
[Ful59]
D.R. Fulkerson. Increasing the capacity of a network: the parametric budget
Management Science, pages 472483, 1959. M.R. Garey and D.S. Johnson. Computers and Intractability A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, 1979. G.C. Harding. Some budgeted optimization problems and the edge disjoint branchings problem. PhD thesis, Cornell University, 1977. problem.
[GJ79]
[Har77]
[HZ80]
G. Handler and I. Zang. A dual algorithm for the constrained shortest path problem.
Networks, 10:293310, 1980. 10
[JOF05]
Alpár Jüttner, András Orbán, and Zoltán Fiala. Two new algorithms for UMTS access network topology design. 164(2):456474, July 2005.
European Journal of Operational Research,
[JSMR01] Alpár Jüttner, Balázs Szviatovszki, Ildikó Mécs, and Zsolt Rajkó. Lagrange relaxation based method for the QoS routing problem. In 2001. [Jüt01]
Infocom. IEEE, April
Alpár Jüttner. Optimization with additional variables and constraints. EGRES report TR-2001-17, Egerváry Research Group, Hungary, 2001.
[Jüt03]
3th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Tokyo, Japan, Janu-
Alpár Jüttner. On budgeted optimization ploblems. In ary 2003.
[Jüt05a]
[Jüt05b]
Alpár Jüttner. On budgeted optimization ploblems.
Matemathics, 2005. to appear.
SIAM Journal on Discrete
4th JapaneseHungarian Symposium on Discrete Mathematics and Its Applications, Buda-
Alpár Jüttner. On resource constrained optimization problems. In pest, Hungary, June 2005.
Opera-
[Jüt05c]
Alpár Jüttner. Optimization with additional variables and constraints.
[Meg79]
N. Megiddo. Combinatorial optimization with rational objective functions.
[NPT92]
Carolyn H. Norton, S.A. Plotkin, and Éva Tardos. Using separation algorithms
tions Research Letters, 33(3):305311, May 2005.
hematics of Operations Research, 4:414424, 1979. in xed dimension.
[Rad98]
Mat-
Journal of Algorithms, 13(1):7998, 1992.
Tomasz Radzik. Fractional combinatorial optimization. In DingZhu Du and Panos Pardalos, editors,
Handbook of Combinatorial Optimization. Kluwer Aca-
demic Publishers, dec 1998.
11
