Intézeti Szeminárium

Speciális MINLP feladatokhoz adtunk olyan egzakt módszereket, amik képesek megtalálni a globális optimum adott pontosságú közelítését. Ilyen a hálózaton értelmezett maximális fedési feladat, ahol adott számú vállalat elhelyezése a cél úgy, hogy adott távolságon belül minél többet fedjünk le az éleken folytonosan megadott keresletből. A feladat analitikusan nem megadható, és nem is mindig Lipschitz-folytonos. A felírt MINLP kombinatorikus feladata az élek kiválasztása a vállalatok elhelyezéséhez, míg a folytonos globális optimalizálási feladat a kiválasztott éleken megtalálni az optimális megoldást. Merőben újszerű a korlátozás és szétválasztás (B&B) módszerben a részfeladatok adatszerkezete, és a kapcsolódó felosztási, korlátozási eljárások is. Szintén MINLP egy vállalatlánc cégbővítési feladata, ahol adott befektetési keret mellett kell eldönteni mi hozza a legnagyobb profitot: egy új vállalat telepítése, vagy a létezők bezárása/minőségének változtatása. Az intervallumos B&B módszert általánosítottuk MINLP feladatokra, és vizsgáljuk a gyorsító eljárások adaptálási lehetőségeit sikeresen, az elérhető szoftvereket felülmúlva. Végül egy elhelyezési és árazási játék egyensúlyi pontjának megoldásához adtunk egy intervallumos módszert, illetve egy heurisztikus eljárást.

A szimplex-alapú B&B módszer vizsgálata során kidolgoztunk egy szabályos szimplexekkel történő felosztási eljárást, illetve több gradiensen alapuló korlátozási módszert. A kivágási szabályok fejlesztésére kidolgoztunk egy fejlett monotonitási tesztet és egy kizáró gömbökre épülő szimplex-fedési eljárást. A fejlesztett módszer minden aspektusban rengeteget javult a naív eljáráshoz képest.