Семинар за рачунарство и примењену математику, 29. март 2016.

• 28. Март, 2016
• Коментари (0)

Наредни састанак Семинара биће одржан у уторак, 29. марта 2016. у сали 301ф Математичког института САНУ са почетком у 14:15 часова.

Предавач: Татјана Давидовић, Математички институт САНУ

Наслов предавања: МАТХЕУРИСТИКА VINS

Апстракт: Развијена је нова матхеуристика, хеуристичка оптимизациона метода, добијена хибридизацијом егзактног MIP солвера са процедуром локалне претраге кроз различите околине. Ова метода користи идеју за фиксирање подскупа бинарних променљивих и коришћење егзактног солвера за решавање добијеног потпроблема, тј. одређивање вредности за преостале (нефиксиране) променљиве. Које променљиве и колико њих ће се фиксирати одређује се на разне начине и тиме се дефинишу разне околине за претрагу. Експериментисано је са 10 типова околина. Величине околина се систематски повећавају, а у складу са тим, повећава се и време дозвољено за рад егзактног солвера. Тиме се повећава интензитет претраге у одговарајућој околини. Промена околина, као и интензитета претраге инспирација су за име нове методе: Variable Intensity Neighborhood Search (VINS). Метода је настала комбиновањем идеја из две познате матхеуристике: Variable Intensity Local Search (VILS) и Variable Neighborhood Decomposition Search for 0-1 MIP (VNDS-MIP). Експерименталана евалуација извршена је на два скупа тест примера бенчмарк инстанци из MIPLIB 3.0 библиотеке и реалним примерима рутирања контејнерских бродова у речној пловидби. Предложена метода поређена је са VNDS-MIP методом и показано је да VINS најчешће даје боље резултате од свог претходника, било по квалитету решења, било по времену извршавања, а некад и по оба критеријума.

Резултати су добијени у сарадњи са П. Јовановићем, Ј. Лазић и С. Митровић Минић.