Kombinatorikus optimalizálás

Kombinatorikus optimalizálás 2018

Vissza a főoldalra

A tárgy hivatalos honlapja

Az előadások keddenként 10:15-11:45 között vannak az IE220-as teremben (Április 3-án tavaszi szünet), a gyakorlatok pedig minden második pénteken az IB138-ban 14:15-15:45 között vannak (dátum szerint: 2018.02.16, 03.02,03.09,03.30, 04.20, 05.04,05.18, {Március 9-én pénteken 8:30-tól az IB134-ben lesz gyakorlat a 16-ai helyett})

A vizsgák:

Akinek az elsőn szerzett eredménye változott az eredetihez, kérem jelezze (mert a tábla sajnos az első zhban visszaállt a korábbi verzióra): Eredmények.

A vizsgák dátumai:
03.22. 18:00-20:00 Q-I terem
05.08. 18:00-20:00 Q-I terem
05.18. 14:00-16:00 (pótzh)
05.28 10:00-12:00 (pótpót: Neptun-on kell jelentkezni)

A jegyek a zhkon elért pontok alapján lesznek számítva. Mindkét zhn 60 pontot lehet elérni. (jegyek alakulása: 0-47: 1; 48-65: 2; 66-83: 3; 84-101: 4; 102-120: 5).
Két írásbeli vizsga lesz, mindkettőt teljesíteni kell legalább 40%-ra, sőt a kettőből az egyiknek elsőre sikerülnie kell legalább 40%-ra az aláírás megszerzéséhez.

Ha kérdésetek van írjatok nyugodtan emailt (cscsgy kukac gmail pont com).

A előadások és gyakorlatok anyagai:

ELSŐ előadás: Átbeszéltük a maximális párosítás keresésének problémáját. Tanultuk a Magyar módszert, aminek működését bizonyítottuk is (a végállapotban találtunk a párosításunk méretével megegyező méretű lefogó ponthalmazt).
Tanultuk a maximális összsúlyú párosítás problémáját, és ennek megoldására az Egerváry algoritmust
Végül egy példán követtük végig az Egerváry algoritmus működését.
FUNFACT: Valójában inkább az Egerváry algoritmust hívják magyar módszernek, de mivel a wikipédiát olyanok is szerkeszthetik akik nem feltétlen értik a maximális prosítás és maximális összsúlyú párosítás közötti különbséget, így sajnos ez tévesen került a magyar szócikkbe. Ennek ellenére meghagyom így, mert így viszont könnyebb rájuk külön hivatkozni.

MÁSODIK előadás: Megbeszéltük, hogy hogyan használható az Egerváry algoritmus olyan esetben amikor nem maximális összsúlyú teljes párosítást keresnénk, csak maximális összsúlyú párosítást (1. a negatív élek törlése; 2. a kisebbik színosztály bővítése, 3. a hiányzó élek behúzása 0 súllyal).
Tanultuk a lineáris programozás alapfeladatát, és láttunk egy egyszerű példán grafikus megoldást.
Megbeszéltük a három fő problémakört: 1. megoldás létezése; 2. megoldások célfüggvény értékének korlátossága; 3. optimális megoldás értéke.
Tanultuk a 'standard' forma mátrixos reprezentációját (max{cx: Ax<=b}).
Tanultuk hogyan kell standard formára hozni a lineáris programozási feladatot, ha minimalizálási problémát kapunk, ha az egyenlőtlenségek iránya nem stimmelne és ha egyenlőségi kritérium is lenne.
Tanultuk a Fourier-Motzkin eliminációt, a megoldhatóság eldöntésére.

ELSŐ gyakorlat: Egerváry, (megcsináltuk az első három feladatot)
Fourier-Motzkin, (mecsináltuk az első feladatot)
Egerváry, Grafikus LP megoldás, Fourier-Motzkin (elkezdtük az 1-es feladat első mátrixát, és nagyjából megcsináltuk az 5-öst)

HARMADIK előadás: P és NP problémaosztályok átismétlése.
Megoldhatóság ekvivalens feltétele: Farkas lemmák (könnyű irányok bizonyításával).
Korlátosság ekvivalens feltétele: 3 kalitkás tétel (2<=>3 és 1=>2 bizonyítással).
Dualitás tétel. Lineáris programozási feladatok duálisai (egy alakból többi levezetése).
Lineáris programozási feladatok bonyolultsága. Egészértékű programozási feladat.

NEGYEDIK előadás: . NP teljesség, Karp redukció átismétlése.
Egészértékű programozási feladat bonyolultsága (maxklikk visszavezetés). Branch and bound (azaz korlátozás és szétválasztás). Példa hátizsák problémával: 10: 1-1,2-8,3-10,4-10,5-19,6-25.

MÁSODIK gyakorlat: Farkas lemmák, (megcsináltuk az első feladatot)
Dualitás, (mecsináltuk az első és negyedik feladatot)
Futtassuk a korlátozás és szétválasztás módszerét az alábbi hátizsák problémán 6: 3-25,2-18,1-15,4-40,5-41

ÖTÖDIK előadás: TU mátrix definíciója, példák, tulajdonságok (6). Egészértékű programozási feladatok dualitástétele.
Folyamfeladatok LP felírása, példa. Egészértékű folyam probléma polinom időben megoldható.

HARMADIK gyakorlat: Maximális összsúlyú párosítás ILP felírása, példa. Példák.

HATODIK előadás: Példák: maximális összsúlyú párosítás, maximális összsúlyú feszítőfa, maximális súlyú független ponthalmaz, maximális súlyú független oszlophalmaz. Ezen problémák általános közös formája
Mohó algoritmus, matroid, függetlenségi axiómák, kör, bázis, rang, izomorfia, törlés, összehúzás, minor, mátrix matroid, lineris matroid, bináris matroid, reguláris matroid, grafikus matroid. Tutte tételei tiltott minorokkal.
Példák.

HETEDIK előadás: gyakorlás a zhra. Duális matroid. Matroidok osztályainak tartalmazási relációi (Tutte tétele alapján). Rangfüggvény alakulása törlés, összehúzás, duálisképzés során. Bázisaxiómák.

NYOLCADIK előadás: ZH feladatok átbeszélése. Köraxiómák, Rangaxiómák. Matroid partíciós probléma, matroid metszet probléma.

KILENCEDIK előadás: Gyakorlás: rangfüggvényképletek (elhagyás, összehúzás, duális); A 4 ekvivalens axiómacsomag.
Házi feladatnak:
1. Milyen matroidot kapunk, ha összehúzunk j (kisebb n) elemet egy U_{n,k} uniform matroidban?
2. A K_{3,3} gráf matroidjában húzzunk össze két szomszédos élet, és hagyjuk el a harmadik szomszédjukat; mennyi lesz a kapott matroid duálisának a rangja?
3. Milyen k-ra kapunk matroidot, ha egy matroid függetlenei közül elhagyjuk a k elemű függetleneit?
4. Minden gráf esetén matroidot alkot a struktúra, aminek az alaphalmaza a csúcsok halmaza, a 'függetlenek' pedig a független ponthalmazok (semelyik kettő között nem fut él)?
5. Minden mátrix esetén matroidot alkot a struktúra, aminek alaphalmaza a mátrix oszlopainak halmaza, és egy k elemű halmaz 'független', ha van benne k-1 elemű független vektorhalmaz?

TIZEDIK előadás: Síkbarajzolhatóság és dualitás. Matroid összeg. Villamos hálózatok: Tassy Gergely diplomamunkájában szépen összefoglalva a 15-18. oldalakon.
Matroid metszet alkalmazásai: maximális párosítás páros gráfban; feszítő fenyő keresés; irányított u-v Hamilton út;

NEGYEDIK gyakorlat: Villamos hálózati példák. (vezérlés nélkül / vezérléssel)
Matroid metszet példák (1. max párosítás; 2. feszítő fenyő, Hamilton út).

TIZENEGYEDIK előadás: Többszörös összefüggőség: Nagamochi Ibaraki algoritmus. Dinamikus programozás: hátizsák problémára, Dijkstra legrövidebb utakra, és legszélesebb utakra.

ÖTÖDIK gyakorlat: Hátizsák DP: 6:2-5,1-4,4-12,3-9,5-15; Nagamochi Ibaraki példák. Legrövidebb, legszélesebb példák.
Házi feladatok:a) Dijkstra legrövideb utakra A-ból és G-ből Megoldás
b) Dijkstra legrövideb utakra k-ból és e-ből Megoldás
c) Dijkstra legszélesebb utakra 3-ból és 4-ből Megoldás
d) Dijkstra legszélesebb utakra 3-ból és 7-ből Megoldás
e) Oldjuk meg dinamikus programozással az alábbi hátizsák problémát: 10: 1-1,2-8,3-10,4-10,5-19,6-25 Megoldás
f) Oldjuk meg dinamikus programozással az alábbi hátizsák problémát: 6: 3-25,2-20,1-15,4-40,5-50 Megoldás
g) Nagamochi Ibaraki algoritmussal állapítsuk meg az összefüggőségi számát az a) részfeladat gráfjának. h) Nagamochi Ibaraki algoritmussal állapítsuk meg az összefüggőségi számát a b) részfeladat gráfjának.

TIZENKETTEDIK előadás: Gyakorlás / konzultáció a ZHra.

Hasznos dolgok gyűjteménye:

Az órán látott példa az Egerváry algoritmusra.

A tárgyhoz kapcsolódó tankönyv: Jordán Tibor - Recski András - Szeszlér Dávid: Rendszeroptimalizálás, Typotex Kiadó, 2004
Másik link
Harmadik link
Sajtóhibák rövid jegyzéke a fenti könyvben