General information
Kurs se realizuje u toku prolećnog semestra 2016/2017. godine.Studenti koji su slušali ove kurseve u toku 2015/2016. godine, uradili su domaći zadatak, a nisu odbranili seminarski rad, mogu nastaviti sa izradom seminarskog rada koji su dobili prošle godine (domaći zadatak u CPLEX-u će biti priznat).
Plan kursa
1. Osnove matematičkog modeliranja.
2. Simpleks metod
3. Lagranžova relaksacija
4. Metoda grananja i ograničavanja.
5. Metoda odsecanja ravni.Metoda grananja i sečenja
6. Egzaktni rešavači (CPLEX, LINGO, korišćenje AMPL-a)
7. Heurističke i metaheurističke metode
(osnovni pojmovi, osobine, klasifikacija)
8. Optimizacija metodom kolonije pčela
9. Genetski algoritmi, osnovni i napredni koncepti
10. Metoda roja čestica
11. Mravlje kolonije
12. Lokalno pretraživanje i varijante
13. Simulirano kaljenje
14. Tabu pretraživanje
15. Metoda promenljivih okolina i varijante
16. Hibridizacija metoda optimizacije.
Matheuristike. Hibridne metaheuristike.
Literatura
1. R.J. Vanderbei: "Linear Programming - Foundations and Extensions", Princeton, NY, 2000.
2. F. Glover, G.A. Kochenberger: "Handbook of Metaheuristics", Kluwer Academic Press, 2003.
3. E. G. Talbi: "Metaheuristics", J.W. and Sons Pubilcations, Wiley, 2009.
Način bodovanja ispita i predispitnih obaveza
Predispitne obaveze:
Implementacija problema u CPLEX-u, max 30 poena
Student na predispitnim obavezama mora osvojiti najmanje 16 poena da bi pristupio završnom ispitu.
Zavrsni ispit:
Odbrana seminarskog rada
Usmeni deo
max 70 poena (u zbiru)
Student na završnom ispitu mora osvojiti najmanje 35 poena.
Student je položio ispit ukoliko na predispitnim obavezama i završnom ispitu osvoji najmanje 51 poen.
Simpleks metod i ostale metode LP
Knjiga o Linearnom programiranju i prateći slajdovi mogu se naći na sledećoj WEB STRANI.
CPLEX solver
U okviru kursa bice obrađen CPLEX solver koji se koristi na univerzitetima širom sveta za rešavanje brojnih optimizacionih problema. Svaki student dobija jedan konkretan problem koji će rešiti korišćenjem solvera CPLEX. Može se koristiti bilo koja verzija CPLEX-a od 12.1 naviše.
CPLEX i AMPL
CPLEX i AMPL prezentacija Tanje Davidović, MI SANU
LINGO solver
CPLEX primeri
Primeri problema u CPLEX-u
CPLEX prezentacija sa primerima USAHLP i LTCFLP
Uncapacitated Single Allocation Hub Location Problem (sa komentarima u kodu)
Long-term Care Facility Location Problem (sa komentarima u kodu)
Long-term Care Facility Location Problem-1(verzija bez komentara)
Izvrsne verzije CPLEX-a za navedene probleme mogu se preuzeti sa strane
http://poincare.matf.bg.ac.rs/~zoricast/Zorica/
CPLEX i AMPL prezentacija Tanje Davidović, MI SANU
Uputstvo za izradu domaćeg zadatka u CPLEX-u
Izrada domaćeg zadatka je predispitna obaveza.
Zadatak treba poslati mailom na stefan@matf.bg.ac.rs i zoricast@matf.bg.ac.rs . Rok za predaju domaćeg zadatka i termin odbrane će biti naknadno objavljeni.
Mail treba da sadrži pdf dokument u kome treba navesti
- Ime i prezime, broj indeksa, broj zadatka
- matematičku formulaciju problema
- opis problema (značenje funkcije cilja i uslova)
- instance koje su korišćene, opis instanci i primer jedne (manje instance)
- ako ste instance sami kreirali, opisati način kako su generisane, uz prateće obrazloženje
- rezultate CPLEX-a na svakoj instanci koji sadrže: optimalno rešenje (ako postoji), vreme izvršavanja, broj iteracija, broj čvorova. Rezulatate smestiti u tabelu.
- vreme izvršavanja CPLEX-a ograničiti na 4h. U tim slučajevima ispisati rešenje koje je CPLEX do tada dobio, sa naznakom da rešenje nije optimalno
- ako nema dopustivog rešenja i to naznačiti. Ne bi trebalo generisati instance koje su u većem broju nedopustive (takvih instanci može biti najviše 5 %)
- instance bi trebalo grupisati u 3 dela: instance manjih, srednjih i većih dimenzija (najmanje 20 instanci u svakoj grupi). Koja su tačno dimenizije za manje, srednje i veće instance, to zavisi od konkretnog problema
- kratak komentar i analiza dobijenih rezultata
- na kraju navesti link na stranu na kome može da se skine izvršna verzija zadatka u CPLEX-a i kod programa.
Za sva pitanja možete se obratiti mailom ili na konsultacijama!
Primeri domaćih zadataka:
CPLEX i seminarski radovi
Student pristupa izradi seminarskog rada nakon izrade i odbrane domaćeg zadatka korišćenjem CPLEX solvera (predispitna obaveza). Rok za predaju domaćeg zadatka je 10. januar 2016, a odbrana će biti organizovana u periodu 19-22. januara 2016.
Seminarski rad zamenjuje pismeni ispit, te ga je moguće odbraniti u bilo kom ispitnom roku (ili ranije, kada ga student završi seminarski).
U okvuru seminarskog rada, problem koji je student već rešavao CPLEX-om u domaćem zadatku, sada treba rešiti implementacijom dve heurističke metode (svake zasebno), kao i njihovom hibridizacijom. Heurističke metode se dobijaju istovremeno sa problemom. Dobijene rezultate (svake od heuristika i njihove hibridizacije) uporediti sa optimalnim resenjima dobijenim pomoću CPLEX solvera.
Seminarski rad treba da sadrži sledeće elemente:
1. Naslov, ime i prezime studenta, broj indeksa
2. Abstrakt i ključne reči,
3. Opis problema i matematička formulacija, potencijalne oblasti primene,
4. Opis heuristike 1,
5. Opis heuristike 2,
6. Opis načina hibridizacije heuristika 1 i 2,
7. Rezultati testiranja, analiza rezultata i poređenja,
8. Zaključak,
9. Reference
Test primeri za neki od problema se mogu naći na
http://people.brunel.ac.uk/~mastjjb/jeb/info.html
Ukoliko test instance za problem nisu dostupne, mogu se modifikovati postojeće ili generisati nove. U tom slučaju, potrebno je opisati postupak modifikacije, odnosno generisanja instanci.
Uputstvo za izvestaje testiranja metaheuristika
Napomena: Neki seminarski radovi imaju samo 1 metodu zbog njene kompleksnosti
Primer seminarskog rada 2(prateći pdf) Kod seminarskog 2
Metaheuristike
Prezentacije:
Evolutivni algoritmi + primeri
Heuristike zasnovane na lokalnom pretraživanju (LS, ILS, SA, TS, VNS)
VNS, Matheuristike-Tanja Davidović, MI SANU
Dodatak:
Matheuristike-Jasmina Lazic-PhD
Literatura za metaheuristike:
1. Ribeirio C .C., Hansen P., Essays and survays in Metaheuristics,
Kluwer Academic Publishers Boston - Dordrecht - London (2002).
2. Glover F., Kochenberger G.A., Handbook of Metaheuristics,
Kluwer Academic Publishers,Boston Dordrecht-London (2003).
3. Michalewitz Z., Fogel D.B., How to solve it: modern metaheuristics, Springer (1999)
4. Osman I.H., Kelly J.P., Metaheuristics: Theory and Applications,
Kluwer Academic Publishers, Norwell (1996).
5. Talbi, E.G. "Metaheuristics-from design to implementation", Wiley & Sons Publications, 2009.
Seminarski radovi
Student pristupa izradi seminarskog rada nakon izrade i odbrane domaćeg zadatka korišćenjem CPLEX solvera (predispitna obaveza). Seminarski rad zamenjuje pismeni ispit, te ga je moguće odbraniti u bilo kom ispitnom roku (ili ranije, kada ga student završi).
Problem iz domaćeg zadatka treba rešiti implementacijom dve heurističke metode (svake zasebno), kao i njihovom hibridizacijom. Heurističke metode se dobijaju istovremeno sa problemom. Dobijene rezultate (svake od heuristika i njihove hibridizacije) uporediti sa optimalnim rešenjima dobijenim pomoću CPLEX solvera.
Seminarski rad treba da sadrži sledeće elemente:
1. Naslov, ime i prezime studenta, broj indeksa
2. Apstrakt i ključne reči,
3. Opis problema i matematička formulacija, potencijalne oblasti primene, postojeći načini rešavanja problema,
4. Opis heuristike 1,
5. Opis heuristike 2,
6. Opis načina hibridizacije heuristika 1 i 2,
7. Rezultati testiranja, analiza rezultata i poređenja (pogledati način izrade izveštaja),
8. Zaključak,
9. Spisak korišćene literature (reference).
Test primeri za neki od problema se mogu naći na
http://people.brunel.ac.uk/~mastjjb/jeb/info.html
Ukoliko test instance za problem nisu dostupne, mogu se modifikovati postojeće ili generisati nove. U tom slučaju, potrebno je opisati postupak modifikacije, odnosno generisanja instanci.
Uputstvo za izvestaje testiranja metaheuristika
Uputstvo za navođenje literature i pozive u tekstu
Neophodne radove za uvodni deo potražiti na Kobson-u.
Kobson
Šta je KOBSON?
KONBSON je Konzorcijum biblioteka Srbije za objedinjenu nabavku - novi oblik organizovanja biblioteka Srbije. Inicijativu za formiranje Konzorcijuma su pokrenule novembra 2001. vodeće naučne biblioteke u Srbiji.
Osnovni ciljevi KOBSON-a su:
- optimizovana nabavka stranih naučnih informacija
- prelazak sa papirnih izdanja na elektronska
- unapređenje pristupa elektronskim informacijama
- promocija domaćeg naučnog izdavaštva
http://kobson.nb.rs
Šta sve KoBSON radi?
-
obezbeđuje novčana sredstva za nabavku naučnih informacija, promociju ili edukaciju, putem projekata u zemlji i inostranstvu
-
upravlja pribavljenim novčanim sredstvima
-
odlučuje o nabavci naučnih informacija, nakon anketiranja svih zainteresovanih članica i detaljne analize
-
pregovara sa izdavačima (dobavljačima) časopisa i baza podataka u cilju što povoljnije nabavke
-
potpisuje licencne ugovore o korišćenju pretplaćenih servia
-
kreira, ažurira i održava veb stranicu dostupnu svim krajnjim korisnicima u Srbiji
-
instalira i održava sve mrežne baze podataka na centralnom računaru, a koje moraju biti dostupne svim korisnicima
-
prati iskorišćenost nabavljenih naučnih informacija i o tome izveštava finansijere Konzorcijuma
Prezentacija "KOBSON-prostup, mogućnosti, namena" je dostupna na adresi
http://old.matf.bg.ac.rs/vesti/428/kako-do-naucnih-informacija-kobson---pristup-mogucnosti-namena/
Teme za seminarski
Tema br 1. (Bojana Zečević 1108/2011)
Tema br 6. (Miloš Stanković 1030/2011)
Tema br 10. (Vladimir Elez 1058/2009)
Tema br 11. (Rajačić Jasna 1110/2011)
Zadati problem najpre treba resiti CPLEX solverom na postojecem iili generisanom skup primera. Zatim problem resavati nekom od izabranih egzaktnih ili heuristickih metoda ili njihovim kombinovanjem.
Redni broj izabrane teme (kao i ime, prezime i broj indeksa) poslati mailom na zoricast@matf.bg.ac.rs.