Barta
Zsuzsanna:
Dekompozíciós módszerek alkalmazása nagyméretű optimalizálási feladatokra
<br><br>
A gyakorlati életben számos olyan nehéz optimalizálási problémával
szembesülünk (általában NP-teljesek), melyekben jól felismerhetőek
egyszerűbb problémák (hatékonyan megoldhatók), amiket egyéb feltételek
kapcsolnak össze. Csak néhány példa: időkorlátos legolcsóbb út,
utazóügynök feladat, gyárelhelyezési probléma, többdimenziós hátizsák
feladat, általánosított hozzárendelési probléma illetve a minimális
költségű többtermékes folyamfeladat. A széleskörűen alkalmazható
Lagrange relaxáció lehetőséget ad arra, hogy a nehéz feltételek
relaxálásával az eredeti probléma szétessen hatékonyan megoldható,
kisebb feladatokra. Az előadásban megvizsgáljuk, hogy mit veszítünk a
relaxációval, milyen feltételeket érdemes relaxálni illetve hogyan
tudjuk hatékonyan megoldani a relaxált feladatot.