Cilj i ishod predmeta
Cilj predmeta je da se studenti upoznaju sa najvažnijim problemima kombinatorne optimizacije i metodama za njihovo rešavanje. Sposobnost karakterizacije optimalnih rešenja i nalaženje efikasnih algoritama za optimizacione probleme nad diskretnim strukturama, kao što su npr. problemi protoka kroz mrežu, optimalno poklapanje, matroidna optimizacija, itd.
Teorijska nastava
Celobrojni poliedri. Metode odsecanja. Metode grananja i ograničavanja. Metode implicitne enumeracije. Optimalna stabla i putevi. Minimalna razapinjuća stabla i pohlepni algoritmi. Određivanje najkraćeg puta. Protoci u mrežama. Određivanje maksimalnog protoka. Određivanje protoka sa minimalnom cenom. Simpleks metoda na mrežama. Optimalna sparivanja. Sparivanje u bipartitnim grafovima. Sparivanje u proizvoljnim grafovima. Sparivanje u težinskim grafovima. Problem maksimalnog sparivanja. Hamiltonovi putevi i problem trgovačkog putnika. Razne relaksacije problema trgovačkog putnika: Lin-Kernighan heuristika. Problem više trgovačkih putnika.
Studijski istraživački rad
Deo nastave na predmetu se odvija kroz samostalni studijski istraživački rad koji obuhvata primenu kombinatorne optimizacije u računarskim naukama i računarskom inženjerstvu.