Raziskovalni projekti so (so)financirani s strani Javne agencije za raziskovalno dejavnost

 

https://www.fs.uni-lj.si/wp-content/uploads/2022/08/Screenshot-2022-08-10-at-11.26.47-e1660123721587.png

  • Članica UL: UL Fakulteta za strojništvo
  • Šifra projekta: N1-0071
  • Naslov: Razširitev algoritmov prvega in drugega reda za izbrane razrede optimizacijskih problemov s ciljem rešiti računsko zahtevne industrijske probleme
  • Trajanje: 01.01.2018 – 31.12.2020
  • Letni obseg: 0,59 FTE
  • Vodja: izr. prof. dr. Janez Povh
  • Veda: Naravoslovje
  • Sestava projektne skupine: Povezava
  • Bibliografske reference: Povezava

Vsebinski opis projekta

Ta projekt je skupni slovensko-madžarski prpjekt, kjer je delo dobro razdeljeno med madžarski in slovenski del projektne ekipe, ki se srečujeta 2-3 krat letno na skupnih delavnicah, ostalo delo pa poteka na daljavo.

V projektu smo razvili nove metode za reševanje več-linearnih optimizacijskih problemov in jih uporabili pri reševanju nekaterih pomembnih optimizacijskih problemov iz realnega, tudi industrijskega okolja: problem iskanja ekonomskega ravnotežja (EEP), problem združevanja (PP) in problem nenegativnega matričnega razcepa (NMFP). Vsi ti optimizacijski problemi spadajo v razred NP-polnih problemov, za katere algoritmi s polinomsko zahtevnostjo ne obstajajo, razen če drži P = NP.

Za reševanje smo uporabili najboljše obstoječe algoritme ter razvili nekaj novih , ki smo jih tudi implementirali v okolju Matlab in C ter jih prilagodili za izvajanje na superračunalnikih.

Skupna značilnosti teh optimizacijskih problemov je, da nekonveksnost prihaja iz zmnožkov različnih odločitvenih spremenljivk tako v kriterijski funkciji kot v dopustni množici. Za reševanje smo uporabili obstoječe reševalce za splošne nelinearne probleme kot npr. Baron, ki pa so bili uporabni le za probleme manjših dimenzij in so generirali referenčne izračune.

Naše metode, ki smo jih razvili in implementirali, so hibridne narave: združujejo elemente natančnih algoritmov prvega in drugega reda: tehnike lokalnega iskanja, meta-hevristike in hevristike, ki temeljijo na strukturnih lastnostih problemov. Paralelizacija kod je omogočila, da te metode izvajamo na superračunalniku na UL FS.

Faze projekta in njihova realizacija

Projekt je bil razdeljen v 5 delovnih sklopov z mnogimi nalogami.

DS1: Projektno vodenje: to je sklop aktivnosti, ki so potekale več čas in so rezultirale v usklajenem delovanju obeh delov projektne ekipe in v usklajeni komunikaciji z obema agencijama.

DS2: Problem ekonomskega ravnovesja (PER)

Ta delovni sklop je vodil madžarski del ekipe. Delo je vključevalo:

– raziskovanje lastnosti različnih matričnih razredov, še posebej tistih, ki generirajo t.i. P matrike in zadostne matrike.

– razvoj in implementacija novih metod notranjih točk (MNT) za probleme linearne komplementarnosti in za probleme prepoznavanja zadostnih matrik.

– uporaba metod globalne optimizavcije za reševanje splošnih problemov linearne komplementarnosti (PLK)

Najpomembnejši rezultati so bili objavljeni v

– SIAM journal on optimization: https://epubs.siam.org/doi/abs/10.1137/19M1248972

– CEJOR: https://link.springer.com/article/10.1007/s10100-021-00747-4

DS3: Mešalni problem in posplošitve

ULFS je vključen v

– reševanje mešalnih problemov

– uvajanje dualnih problemov za bilinearno optimizacijo

V sklopu tega dela smo razvili posplošen Petford Welsh algoritem za gručenje, ki deluje kot dualna operacija za barvanje grafa. Rezultati so bili objavljeni v Computational and applied mathematics https://link.springer.com/article/10.1007/s40314-022-01835-0

DS4: Reševanje problemov nenegativne matrične fakorizacije 

Ta sklop je vodila ekipa ULFS: V sklopu tega sklopa smo naredili:

– razvili smo nove algoritme za reševanje problema dvofaktorske nenegativne matrične faktorizacije. Rezultati so objavljeni v MDPI Mathematics https://www.mdpi.com/2227-7390/9/5/540

– razvili smo nove algoritme za reševanje problema trofaktorske nenegativne matrične faktorizacije. Rezultati so objavljeni Journal on Global Optimization v https://link.springer.com/article/10.1007/s10898-021-01074-3.

– razvili smo posebne algoritme za simertično trofaktorsko nnegativno matrično faktorizacijo in jih uporabili pri napredni analizi podatkov o rakavih obolenjih. Rezultati so objavljeni v Nature Communications: https://www.nature.com/articles/s41467-019-08797-8

DS5: Diseminacija

Poleg objavljenih člankov smo rezultate predstavili na različnih mednarodnih konferencah, kot so ISMP, EURO, SOR, KOI, VOCAL

Pojdi na vsebino