Heurističke metode

Tabela predmeta Heurističke metode

Predispitne obaveze (30 poena)

Domaći zadatak - Implementacija matematičkog modela konkretnog problema optimizacije u CPLEX-u. 

Student na predispitnim obavezama mora osvojiti najmanje 16 poena da bi pristupio praktičnom ispitu.

Praktični ispit (40 poena)

Seminarski rad - Implementacija konkretne heurističke metode na isti problem iz domaćeg zadatka i odbrana seminarskog. 

Student na praktičnom ispitu mora osvojiti najmanje 20 poena da bi pristupio usmenom ispitu.

Usmeni ispit (30 poena)

Usmeni ispit se sastoji iz provere znanja iz koncepata heurističkih metoda koje su obrađene na predavanjima.

Student na usmenom ispitu mora osvojiti najmanje 15 poena.

Izrada domaćeg zadatka je predispitna obaveza i nosi max 30 poena.

Zadatak (kod i prateći pdf) treba poslati mejlom na kristina.ivanovic[at]matf.bg.ac.rs i zorica.stanimirovic[at]matf.bg.ac.rs . Rok za predaju domaćeg zadatka je četvrtak, 28. januar 2025. Odbrana će biti u sredu, 4. februara 2026. sa početkom u 13:15 u sali BIM.

Mejl 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;

- instance bi trebalo podeliti u 3 grupe: 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;

- tabele sa rezultatima CPLEX-a na svakoj grupi instanci. Vreme izvršavanja CPLEX-a ograničiti na 2h. Rezultati CPLEX-a na jednoj instanci treba da sadrže: optimalno rešenje koje je CPLEX dobio, vreme izvršavanja, broj iteracija, broj čvorova;

- ukoliko CPLEX kroz 2h nije dobio optimalno rešenje, ispisati najbolje dopustivo rešenje koje je do tada dobio, sa naznakom da rešenje nije optimalno. Takođe naznačiti ukoliko CPLEX nije dao čak ni dopustivo rešenje kroz 2h;

- 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.

Akademska licenca za CPLEX

Primer domaćeg zadatka

Student pristupa izradi seminarskog rada nakon izrade i odbrane domaćeg zadatka - rešavanje zadatog problema optimizacije korišćenjem CPLEX-a (predispitna obaveza).

Seminarski rad predstavlja praktični ispit koji nosi 40 poena, a sastoji se u implementaciji jedne konkrente heuristike za rešavanje istog problema optimizacije iz domaćeg zadatka. Seminarski rad je moguće odbraniti u bilo kom ispitnom roku (ili ranije, kada ga student završi). Seminarski rad (implementaciju heuristike i prateći pdf) poslati na adrese kristina.ivanovic[at]matf.bg.ac.rs i zorica.stanimirovic[at]matf.bg.ac.rs.

Za problem iz domaćeg zadatka treba osmisliti heurističku metodu za dati problem, a zatim napisati njenu implementaciju. Za testiranje metaheuristike koristiti skup instanci kao u domaćem zadatku i ako je potrebno i dodatne test primere.  Dobijene rezultate heuristike uporediti sa optimalnim rešenjima dobijenim pomoću CPLEX solvera ili poznatim rešenjima iz literature.

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 koncepta konkretne heuristike zajedno sa pseudokodom i njena adaptacija na razmatrani problem.

5. Rezultati testiranja, analiza rezultata i poređenja (pogledati način izrade izveštaja).

8. Zaključak.

9. Spisak korišćene literature (reference).

Primer seminarskog rada

Uputstvo za navođenje literature i pozive u tekstu

Neophodni radove iz literature mogu se naći na Kobson-u.