Naredni sastanak Seminara biće održan u utorak, 27. maja 2025. godine, u Ogranku MI SANU u Novom Sadu sa početkom u 14.15.
Predavač: Nada Mladenović, Fakultet organizacionih nauka Univerziteta u Beogradu
Naslov predavanja: APROKSIMATIVNI (ANYTIME) ALGORITMI ZA GENERISANjE PARETO FRONTA VIŠEKRITERIJUMSKOG PROBLEMA RANCA
Apstrakt: Predlažemo dva pristupa za rešavanje višekriterijumskog 0-1 problema ranca sa višestrukim ograničenjima: jedna matheuristika i jedna konstruktivna heuristika. Za večinu instanci malih dimenzija, naša matheuristika uspešno generiše ceo Pareto front pomenutog problema, dok za ostale, može se dobiti samo aproksimacija nultog reda koja sadrži dobro raspoređene nedominirane tačke Pareto fronta. Za instance velikih dimenzija, i matheuristika i konstruktivna heuristika dobijaju pogodnu aproksimaciju Pareto fronta prvog reda. Inspirisani PESA algoritmom koji je nedavno uveden za rešavanje višekriterijumskih kontinualnih problema, pokušali smo da egzaktno rešimo probleme celobrojne višekriterijumske optimizacije na sličan način, uz korišćenje specifičnosti kombinatornih problema. Za velike instance, gde je potrebna aproksimacija, preuzeli smo iz PESA način određivanja hipotetičkih granica i formulisali heuristike za rešavanje novonastalih jednokriterijumskih problema. Egzaktno smo rešili instance različitih stepena složenosti sa 50 i 100 predmeta. Naši algoritmi su u prihvatljivom vremenu nalazili približna rešenja za instance sa 400, 450 i 500 predmeta.
Izlaganje predstavlja rezultate saradnje sa Bogdanom Stanojević.
Napomena: Predavanja na Seminaru se snimaju i prenose uživo.
Sve informacije mogu se naći na stranici
https://miteam.mi.sanu.ac.rs/asset/qGapAHyEBad2FDwXR
