Solving robust variants of the maximum weighted independent set problem

doctoral thesis

• Title (croatian): Rješavanje robusnih varijanti problema maksimalnog težinskog nezavisnog skupa
• Author: Ana Klobučar
• Mentor: Robert Manger (mentor)
• Committee member: Saša Singer (predsjednik povjerenstva)
• Committee member: Krunoslav Puljić (član povjerenstva)
• Committee member: Robert Manger (član povjerenstva)
• Committee member: Goranka Nogo (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2019-12-16, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics
• Universal decimal classification (UDC): 51 - Mathematics

Abstract

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... More 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. Less

Abstract (croatian)

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... More 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)$ neusmjereni graf, gdje je $V$ skup vrhova, a $E$ skup bridova. Nezavisni skup od $G$ je podskup skupa vrhova $X \subseteq V$ takav da ne postoje dva vrha iz $X$ koja su susjedna (povezana bridom iz $E$). Nadalje, neka je $G=(V,E)$ neusmjereni graf čiji vrhovi imaju cjelobrojne nenegativne težine. Maksimalni težinski nezavisni skup} od $G$ je nezavisni skup od $G$ takav da je zbroj težina vrhova najveći mogući. Problem nalaženja takvog skupa za dani graf se naziva (konvencionalni) problem maksimalnog težinskog nezavisnog skupa (MTNS).Da bismo definirali robusne varijante problema tj. njihova rješenja, prvo uvodimo sljedeće oznake. Označimo sa $S$ skup svih scenarija i pretpostavimo da je svaki scenarij zadan s $n$-torkom uređenih brojeva gdje $n$ predstavlja broj vrhova. Za $X$ proizvoljni nezavisni skup, $F(X,s)$ je vrijednost funkcije cilja konvencionalnog problema za scenarij $s$. Funkcija $F(X,s)$ je jednaka zbroju težina vrhova iz skupa $X$ za scenarij $s$. Nadalje $F^*_s$ je optimalna vrijednost funkcije cilja konvencionalnog problema za scenarij $s$. $\Phi$ je kolekcija svih nezavisnih skupova. Apsolutno robusno rješenje $X_A$ je nezavisni skup čiji je minimum funkcije cilja, mjerene po svim scenarijima, najveći mogući tj. $$\begin{equation*} \text{opt}_A = \max_{X \in \Phi} \min_{s \in S} F(X,s) = \max_{X \in \Phi} F_A(X) = F_A(X_A). \end{equation*}$$ Robusno devijantno rješenje $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. Less

• Keywords: robust optimization; maximum weighted independent set; complexity; approximative algorithms; minimum weighted vertex cover; graphs; trees
• Keywords (croatian): robusna optimizacija; maksimalni težinski nezavisni skup; složenost; približni algoritmi; minimalni težinski vršni pokrivač; grafovi; stabla
• Language: english
• URN:NBN: urn:nbn:hr:217:349720
• Promotion: 2020
• Study programme: Title: Mathematics; Study programme type: university; Study level: postgraduate; Academic / professional title: doktor/doktorica znanosti, područje prirodnih znanosti, polje matematika (doktor/doktorica znanosti, područje prirodnih znanosti, polje matematika)
• Type of resource: Text
• Extent: x, 92 str.
• File origin: Born digital
• Access conditions: Open access; Embargo expiration date: 2022-06-05
• Created on: 2020-06-05 12:18:11