Odabrana poglavlja optimizacijeArchived course

1.    Osnove matematičkog modeliranja.
2.    Egzaktni rešavači (CPLEX, LINGO, korišćenje AMPL-a)
3.    Heurističke i metaheurističke metode
      (osnovni pojmovi, osobine, klasifikacija)
4.    Optimizacija metodom kolonije pčela
5.    Genetski algoritmi, osnovni i napredni koncepti
6.    Metoda roja čestica
7.    Mravlje kolonije
8.    Lokalno pretraživanje i varijante
9.    Simulirano kaljenje
10.  Tabu pretraživanje
11.  Metoda promenljivih okolina
12.  Hibridizacija metoda optimizacije.
       Matheuristike. Hibridne metaheuristike.

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.

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.

U okviru kursa bice obrađen CPLEX rešavač 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.

IBM ILOG CPLEX Optimizer

CPLEX v.12.1 User Manual

Prezentacija o CPLEX-u

Korisne napomene

CPLEX i AMPL prezentacija Tanje Davidović, MI SANU

CPLEX i AMPL primeri

Izrada domaćeg zadatka je predispitna obaveza.

Zadatak treba poslati mailom na kristina_kostic[at]matf.bg.ac.rs i zoricast[at]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 2h. 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! Može se koristiti AMPL za CPLEX.

Primeri domaćih zadataka:

Primer 1.

Primer 2.

Prezentacije:

Evolutivni algoritmi + primeri

PSO + primer BLUFLP

ACO+primer TSP

ACO+LS_problem BPP   Master.pdf

BCO-Tanja Davidović, MI SANU

Heuristike zasnovane na lokalnom pretraživanju (LS, ILS, SA, TS, VNS)

VNS, Matheuristike-Tanja Davidović, MI SANU

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 izveštaje testiranja metaheuristika

Uputstvo za navođenje literature i pozive u tekstu

Neophodne radove za uvodni deo potražiti na Kobson-u.

Primer seminarskog rada 1

Primer seminarskog rada 2

Primer seminarskog rada 3

Primer seminarskog rada 4(prateći pdf)    Kod seminarskog 4

Š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

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/