Domov > Obvestila > Timotej Hrga: Uporaba visokozmogljivega računalništva pri izračunu neodvisnega števila grafa

Timotej Hrga: Uporaba visokozmogljivega računalništva pri izračunu neodvisnega števila grafa

Datum objave: 16. 11. 2018
Vir: Seminar za numerično analizo
Sreda, 21.11.2018, od 10h do 11h, soba 3.06 na Jadranski 21
Na seminarju bo predstavljen eksaktni algoritem za izračun neodvisnega (stabilnega) števila grafa, ki temelji na metodi razveji in omeji (B&B). Gre za problem iz kombinatorične optimizacije, kjer iščemo stabilno množico v grafu z največjo kardinalnostjo. Algoritem združuje tehnike iz semidefinitnega programiranja (SDP) in visokozmogljivega računalništva (HPC). Preiskovalno drevo B&B algoritma pregledujemo paralelno, pri čemer v vsakem vozlišču rešimo SDP relaksacijo problema za določitev zgornje meje optimalne vrednosti originalnega problema. Gostota danega grafa določa izbiro algoritma za reševanje dobljenega semidefinitnega programa. Rezultat je odprto dostopni visokozmogljiv reševalec BiqBin.

Gre za skupno delo z Univerzo v Celovcu (AAU Klagenfurt).