Odeljenje za matematiku, 27. novembar 2020.

• 23. Novembar,  2020
• Komentari (0)

Naredni sastanak Seminara biće održan u petak, 27. novembra 2020, u sali 301f Matematičkog instituta SANU sa početkom u 14:15.

Predavač: Tanja Davidović, Matematički institut SANU

Naslov predavanja: MATHEURISTIKE-HIBRIDI IZMEĐU METAHEURISTIČKIH I EGZAKTNIH METODA

Apstrakt:
Problemi optimizacije se obično formulišu u obliku mešovitih celobrojnih programa (Mixed Integer Programs, MIP) i rešavaju se različitim egzaktnim rešavačima (CPLEX, Gurobi, itd.). Međutim, za većinu realnih instanci problema egzaktne metode zahtevaju previše vremena i memorije, pa se obično umesto njih primenjuju metaheuristike. One predstavljaju uopštene algoritme za optimizaciju date ciljne funkcije iterativnim generisanjem novih ili poboljšanjem postojećih rešenja. Uopštenost podrazumeva da se u opisu metaheurističkog algoritma ne koriste apriori znanja o konkretnom problemu optimizacije, već se oni definišu kao skup koraka (recept) o tome kako treba manipulisati rešenjima problema u cilju dobijanja što kvalitetnijih konačnih rezultata. Samim tim omogućena je primena ovih metoda na različite optimizacione probleme, ali je njihova velika mana što ne mogu da garantuju kvalitet konačnih rešenja. Među uopštenim heuristikama, posebno mesto zauzimaju 0-1  MIP metode, tzv. matheuristike. Ove metode su hibridi između metaheurističkih metoda i egzaktnih rešavača za MIP probleme. Glavna ideja koja se krije iza ove hibridizacije je dekompozicija polaznog problema tako što se upotrebom metaheurističkih pravila generišu potproblemi koji se onda rešavaju egzaktnim rešavačem. U okviru predavanja detaljno će biti prikazane tri metode iz literature kod kojih se kao metaheuristika koristi metoda promenljivih okolina (ili njene varijacije). To su grananje kroz promenljive okoline (Variable Neighborhood Branching, VNB), metoda promenljivih okolina sa dekompozicijom za 0-1 MIP (Variable Neighborhood Decomposition Search for 0-1 MIP, VNDS-MIP) i metoda pretrage okolina promenljivim intenzitetom (Variable Intensity Neighborhood Search, VINS). Najvažnija osobina matheuristika je što se, pod određenim uslovima, mogu smatrati egzaktnim metodama.

---