Seminar: Paralelni razveji in omeji algoritem v C z uporabo MPI

Četrtek, 11. februar 2021, 14:00 do 16:00
SLO: Tema seminarja bo paralelni razveji in omeji algoritem, ki ga uporabljamo za reševanje diskretnih problemov iz matematične optimizacije. Predstavljeno bo, kako elemente sekvenčnega algoritma sestavimo v učinkovit porazdeljen paralelni algoritem, ki temelji na MPI. Skalabilnost algoritma bo prikazana na numeričnem primeru iz kombinatorične optimizacije.

V praksi se velikokrat srečamo z reševanjem optimizacijskih problemov, ki imajo končno, vendar znatno število dopustnih rešitev. Veliko število teh problemov, kot sta na primer problem potujočega potnika ali problem največjega prereza, ni moč rešiti z algoritmom s polinomsko časovno zahtevnost. Razveji in omeji je algoritem, ki je največkrat uporabljen za reševanjih takih tipov problemov. Predstavili bomo glavne elemente tega algoritma in pokazali, kako ga uporabimo za iskanje eksaktnih rešitev celoštevilskih optimizacijskih problemov. Za razvoj paralelnega algoritma bo uporabljena shema koordinator – delavci in knjižnica MPI za porazdeljeno računanje. Na numeričnem zgledu bo pokazano kako lahko z uporabo superračunalnika precej zmanjšamo čas računanja sekvenčnega algoritma.

ENG: The topic of this seminar will be the parallel branch and bound algorithm, which is used for solving discrete problems from mathematical optimization. By combining algorithmic ingredients from the serial algorithm we will show how to develop an efficient distributed parallel solver based on MPI. We will use an example problem from the combinatorial optimization to present the scalability results of the algorithm.
In practice, there is a large number of optimization problems which have finite but extensive number of feasible solutions. A significant number of these problems like the traveling salesman problem or max-cut problem can’t be solved in polynomial time. Branch and bound is an algorithm widely used for solving such problems. We will review the most important aspects of this algorithm and show how the method is used for finding exact solutions of integer optimization problems. We will obtain the parallel solver by implementing load coordinator – worker scheme and using message passing interface library (MPI) for multi-node parallelization. Numerical results show how we can considerably reduce the running time of the serial solver by employing HPC.

Organizator/Organizer

SLO: Seminar je dogodek EuroHPC. Organizira ga laboratorij LECAD na Fakulteti za strojništvo Univerze v Ljubljani.

ENG: This Seminar is an EuroHPC event. It is organized by LECAD laboratory at Faculty of Mechanical Engineering, University of Ljubljana, Slovenia.

Predavatelj/About the author

SLO: Timotej Hrga je doktorski študent na Univerzi v Ljubljani, Fakulteti za matematiko in fiziko, ter mladi raziskovalec na Fakulteti za strojništvo. Je glavni razvijalec visokozmogljivih reševalcev MADAM in BiqBin za binarne kvadratične probleme iz področja matematične optimizacije. Sodeluje v nacionalnem kompetenčnem centru HPC, kjer je eden od izobraževalcev. Leta 2020 je bil mentor v programu poletne šole superračunalništva Summer of HPC, ki jo organizira PRACE. Raziskovalno se ukvarja z uporabo semidefinitnega programiranja in visokozmogljivega računalništva v kombinatorični optimizaciji.

ENG: Timotej Hrga is a Ph.D. student at University of Ljubljana, Faculty of mathematics and physics and young researcher at UL FME. He is the main developer of High-Performance distributed solvers MADAM and BiqBin for binary quadratic problems from mathematical optimization. He is involved in EuroCC Competence Center, where he is one of the educators. In year 2020 he was a mentor for PRACE Summer of HPC training. His central topics and main interest is applying semidefinite programming and high-performance computing (HPC) to solve combinatorial optimization problems.

Prijava in povezava do dogodka/Registration and link to the event

Projekt EuroCC je financiran s sredstvi Skupnega podjetja za visoko zmogljivo računalništvo (EuroHPC JU) v skladu s sporazumom o dodelitvi sredstev št. 951732. EuroHPC JU je prejelo finančno podporo iz EU programa Obzorje 2020 ter Nemčije, Bolgarije, Avstrije, Hrvaške, Cipra, Češke , Danske, Estonije, Finske, Grčije, Madžarske, Irske, Italije, Litve, Latvije, Poljske, Portugalske, Romunije, Slovenije, Španije, Švedske, Združenega kraljestva, Francije, Nizozemske, Belgije, Luksemburga, Slovaške, Norveške, Švice, Turčije, Republike Severne Makedonije, Islandije in Črne gore.