Optimalizálás Felsőfokon

A kurzusról

Az (egészértékű) lineáris programozás, mint modellezési eszköz számos esetben hatékony megoldást és mély megértést szolgáltat gráfelméleti/hálózatkutatási problémákhoz. Az utóbbi évtizedekben számos olyan megoldási módszert javasoltak a szakirodalomban, amelyeket aztán egyre többször látni a tudományos cikkekben, alkalmazásokban. Ezen módszerek jelentős része, idő hiányában, már kimarad a kötelező és szakirányos kurzusok tematikájából. Az Optimalizálás Felsőfokon kurzus így ezt a hiányt pótolja.

Kapcsolódó oldalak

For the materials including AMPL model and data files please visit the course website.

The same course was held in English, here is the website of Advanced Optimization

Témakörök (elsősorban a PhD komplex vizsgához)

1 Egészértékű programozás (ILP alapok)

• Tartalom:
  • ILP definíciója, bináris egészértékű program, kevert egészértékű program
  • Példák: hozzárendelési feladat, hátizsák
  • Relaxáció, megoldás kerekítéssel (miért nem jó)
  • Szimplex algoritmus (csak az alapok)
  • Dualitás, dualitási tételek (gyenge és erős)
  • Poliéder, politóp
  • Korlátozás és szétválasztás (csak az alapok)
• Jegyzet
• Videó - sajnos nincs

AMPL bevezetés és Modellezési trükkök

• Tartalom:
• Jegyzet

Teljesen unimoduláris mátrixok (TUM)

• Tartalom:
  • TUM definíció
  • TUM tulajdonságok
  • LP feladat TUM korlátozó feltétel mátrixszal mindig egész értékű megoldást ad (tétel és bizonyítás)
  • Incidencia mátrix TUM (tétel és bizonyítás)
  • Páros gráfok és TUM
  • Példák: legrövidebb út, maximális párosítás páros gráfokon, minimális s-t vágás
• Jegyzet
• Videó - sajnos nincs

Dantzig-Wolfe dekompozíció

• Tartalom:
  • Példa
• Jegyzet és fóliasor (A Papavasiliou anyaga)
• Videók (angolul): part 1, part 2, part 3.