Diskretna optimizacija (ili kombinatorna optimizacija) bavi se optimizacijskim problemima gdje su varijable odlučivanja cjelobrojne. Pojedini primjerak problema diskretne optimizacije zadaje se navođenjem točnih vrijednosti parametara koji se pojavljuju unutar njegove funkcije cilja i u njegovim ograničenjima. Te vrijednosti u stvarnom životu obično je teško odrediti budući da one mogu ovisiti o nepredvidivim budućim okolnostima ili se možda ne mogu pouzdano izmjeriti. Tada govorimo o neizvjesnosti (neodređenosti) kod formulacije problema.
Tradicionalna škola optimizacije kakvu susrećemo u udžbenicima u pravilu ignorira neizvjesnost. To znači da se parametrima vrlo često pridružuju približne, nepouzdane ili proizvoljne vrijednosti, što može voditi do nezadovoljavajućih ili čak nedopustivih rješenja. No u novije vrijeme razvio se bolji pristup u izlaženju na kraj sa spomenutom neizvjesnošću koji se naziva robusna optimizacija. U skladu s tim pristupom definira se skup scenarija - svaki od njih zadaje jednu moguću kombinaciju vrijednosti parametara. Promatraju se samo ona rješenja koja su dopustiva za sve scenarije. Na neki se način mjeri ponašanje rješenja ovisno o scenariju. Kao optimalno rješenje u robusnom smislu bira se ono čije je najgore ponašanje, mjereno na cijelom skupu scenarija, najbolje među svim rješenjima.
Posljedica korištenja robusnog pristupa je da se početni optimizacijski problem pretvara u složeniji min-max ili max-min problem. Robusno rješenje ne mora zaista biti optimalno ni za jedan scenarij, no odabrano je tako da bude prihvatljivo čak i pod najgorim scenarijem. Makar se konvencionalne (ne-robusne) varijante nekih problema diskretne optimizacije mogu riješiti u polinomijalnom vremenu, robusne varijante istih problema obično su NP-teške. To znači da pronalaženje efikasnih algoritama za robusne varijante predstavlja zanimljivu istraživačku temu. U ovom trenutku nema baš puno algoritama takve vrste koji bi se mogli smatrati prikladnima za primjene u stvarnom životu.
Cilj ovog projekta je pokazati da se problemi robusne diskretne optimizacije mogu efikasno rješavati makar su NP-teški. Ili preciznije rečeno, cilj je razviti efikasne i u praktičnom smislu upotrebljive algoritme za robusne varijante sljedećih problema diskretne optimizacije: optimalni putovi u grafovima, optimalni tokovi u mrežama, maksimalni težinski nezavisni skupovi, trgovački putnik i slični problemi. Promatrat će se varijante gdje je skup scenarija konačan i eksplicitno zadan. Naglasak će biti na heurističkim ili meta-heurističkim rješenjima, a ne na egzaktnim rješenjima.
Svaki od razvijenih algoritama analizirat će se sa stanovišta korektnosti, preciznosti odnosno vremenske složenosti. Također, algoritmi će se implementirati kao softver, vrednovati na velikim primjercima problema te učiniti dostupnima drugim istraživačima preko repozitorija na webu. Postignuti rezultati dokumentirat će se u znanstvenim člancima i objaviti u odgovarajućim časopisima. Također se očekuje da će najmlađa članica projektnog tima izraditi i obraniti svoju doktorsku disertaciju.
