Seminar za računarstvo i primenjenu matematiku, 29. mart 2016.

• 28. Mart,  2016
• Komentari (0)

Naredni sastanak Seminara biće održan u utorak, 29. marta 2016. u sali 301f Matematičkog instituta SANU sa početkom u 14:15 časova.

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

Naslov predavanja: MATHEURISTIKA VINS

Apstrakt: Razvijena je nova matheuristika, heuristička optimizaciona metoda, dobijena hibridizacijom egzaktnog MIP solvera sa procedurom lokalne pretrage kroz različite okoline. Ova metoda koristi ideju za fiksiranje podskupa binarnih promenljivih i korišćenje egzaktnog solvera za rešavanje dobijenog potproblema, tj. određivanje vrednosti za preostale (nefiksirane) promenljive. Koje promenljive i koliko njih će se fiksirati određuje se na razne načine i time se definišu razne okoline za pretragu. Eksperimentisano je sa 10 tipova okolina. Veličine okolina se sistematski povećavaju, a u skladu sa tim, povećava se i vreme dozvoljeno za rad egzaktnog solvera. Time se povećava intenzitet pretrage u odgovarajućoj okolini. Promena okolina, kao i intenziteta pretrage inspiracija su za ime nove metode: Variable Intensity Neighborhood Search (VINS). Metoda je nastala kombinovanjem ideja iz dve poznate matheuristike: Variable Intensity Local Search (VILS) i Variable Neighborhood Decomposition Search for 0-1 MIP (VNDS-MIP). Eksperimentalana evaluacija izvršena je na dva skupa test primera benčmark instanci iz MIPLIB 3.0 biblioteke i realnim primerima rutiranja kontejnerskih brodova u rečnoj plovidbi. Predložena metoda poređena je sa VNDS-MIP metodom i pokazano je da VINS najčešće daje bolje rezultate od svog prethodnika, bilo po kvalitetu rešenja, bilo po vremenu izvršavanja, a nekad i po oba kriterijuma.

Rezultati su dobijeni u saradnji sa P. Jovanovićem, J. Lazić i S. Mitrović Minić.

---