Sveikiname naująjį gamtos mokslų srities informatikos mokslų krypties daktarą Mindaugą Kepalą sėkmingai apgynus disertaciją pavadinimu „Globaliojo sprendinio paieška vietos parinkimo uždaviniams su apribojimais“ (angl. – Searching for the Global Solution of Constrained Location Problems).
Dr. Mindaugas Kepalas ir mokslinis darbo vadovas prof. dr. Julius Žilinskas
Mindaugo Kepalo disertacija galėtų sudominti tyrėjus ir praktikus, kurie sprendžia infrastruktūros planavimo, statybų inžinerijos ir kitus uždavinius, kur reikia optimalaus objektų išdėstymo.
Disertacijoje nagrinėjami plokštumos vietų su apribojimais parinkimo uždaviniai, kurių tikslas – rasti optimalų taškų išdėstymą duotame plokštumos poaibyje, pavyzdžiui, tinkle. Tyrime analizuojami trys pagrindiniai matematiniai modeliai: vienodo ploto Voronojaus mozaikos uždavinys su tinklo ribojimu, klasterizavimas su tinklo ribojimu klasterių centrams bei multi-Weberio uždavinys su barjerais. Pirmieji du modeliai mokslinėje literatūroje iki šiol nebuvo nagrinėti ir pirmąkart sprendžiami darbe, o trečiajam pirmąkart rasti globalūs sprendiniai tam tikriems uždavinio atvejams.
Vienodo ploto Voronojaus mozaikos uždaviniui su tinklo ribojimu centrams disertacijoje pasiūlytas iteracinis algoritmas. Sprendžiant uždavinį, naudojamasi klasikiniais matematinės analizės ir optimizavimo rezultatais. Pavyzdžiui, formuluojant tarpinį uždavinį, daugiamatė funkcija yra aproksimuojama Teiloro eilute, o absoliučių skirtumų minimizavimui suformuluojamas tiesinio programavimo uždavinys. Disertacijoje pasiūlytas algoritmas leidžia rasti ,,geros kokybės“ sprendinius nagrinėjamam uždaviniui.
Mažiausių kvadratų klasterizavimo uždavinio su tinklo ribojimu globaliam sprendimui pasiūlytas šakų ir rėžių (branch and bound) algoritmas su iškilojo apvalkalo šakų kirpimo kriterijumi. Nors kriterijus labai paprastas – tiesiog pasinaudota pastebėjimu, kad apibrėžus klasterius ir paskaičiavus jų iškiluosius apvalkalus, šie privalo nesikirsti optimaliam sprendiniui, – tačiau šis paprastas kriterijus leido didžiausią nagrinėtą uždavinį išspręsti per valandą, kai palyginimui atlikti tyrimai parodė, kad naudojantis komerciniu bendro pobūdžio sveikaskaitinio optimizavimo įrankiu šį uždavinį išspręsti būtų užtrukę ilgiau nei metus!
O štai sprendžiant multi-Weberio uždavinį su barjerais naujajam daktarui prireikė skaičiuojamosios geometrijos ir klasikinių algoritmų žinių. Pavyzdžiui, reikėjo mokėti suskaičiuoti dviejų daugiakampių bendrą susikirtimo plotą, o skaičiuojant apatinį rėžį, pasinaudota klasikiniu Dijkstros trumpiausio kelio algoritmu. Nors savo esme ir nesudėtingas, disertacijoje pasiūlytas algoritmas leido rasti globalų sprendinį tam tikriems uždavinio atvejams, kuriems globalus sprendinys literatūroje iki šiol nebuvo prieinamas.
Pagrindinis darbo naujumas yra tai, kad nagrinėjami plokštumos vietų parinkimo modeliai, kuriems yra duoti arba nurodyti neiškilūs ribojimai. Tokie ribojimai turi natūralią interpretaciją. Pavyzdžiui, matematinis tinklo modelis galėtų atitikti kelius arba elektros linijas žemėlapyje, o barjerus galėtų atitikti pastatai, ežerai, miškai ir pan. Vis dėlto šis ribojimų aibės neiškilumas uždavinius, kurie ir be tokio ribojimo yra nelengvi, padaro dar sunkesnius (tačiau, kaip sako pats disertantas, ir įdomiais!).
Darbas rengtas 2020–2025 metais Vilniaus universiteto Matematikos ir informatikos fakultete.
Mokslinis vadovas – prof. dr. Julius Žilinskas.
Disertacijos gynimo taryba:
akademikė prof. dr. Olga Kurasova – tarybos pirmininkė (VU),
doc. dr. Algirdas Lančinskas (VU),
prof. dr. Audris Mockus (Tenesio universitetas, JAV),
prof. dr. Remigijus Paulavičius (VU),
prof. dr. Dmitrij Šešok (Vilniaus Gedimino technikos universitetas).
2026 04 01