1 UVOD Kombinatorična dražba (ang. combinatorial auction) je postopek za dodeljevanje virov v različnih problemih ekonomske in logistične narave, kjer uporabnik (kupec) podaja ponudbe za kombinacije virov in ne za posamezne vire ločeno. Izkaže se, da s tem dražitelj doseže večji ekonomski učinek, hkrati pa ta postopek omogoča natančnejšo regulacijo trga. Postopek kombinatorične dražbe je med drugim v rabi na področju prodaje nepremičnin, transportnih poti in dodeljevanja frekvenc brezžičnih komunikacij. Pri dodeljevanju frekvenčnih pasov kupec predloži ponudbe za izbrane kombinacije časovnih rezin in frekvenc, pri čemer dražitelj maksimizira število kupcev, katerih zahteve so izpolnjene. V drugem krogu so nedodeljeni viri prodani tako, da maksimizirajo pretočnost sistema. S takim načinom dodeljevanja virov se lahko izognemo prodaji virov na način, ki kasneje ne omogoča vzpostavitev želenih razmer na trgu [1]. Kombinatorično dražbo je prav tako mogoče uporabiti pri dodeljevanju nosilcev pri OFDM prenosu [1]. Problem rešitve kombinatorične dražbe je dodeljevanje virov glede na prispele ponudbe, pri čemer maksimiziramo izbran kriterij, navadno je to dobiček dražitelja. Imenujemo ga tudi problem določanja zmagovalca (ang. winner determination problem) in spada v razred NP polnih problemov. Pri tem obstajajo izjeme, ki jih je mogoče rešiti s približkom v polinomskem času [3]. Cilj tega članka je eksperimentalno ovrednotenje računske in časovne zahtevnosti reševanja kombinatorične dražbe izbranih optimizacijskih problemov, kjer le te izbiramo glede na velikost problema in glede notranjih porazdelitev problema. V nadaljevanju članka v 2. poglavju predstavljamo problem kombinatorične dražbe. Uporabo dražbe v telekomunikacijah na kratko podajamo v 3. poglavju. V 4. poglavju podajamo eksperimentalne rezultate z opombami in pojasnili, zaključke navajamo v zadnjem, 5. poglavju. 2 OPTIMIZACIJSKA NALOGA IN PROBLEM KOMBINATORIČNE DRAŽBE V tem poglavju podajamo problem kombinatorične dražbe kot optimizacijsko nalogo. Dodajamo tudi potrebne opombe in pojasnila k reševanju podanega optimizacijskega problema. Problem splošne kombinatorične dražbe je določitev množice ponudb, ki maksimizirajo privzet kriterij. Množico virov (ang items, resources) označimo z M = {1,2, … ,m}. Posamezna ponudba je sestavljena iz več virov in ne le enega, označimo jo z b�, j = 1…n. S tem dosežemo, da se viri, združeni v ponudbah, nujno prodajo skupaj. Dražitelj vsaki ponudbi priredi ceno p� = p(b�). Ta cena navadno ni vsota cen posameznih Prejet 24. oktober, 2011 Odobren 7. november, 2011 194 VIRANT, KOŠIR virov v ponudbi b�. Prav določanje cene posameznim ponudbam je eden od pomembnih mehanizmov regulacije trga, ki ga je mogoče opraviti s kombinatorično dražbo, kar je tudi razlog za njeno rabo v telekomunikacijah in drugje. Vhodni parametri algoritma za določanje zmagovalca (ang. winner determination algorithm) je množica ponudb skupaj s cenami (�� , ��). Optimizacijska naloga je določitev nekonfliktnih ponudb (kjer je vsak vir prodan največ enkrat), ki maksimizirajo ceno [5], ��� ∑ �� �� � ��� , �. �. max∑ ���|"∈$% ≤ 1, �� ∈ {0,1}. Z binarnimi spremenljivkami �� izbiramo ponudbe tako, da maksimiziramo ceno vseh izbranih ponudb, ki je dana z izrazom ∑ �� �� � ��� , pri čemer upoštevamo (g. n.) omejitev, da je vsak vir lahko prodan največ enkrat (torej x�, ki predstavlja isti vir, se lahko sešteje v največ ena). Rešitev problema kombinatorične dražbe je binarni vektor x = (x�, … , x(), ki podaja izbrane ponudbe. Splošen problem določanja zmagovalca kombinatorične dražbe je NP poln in ga v splošnem ni mogoče rešiti s približkom [6]. Osnovni prijem algoritmov za reševanje kombinatorične dražbe je preiskovanje iskalnih dreves. Pri tem postopek določa sprejemljive podmnožice ponudb, ki zadoščajo pogoju optimizacijske naloge. Ob koncu postopka je rezultat rešitev problema skupaj z dokazom, da je rešitev optimalna. Pri realnih problemih pa je navadno iskalno drevo preveliko, da bi ga bilo mogoče v celoti preiskati. Zato uporabimo postopek razveji in omeji (ang. branch and bound), kar vodi do hitrejšega preiskovanja. Za posebne primere problemov kombinatorične dražbe obstajajo algoritmi s polinomsko časovno zahtevnostjo za iskanje približnih rešitev [5]. Pristop k reševanju »kadarkoli« (ang. any-time) temelji na velikem številu poskusov reševanja s hitrimi slučajnimi algoritmi, pri čemer uporabljamo pametne slučajne sprehode in lahko hitro vodi do dobrih rešitev. Prednost pristopa je v tem, da ga lahko kadarkoli prekinemo in dobimo približek k rešitvi. Slabost pristopa je, da nimamo nobene informacije o kvaliteti približka k rešitvi, ki je lahko vse od zelo dobre do zelo slabe. 3 KOMBINATORIČNA DRAŽBA V TELEKOMUNIKACIJAH Najpogostejša uporaba kombinatorične dražbe na področju telekomunikacij je dodeljevanje komunikacijskih nosilcev (ang. carrier resources). Med drugim so znane uporabe pri dodeljevanju radijskih spektrov za brezžične komunikacije [1] in dodeljevanje OFDM nosilcev [2]. Dodeljevanje radijskih spektrov temelji na reverzni dražbi (ang. reverse auction), ki je NP poln problem, pri čemer algoritem sistematično preišče vse možnosti. Prirejanje OFDM podnosilcev (ang. sub-carrier) temelji na selektivnem preiskovanju iskalnih dreves. Razlog za uporabo kombinatorične dražbe v problemih dodeljevanja oz. prodaje virov v telekomunikacijah je v tem, da je telekomunikacijski trg s tehničnimi in regulatornimi omejitvami zelo kompleksen, hkrati pa ima velik vpliv na razvoj ekonomije in družbe. Postopek kombinatorične dražbe preko mehanizmov oblikovanja ponudb in določanja cen omogoča potrebno regulacijo trga. Kompleksnost telekomunikacijskega trga povečuje tudi udeležba samostojnih povezanih podsistemov kot so uporabniki in ponudniki storitev z zelo raznolikimi in nasprotujočimi interesi. Za zagotovitev ugodnih razmer za razvoj telekomunikacij in posledično povezanih segmentov ekonomije in družbe je ta kompleksen trg potrebno regulirati tudi z dodeljevanjem oziroma prodajo virov. 4 REZULTATI POSKUSOV Postopki reševanja kombinatorične dražbe so večinoma neodvisni od narave problema, ki ga rešujemo. Zato je mogoče brez škode za uporabnost rezultatov merjenja računske in prostorske zahtevnosti za generiranje primerkov optimizacijskih problemov uporabit slučajne generatorje. Da bi omogočili izbiro različnih načrtov poskusov, smo za potrebe predstavljenih meritev uporabili generator problemov kombinatorične dražbe CATS [4]. Na mestu implementacije algoritma za reševanje kombinatorične dražbe, ki temelji na postopku razveji in omeji, smo uporabili paket CASS [4]. Omogoča enostaven nadzor generiranja primerov preko parametrov ukazne vrstice in s tem uporabo testnih skript. Paketa CATS in CASS sta pogosto uporabljana pri raziskavah kombinatorične dražbe. Ker je za izvedbo načrtovanih meritev potrebno izvesti ogromno število reševanj, je uporaba testnih skript edina obvladljiva možnost. Tako veliko število poskusov je potrebno zato, ker testne primerke generiramo slučajno in so območja parametrov problema (npr. število virov) velika. Meritve računske (časovne) in prostorske (spominske) zahtevnosti reševanja kombinatorične dražbe smo opravili na osebnem računalniku. Testne skripte smo pripravili v okolju PowerShell, s katerimi v zanki generiramo testne primere, nadzorujemo reševanje primerov in beležimo izmerjene čase ter porabo spomina. Opravili smo naslednje tipe meritev, rezultate navajamo v nadaljevanju tega poglavja: • Časovna zahtevnost kombinatorične dražbe; • Časovna zahtevnost kombinatorične dražbe za primerke problema enake velikosti; • Časovna zahtevnost kombinatorične dražbe za isti primerek problema; • Prostorska zahtevnost kombinatorične dražbe; ČASOVNA IN PROSTORSKA ZAHTEVNOST KOMBINATORIČNE DRAŽBE V TELEKOMUNIKACIJAH 195 • Prostorska zahtevnost kombinatorične dražbe za primerke problema enake velikosti; • Prostorska zahtevnost kombinatorične dražbe za isti primerek problema; Izbrana pojasnila glede testnih scenarijev in opombe k rezultatom podajamo v nadaljevanju tega poglavja. 4.1 Materiali in metode Meritve smo opravili na osebnem računalniku HP Compaq nx6310 (dvojederni, 2GB RAM) z operacijskim sistemom Windows XP. Pri izvajanju algoritmov nismo uporabili vzporednosti ali virtualnega spomina. Uporabili smo klasičen pristop s testnimi skriptami. Primerke optimizacijskih problemov, njihovo reševanje in beleženje rezultatov smo izvajali avtomatizirano, s čemer smo zagotovili ponovljivost poskusov in nadzor nad merskimi karakteristikami meritev. Primerke kombinatorične dražbe smo generirali s paketom CATS in jih reševali s paketom CASS [4]. Primerke dražb smo generirali z različnimi parametri, jih reševali in pri tem merili čas izvajanja in porabo spomina. Vhodni parametri algoritma so velikost kombinatorične dražbe, ki je dana s številom virov in s številom ponudb. Velikost dražbe smo povečevali dokler čas izvajanja ni presegel 1000 sekund. V praksi navadno ni potrebno zagotoviti izvajanja v realnem ali blizu realnega časa. Tako smo 1000 sekund izbrali kot še sprejemljiv čas reševanja relativno majhnih problemov kombinatorične dražbe. 4.2 Skriptno testiranje Kot smo že nakazali, smo skriptno testiranje uporabili zaradi ponavljanja testov sorodne oblike. Uspešno izvedeno skripto je mogoče v kratkem času preoblikovati za izvajanje sorodnih oblik poskusov. Vse izvajane skripte temeljijo na dveh skriptah, prva služi meritvam časovne, druga pa meritvam prostorske zahtevnosti. 4.3 Meritve časovne in prostorske zahtevnosti Cilj meritev časovne in prostorske zahtevnosti reševanja kombinatorične dražbe je poleg odvisnosti od velikosti problema analizirati še vpliv drugih parametrov na čas izvajanja in poraba spomina kot so različni primerki problemov, nenatančnost merilnega okolja in drugo. Slednje je nujno za oceno ponovljivosti merjenj in zagotavljanje merskih karakteristik. Poleg velikosti primerka dražbe je pomembna verjetnostna porazdelitve virov in ponudb (notranja porazdelitev). Meritve smo opravili pri poljubni porazdelitvi in porazdelitvi L6. Ta ima eksponentno porazdelitev virov in normalno porazdelitev cen. Več o tej in drugih notranjih porazdelitvah kombinatoričnih problemov najdemo v [4]. 4.3.1 Poskus 1: Časovna zahtevnost Ugotovili smo, da na časovno zahtevnost ne vpliva le velikost optimizacijskega problema ampak tudi notranje porazdelitve. Kot kaže slika 1, lahko pri poljubnih notranjih porazdelitvah rešimo le relativno majhne probleme. Glede na dostopne realne podatke o telekomunikacijskih sistemih nimamo možnosti ugotavljanja notranjih porazdelitev problemov kombinatorične dražbe v praksi. Znano je, da lahko realni problemi vključujejo veliko število virov, ne pa tudi veliko število ponudb. To je posledica dejstva, da je zaradi tehničnih, regulatornih in ekonomskih omejitev veliko število sicer mogočih ponudb za realne kupce nesmiselnih. Zato rezultati kot jih kaže slika 1 ne izključujejo uporabe kombinatorične dražbe v realnih problemih, čeprav je zgornja meja števila ponudb pri velikem številu virov že pri okoli 60. Poleg tega je mogoče v praksi veliko število ponudb zmanjšati z uporabo preprostih izključevalnih pravil, ki upoštevajo tehnične in/ali regulatorne omejitve. Po drugi strani pa velja, da uporaba močnejše strojne opreme brez večjih modifikacij implementiranih algoritmov za reševanje (paralelizacija) ne bi bistveno izboljšalo možnosti reševanja. Slika 1: Velikost kombinatorične dražbe ko čas reševanja preseže 1000 sekund, poljubna porazdelitev. Slika 2: Velikost kombinatorične dražbe ko čas reševanja preseže 1000 sekund, porazdelitev L6. Večje primerke kombinatorične dražbe lahko rešimo v primeru, ko uporabimo porazdelitev L6, glejte sliko 2. Število virov enakomerno narašča s številom ponudb, manjši odkloni so posledica naključno generiranih primerkov problemov. 196 VIRANT, KOŠIR Slika 3: Čas reševanja kombinatorične dražbe v odvisnosti od števila virov, porazdelitev L6. Slika 3 prikazuje potek časov reševanja, ki so nelinerani in nakazujejo eksponentno rast. To velja za vse porazdelitve, glejte tudi sliko 4. V praksi to pomeni, da z močnejšo strojno opremo brez posegov v algoritem ne bomo dosegli bistveno boljših rezultatov. Slika 4: Čas reševanja kombinatorične dražbe v odvisnosti od števila virov, poljubna porazdelitev. Poskus2: Časovna zahtevnost dražb enakih velikosti. Analizirali smo čas reševanja kombinatoričnih dražb, ki so različni primerki dražb enakih velikosti. Slika 5 kaže, da med časi reševanja obstajajo velike razlike, kar velja za vse porazdelitve. Slika 5: Čas reševanja kombinatorične dražbe za različne primerke enakih velikosti. Različni časi reševanja so posledica razlik v iskalnih drevesih, po katerih algoritem išče rešitev. 4.3.2 Poskus 3: Časovna zahtevnost reševanja istega primerka dražbe Izmerili smo čase reševanja istega primerka kombinatorične dražbe v več poskusih. Opazili smo manjše razlike, kar je posledica izvajanja drugih procesov na računalniku, glejte sliko 6. Opažanja veljajo za vse porazdelitve. Vendarle menimo, da te razlike bistveno ne vplivajo na meritve, objavljene v tem članku. Slika 6: Čas reševanja kombinatorične dražbe isti primerek 4.3.3 Poskus 4: Prostorska zahtevnost Meritve kažejo, da prostorska zahtevnost (poraba spomina) narašča linearno s številom ponudb, glejte sliko 7, in nelinearno s številom virov, slika 8. Opazimo tudi, da je poraba spomina neodvisna od notranje porazdelitve primerkov z enakim številom ponudb. Na drugi strani je prostorska zahtevnost pri enakem številu virov odvisna od notranje porazdelitve. Slika 7: Poraba spomina pri reševanju kombinatorične dražbe, porazdelitev L6. Slika 8: Poraba spomina pri reševanju kombinatorične dražbe, porazdelitev L6 ČASOVNA IN PROSTORSKA ZAHTEVNOST KOMBINATORIČNE DRAŽBE V TELEKOMUNIKACIJAH 197 Naraščanje porabe spomina v odvisnosti od števila ponudb narašča stabilno, prav tako v odvisnosti od števila virov. Vendarle, do razlage za nepričakovano obnašanje po približno 4500 virov se nismo dokopali. 4.3.4 Poskus 5: Prostorska zahtevnost dražb enake velikosti Izmerili smo porabo spomina pri reševanju različnih primerkov dražb enake velikosti. Podobno kot pri časovni zahtevnosti je tudi poraba spomina odvisna od iskalnih dreves in varira od primerka do primerka dražbe enake velikosti, glejte sliko 9. Trditev velja za vse porazdelitve. Opažene razlike so manjše kot v primeru časovne zahtevnosti. Slika 9: Poraba spomina pri reševanju kombinatorične dražbe za primerek enake velikosti, porazdelitev L6. 4.3.5 Poskus 6: Prostorska zahtevnost istega primerka dražbe Izmerili smo porabo spomina pri večkratnem reševanju istega primerka dražbe. Omembe vrednih razlik nismo opazili, glejte sliko 10, velja za vse porazdelitve. Slika 10: Poraba spomina pri reševanju kombinatorične dražbe za primerek enake velikosti, porazdelitev L6. 4.4 Razprava Kot pričakovano na časovno in prostorsko zahtevnost bistveno vpliva velikost optimizacijskega problema kombinatorične dražbe. Ugotovili smo, da na računsko in prostorsko zahtevnost reševanja problema kombinatorične dražbe poleg parametrov velikosti problema vplivajo tudi notranje porazdelitve virov in ponudb v primerkih dražb. Pri porazdelitvi L6 na računsko in prostorsko zahtevnost bolj vpliva število virov kot število ponudb. Velikost dražbe v smislu števila virov, ki jo je mogoče rešiti na osebnem računalniku, je odvisna od notranje porazdelitve virov in ponudb. Poleg tega smo odkrili, da sta obe zahtevnosti pri enaki velikosti primerka bistveno odvisni od porazdelitev virov in ponudb. Poraba spomina pri reševanju kombinatorične dražbe je odvisna tako od števila virov kot od števila ponudb. Rast je eksponentna s številom virov in približno linearna s številom ponudb. Obe rasti sta neodvisni od porazdelitev virov in dobrin. Obstajajo pa velike razlike pri porabi spomina pri reševanju različnih primerkov dražb enake velikosti. 5 ZAKLJUČEK IN NADALJNJE DELO Na podlagi meritev smo analizirali računsko in prostorsko zahtevnost postopkov za reševanje kombinatorične dražbe. Izmerili smo tudi variacije zahtevnosti za različne primerke dražbe enake velikosti in različne izvedbe istega primerka dražbe z istim postopkom reševanja. Omejili smo se na dve porazdelitvi virov in ponudb, ker smo pri slučajnem generiranju primerkov s paketom CATS za druge porazdelitve naleteli na težave. Ta del uvrščamo v nadaljnje delo. Poleg tega načrtujemo tudi natančnejšo analizo vpliva porazdelitev virov in ponudb na računsko in prostorsko zahtevnost reševanja kombinatorične dražbe.