Naslov Solving robust variants of the maximum weighted independent set problem Naslov (hrvatski) Rješavanje robusnih varijanti problema maksimalnog težinskog nezavisnog skupa Autor Ana Klobučar Mentor Robert Manger (mentor)Član povjerenstva Saša Singer (predsjednik povjerenstva)Član povjerenstva Krunoslav Puljić (član povjerenstva)Član povjerenstva Robert Manger (član povjerenstva)Član povjerenstva Goranka Nogo (član povjerenstva)Ustanova koja je dodijelila Sveučilište u Zagrebu Datum i država obrane 2019-12-16, Hrvatska Znanstveno / umjetničko PRIRODNE ZNANOSTI Univerzalna decimalna klasifikacijaUDC ) 51 - Matematika Sažetak This work is concerned with robust variants of the maximum weighted independent set problem (MWIS problem). Three basic robustness criteria are used, i.e. absolute robustness, robust deviation and relative robust deviation. More general ordered weighted averaging criteria (OWA) are also considered. Problems are posed in a graph whose vertices are given weights. Uncertainty in vertex weights is expressed through a finite collection of explicitly given scenarios or by intervals. First we explore
... Više relationship between robust variants of our problem and robust variants of minimum weighted vertex cover problem (MWVC). In more detail, we explore whether the complement of a robustly optimal independent set must be a robustly optimal vertex cover, and vice-versa (as it is true for conventional optima). It turns out that the answer to this question is not straightforward. More precisely, the answer depends on the chosen criterion of robustness. Further, since solving the conventional MWIS problem is already NP-hard, finding the exact solution of its robust counterpart obviously cannot be any easier. Therefore, we propose an approximate algorithm for solving the considered robust variants, which is based on evolutionary computing and on various crossover and mutation operators. The algorithm is experimentally evaluated on appropriate problem instances. It is shown that satisfactory solutions can be obtained for the mentioned robust robustness criteria in reasonable time. Finally, we explore complexity of our robust variants on trees. It is well known that the conventional MWIS problem can be solved in polynomial time on trees. However, it turns out that almost all robust variants are NP-hard. Hence, we propose an approximative algorithm specially designed for trees which takes into consideration their special structure. More precisely, the algorithm combines good features from dynamic programming, evolutionary computing and greedy decision making. Again, the algorithm is experimentally evaluated on appropriate problem instances. It is shown that satisfactory solutions can be obtained for any of the three basic robustness criteria in reasonable time. Sakrij dio sažetka Sažetak (hrvatski) Konvencionalna optimizacija podrazumijeva maksimiziranje ili minimiziranje funkcije cilja nad danim skupom dopustivih rješenja koja zadovoljavaju određena ograničenja. Međutim, u stvarnim situacijama, ulazni podaci su često nepoznati i podložni promjenama. Suvremena metoda za rad s takvim nesigurnostima se zove robusna optimizacija. Ovaj rad se bavi robusnim varijantama problema maksimalnog težinskog nezavisnog skupa (problem MTNS). Koriste se tri osnovna kriterija robusnosti: apsolutna
... Više robusnost, robusna devijacija te relativna robusna devijacija. Također se promatraju i općenitiji OWA kriteriji. Nesigurnost u pogledu težina vrhova izražena je preko eksplicitnog skupa scenarija ili pomoću intervala. Neka je G = ( V , E ) V E G X ⊆ V X E G = ( V , E ) G G S n n X F ( X , s ) s F ( X , s ) X s F ∗ s s Φ X A opt A = max X_D je nezavisni skup čije je maksimalno odstupanje od konvencionalnog optimuma, mjerenog po svim scenarijima, najmanje moguće tj. \begin{equation*} \text{opt}_D= \min_{X \in \Phi} \max_{s \in S} \Big( F^*_s - F(X,s) \Big) = \min_{X \in \Phi} F_D(X) = F_D(X_D). \end{equation*} Relativno robusno devijantno rješenje X_R je nezavisni skup čije je maksimalno relativno odstupanje od konvencionalnog optimuma, mjerenog po svim scenarijima, najmanje moguće tj. \begin{equation*} \text{opt}_R= \min_{X \in \Phi} \max_{s \in S} \Big((F^*_s - F(X,s))/F^*_s \Big) = \min_{X \in \Phi} F_R(X) = F_R(X_R). \end{equation*} OWA kriteriji su generalizacija navedenih kriterija. Primjerice, OWA_A se definira na sljedeći način. Za odabrano rješenje X pripadne vrijednosti funkcije cilja F(X,s) sortiramo uzlazno: \begin{equation*} F(X,s_{\sigma(1)}) \leq F(X,s_{\sigma(2)}) \leq \ldots \leq F(X,s_{\sigma(p)}), \end{equation*} \sigma je permutacija. Tada se OWA_A cijena za X računa: O_A(X) = \sum_{i=1}^p a_i\cdot F(X,s_{\sigma(i)}) . OWA_A rješenje X_{OA} je nezavisni skup koje maksimizira funkciju O_A(X) na skupu svih mogućih rješenja tj. \begin{equation*} \text{opt}_{OA} =O_A(X_{OA}) =\max_{X \in \Phi} O_A(X). \end{equation*} U radu prvo istražujemo odnos između robusnih varijanti našeg problema i robusnih varijanti problema minimalnog težinskog vršnog pokrivača (problem MTVP). Definirajmo problem MTVP. Neka je G=(V,E) neusmjereni graf, gdje je V skup vrhova, a E skup bridova. Vršni pokrivač od G je podskup skupa vrhova Y \subseteq V takav da je svaki brid iz E incidentan s barem jednim vrhom iz Y . Neka je G=(V,E) neusmjereni graf čiji vrhovi imaju cjelobrojne nenegativne težine. Minimalni težinski vršni pokrivač od G je vršni pokrivač od G takav da je zbroj težina vrhova najmanji mogući. Problem nalaženja takvog skupa za dani graf se naziva (konvencionalni) problem minimalnog težinskog vršnog pokrivača (MTVP). Istražujemo je li komplement robusno optimalnog nezavisnog skupa robusno optimalni vršni pokrivač i obratno (kao što vrijedi za konvencionalne optimume). Pokazuje se da odgovor na to pitanje nije trivijalan. Točnije, odgovor ovisi o odabranom kriteriju robusnosti. Komplement robusnog devijantnog rješenja problema MTNS je robusno devijantno rješenje problema MTVP i obratno. Za ostale kriterije ne vrijedi ekvivalencija osim u nekim specijalnim slučajevima. Potom se bavimo rješavanjem robusnih varijanti problema MTNS na običnim grafovima. Kako je rješavanje konvencionalnog problema MTNS već NP-teško, nalaženje egzaktnog rješenja njegove robusne varijante neće biti ništa lakše. Stoga predlažemo približni algoritam za rješavanje spomenutih robusnih varijanti koji se temelji na evolucijskom računanju i na kolekciji različitih operatora križanja i mutacija. Navedeni algoritam je eksperimentalno testiran na odgovarajućim instancama problema. Pokazuje se da je moguće postići zadovoljavajuća rješenja u prihvatljivom vremenu. Konačno, istražujemo složenost navedenih robusnih varijanti na stablima. Poznato je da je konvencionalni problem MTNS na stablima rješiv u polinomijalnom vremenu. Nažalost, pokazuje se da su gotovo sve robusne varijante NP teške. Stoga predlažemo približni algoritam dizajniran specijalno za stabla koji uzima u obzir njihovu specifičnu strukturu. Detaljnije, algoritam kombinira dobre osobine dinamičkog programiranja, evolucijskog računanja i pohlepnog odlučivanja. Navedeni algoritam je također eksperimentalno testiran na odgovarajućim instancama problema. Opet se pokazuje da je moguće postići zadovoljavajuća rješenja u prihvatljivom vremenu. Sakrij dio sažetka Ključne riječi
robust optimization
maximum weighted independent set
complexity
approximative algorithms
minimum weighted vertex cover
graphs
trees
Ključne riječi (hrvatski)
robusna optimizacija
maksimalni težinski nezavisni skup
složenost
približni algoritmi
minimalni težinski vršni pokrivač
grafovi
stabla
Jezik engleski URN:NBN urn:nbn:hr:217:349720 Datum promocije 2020 Studijski program Naziv: Matematika Vrsta resursa Tekst Opseg x, 92 str. Način izrade datoteke Izvorno digitalna Prava pristupa Otvoreni pristup Uvjeti korištenja Datum i vrijeme pohrane 2020-06-05 12:18:11
