Циљ и исход предмета
Циљ предмета је да се студенти упознају са најважнијим проблемима комбинаторне оптимизације и методама за њихово решавање. Способност карактеризације оптималних решења и налажење ефикасних алгоритама за оптимизационе проблеме над дискретним структурама, као што су нпр. проблеми протока кроз мрежу, оптимално поклапање, матроидна оптимизација, итд.
Теоријска настава
Целобројни полиедри. Методе одсецања. Методе гранања и ограничавања. Методе имплицитне енумерације. Оптимална стабла и путеви. Минимална разапињућа стабла и похлепни алгоритми. Одређивање најкраћег пута. Протоци у мрежама. Одређивање максималног протока. Одређивање протока са минималном ценом. Симплекс метода на мрежама. Оптимална спаривања. Спаривање у бипартитним графовима. Спаривање у произвољним графовима. Спаривање у тежинским графовима. Проблем максималног спаривања. Хамилтонови путеви и проблем трговачког путника. Разне релаксације проблема трговачког путника: Lin-Kernighan хеуристика. Проблем више трговачких путника.
Студијски истраживачки рад
Део наставе на предмету се одвија кроз самостални студијски истраживачки рад који обухвата примену комбинаторне оптимизације у рачунарским наукама и рачунарском инжењерству.