Наредни састанак Семинара биће одржан у уторак, 27. маја 2025. године, у Огранку МИ САНУ у Новом Саду са почетком у 14.15.
Предавач: Нада Младеновић, Факултет организационих наука Универзитета у Београду
Наслов предавања: АПРОКСИМАТИВНИ (ANYTIME) АЛГОРИТМИ ЗА ГЕНЕРИСАЊЕ ПАРЕТО ФРОНТА ВИШЕКРИТЕРИЈУМСКОГ ПРОБЛЕМА РАНЦА
Апстракт: Предлажемо два приступа за решавање вишекритеријумског 0-1 проблема ранца са вишеструким ограничењима: једна матхеуристика и једна конструктивна хеуристика. За вечину инстанци малих димензија, наша матхеуристика успешно генерише цео Парето фронт поменутог проблема, док за остале, може се добити само апроксимација нултог реда која садржи добро распоређене недоминиране тачке Парето фронта. За инстанце великих димензија, и матхеуристика и конструктивна хеуристика добијају погодну апроксимацију Парето фронта првог реда. Инспирисани PESA алгоритмом који је недавно уведен за решавање вишекритеријумских континуалних проблема, покушали смо да егзактно решимо проблеме целобројне вишекритеријумске оптимизације на сличан начин, уз коришћење специфичности комбинаторних проблема. За велике инстанце, где је потребна апроксимација, преузели смо из PESA начин одређивања хипотетичких граница и формулисали хеуристике за решавање новонасталих једнокритеријумских проблема. Егзактно смо решили инстанце различитих степена сложености са 50 и 100 предмета. Наши алгоритми су у прихватљивом времену налазили приближна решења за инстанце са 400, 450 и 500 предмета.
Излагање представља резултате сарадње са Богданом Станојевић.
Напомена: Предавања на Семинару се снимају и преносе уживо.
Све информације могу се наћи на страници
https://miteam.mi.sanu.ac.rs/asset/qGapAHyEBad2FDwXR
