Одељење за математику, 20. март 2020.

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

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

Наслов предавања: МАТХЕУРИСТИКЕ-ХИБРИДИ ИЗМЕЂУ МЕТАХЕУРИСТИЧКИХ И ЕГЗАКТНИХ МЕТОДА

Апстракт:
Проблеми оптимизације се обично формулишу у облику мешовитих целобројних програма (Mixed Integer Programs, MIP) и решавају се различитим егзактним решавачима (CPLEX, Gurobi, итд.). Међутим, за већину реалних инстанци проблема егзактне методе захтевају превише времена и меморије, па се обично уместо њих примењују метахеуристике. Оне представљају уопштене алгоритме за оптимизацију дате циљне функције итеративним генерисањем нових или побољшањем постојећих решења. Уопштеност подразумева да се у опису метахеуристичког алгоритма не користе априори знања о конкретном  проблему оптимизације, већ се они дефинишу као скуп корака (рецепт) о томе како треба манипулисати решењима проблема у циљу добијања што квалитетнијих коначних резултата. Самим тим омогућена је примена ових метода на различите оптимизационе проблеме, али је њихова велика мана што не могу да гарантују квалитет коначних решења. Међу уопштеним хеуристикама, посебно место заузимају 0-1 MIP методе, тзв. матхеуристике. Ове методе су хибриди између метахеуристичких метода и егзактних решавача за MIP проблеме. Главна идеја која се крије иза ове хибридизације је декомпозиција полазног проблема тако што се употребом метахеуристичких правила генеришу потпроблеми који се онда решавају егзактним решавачем. У оквиру предавања детаљно ће бити приказане три методе из литературе код којих се као метахеуристика користи метода променљивих околина (или њене варијације). То су гранање кроз променљиве околине (Variable Neighborhood Branching, VNB,), метода променљивих околина са декомпозицијом за 0-1 MIP (Variable Neighborhood Decomposition Search for 0-1 MIP, VNDS-MIP) и метода претраге околина променљивим интензитетом (Variable Intensity Neighborhood Search, VINS). Најважнија особина матхеуристика је што се, под одређеним условима, могу сматрати егзактним методама.


Оставите ваш коментар:


(опционо)
(неће бити приказано)



Вести и дешавања


Активности на семинарима

све вести