Continous Optimization Seminars

Folytonos optimalizálás szeminárium
Időpontja: csütörtök 13:15 - 14:45
Helye: Műegyetem H épület, 306.


Előadások :

2011.06.28. Terlaky Tamás Cone Linear Optimization (CLO) From LO, SOCO and SDO towards mixed integer CLO
2011.05.05. Papp Olga A szimplex módszer implementációja vágósíkos eljárásként
2011.04.28.

Barta Zsuzsa
Nagy Adrienn

Operációkutatási problémák modellezése MOSEL (XPRSS-MP) környezetben
Pivot algoritmusok implementálása az XPRESS-MP callable library-je segítségével C-ben
2011.04.07. Markót Mihály A COCONUT Environment optimalizálási környezet
2011.03.31. Tatay Viola Menedzsmentdöntések támogatása gyártósor-kiegyenlítési modellekkel
2011.03.24. Dósa György Ütemezés és ládapakolás
2011.03.03. Újvári Miklós A stabilitási szám négy új felső korlátja
2011.02.17. Csendes Tibor Megbízható számítógépes eljárások

Korábbi félévek előadásai (Átmenetileg nem elérhető)


Cone Linear Optimization (CLO) From LO, SOCO and SDO towards mixed integer CLO

Fóliák

Cone Linear Optimization (CLO) has been the subject of intense study in the past two decades. Interior Point Methods (IPMs) provide polynomial time algorithms in theory, and powerful software tools in computational practice. The applications of Second-Order Conic (SOCO) and Semi-Definite Optimization (SDO) expanded rapidly. The first part of this talk reviews model formulation, IPM fundamentals, available software and some applications of CLO problems.

The use of integer variables naturally occur in CLO problems too, thus the need for dedicated mixed integer CLO algorithms and software is evident. The second part of this talk gives some insight of how to design disjunctive conic cuts for mixed integer CLO problems.


A szimplex módszer implementációja vágósíkos eljárásként

Megmutatjuk, hogy a szimplex módszer vágósíkos eljárásként értelmezhető, feltéve, hogy egy speciális árképzési szabályt alkalmazunk. Ezt a megközelítést a speciális sztochasztikus programozási feladatok vágósíkos eljárásokkal történő megoldásának nemrégiben elért sikerei motiválják.Összehasonlítjuk a klasszikus Danztig és a vágósíkos eljárásból levezetett árképzési szabályokat. A speciális lineáris programozási feladatra összpontosítunk, amelyben adott poliéderbe elférő legnagyobb gömböt keressük.

A COCONUT Environment optimalizálási környezet

A COCONUT Environment egy nyílt forráskódú, moduláris szoftvercsomag, elsősorban globális optimalizálási, illetve feltétel-kielégítési problémák  intervallumos számításokon alapuló (ún. megbízható) megoldásához. Fejlesztésének fő céljai a következők: az optimalizáláshoz köthető vezető - intervallumos es nem intervallumos - algoritmusok közös környezetbe integrálása, az ezeken alapuló keresőszoftverek kidolgozásának támogatása, egy egységes tesztkörnyezet biztositása, valamint kész megoldó szoftverek rendelkezésre bocsátása.

Az előadás három részből áll: az első részben a COCONUT felépítését és főbb komponenseit tekintem át. A második részben bemutatom az aritmetikai kifejezések körmentes aciklikus gráfokkal (DAG) történő reprezentálását es kiértékelését a COCONUT-ban: függvényértékek, első- és másodrendű deriváltak kiszámítását (valós és intervallum típusú  argumentumokon), valamint első- és másodrendű intervallumos lejtő (slope) formulák meghatározását. Az előadás harmadik részében röviden  ismertetek néhány, az intervallumos globális optimalizálási eljárások fejlesztéséhez köthető COCONUT-os projektet: lokális keresők automatizált  kiválasztását, kizáróbefoglaló box-ok meghatározását (azaz egy -  közelítően ismert - helyi szelsőérték létezésének és egyértelműségének  igazolását annak egy környezetében), végül egy korábbi bound-onstrained optimalizáló eljárás adaptálását és továbbfejlesztett változatát.

Menedzsmentdöntések támogatása gyártósor-kiegyenlítési modellekkel

A gyártósor-kiegyenlítés egymás után többször végrehajtandó, azonos tevékenységek szervezésével foglalkozik. A különböző műveletek végrehajtásának eredménye lehet egy termék (például járművek, elektronikai berendezések) vagy egy szolgáltatás (például egészségügyi szolgáltatás, ügyviteli feladatok végrehajtása). A gyártósor-kiegyenlítés célja a különböző tevékenységek munkahelyhez, munkáshoz rendelése úgy, hogy az bizonyos menedzsment céloknak a lehető legjobban megfeleljen. Ezt a hozzárendelést számos tényező befolyásolja, mint például a tevékenységek közötti logikai kapcsolatok, a tevékenységek végrehajtásának ideje, technológiai és minőségügyi előírások. A tevékenységek munkahelyhez rendelésekor cél lehet a szükséges munkahelyszám minimalizálása, a ciklusidő minimalizálása vagy a hatékonyság maximalizálása. A különböző célú, optimális hozzárendelések matematikai programozási modellekkel ma már elhanyagolható időn belül meghatározhatóak. Az előadás célja a gyártósor-kiegyenlítés alapmodelljeinek áttekintése és a modellek menedzsment alkalmazási lehetőségeinek bemutatása. Az előadás kiemelten foglalkozik a dolgozók eltérő képzettségeiből és a feladatok különböző nehézségi szintjeiből adódó korlátoknak az optimális megoldásra kifejtett hatásával.


Ütemezés és ládapakolás

Előadásunkban ládapakolási és ütemezés-elméleti feladatokkal (ezen belül offline, online, szemi-online feladatokkal is) foglalkozunk. Áttekintünk néhány klasszikus modellt, és eredményt is. Egyes modellek bemutatásán túl az előadás betekintést igyekszik nyújtani a legjobb/legújabb eredményekbe is, bemutatunk néhány algoritmust,úgynevezett "adversary" konstrukciókat is, amelyek a feladatok bármely algoritmusának hatékonyságára alsó korlátot szabnak. Nagyjából a következő feladatokkal foglalkozunk:
   * Párhuzamos gépek ütemezése
   * Klasszikus ládapakolási feladat, First Fit, First Fit Decreasing algoritmusok, ezekre vonatkozó hatékonysági becslések
   * Ütemezés, ládapakolás elutasítással
   * Gépköltséges ütemezés
   * Pufferes és átrendezéses modellek (2 hasonló gép ütemezésekor)
   * Ládapakolás LIB (largest in bottom) feltétellel
Esetleg más modellek is szóba kerülhetnek, új feladatok, nyitott kérdések


A stabilitási szám négy új felső korlátja

1979-ben Lovász definiálta a théta-függvényt, amely gráfok stabilitási számának perfekt gráfokra pontos spektrális/szemidefinit felső korlátja. A Lovász-szám definíciója az ortonormált reprezentáció fogalmán alapul, és duálisan megkapható, mint az elemösszeg maximuma a théta konvex test felett. Az előadásban Wilf, Hoffman és Lovász tételeinek tükörképeit tárgyaljuk. A stabilitási szám három spektrális és egy szemidefinit felső korlátját írjuk le, amelyek nemnegatív mátrixok egy poliédere, illetve az inverz théta test felett optimalizálva nyerhetők.
A szemidefinit korlát ugyanúgy multiplikatív, mint a théta-függvény, így a Shannon-kapacitás felső korlátja is.


Megbízható számítógépes eljárások

Az előadás címe kissé rejtélyes: a számítógépes algoritmusok a köztudat szerint pontosak és megbízhatók. Az alku során az ügynökök végső érve gyakran az, hogy a kalkulátor is a mondott számot mutatja.
Ezzel szemben sajnos fontos feladatok megoldása során is azzal szembesülünk, hogy a kapott eredmény csak közelítő érték, és gyakran kritikus esetben a kapott szám nagyságrendje, vagy az előjele sem helyes. Ennek ellenére van olyan számítógépes módszertan, amely biztosítani tudja a numerikus számítások tetszőleges pontosságát és megbízhatóságát. Ez úgy érhető el, hogy a többet kell számolni, és tovább tart a megoldás. Gyakran a gép memóriája is nagy kell hogy legyen.
Az intervallum aritmetikára támaszkodó eljárások eredményességét körpakolási feladatok megoldásával, az inga kaotikusságának matematikai szigorúsággal vett igazolásával és  ipari-gazdasági problémák kezelésében való hasznosságával illusztráljuk.


Department of Operations Research, Eötvös Loránd University of Sciences
1117 Budapest, Pázmány Péter Sétány 1/c, Hungary
Contact: Nagy Adrienn - orr@cs.elte.hu