Home  
  Teaching  
  Research  
  Misc  
Milan Hladík
Teaching

Ročníkové projekty a bakalářské práce

Projekty a práce tématicky především z oblasti lineární algebry, intervalové analýzy a optimalizace. U projektů preferuji pokračování do bakalářské práce.

Některá témata jsou v SISu. Další navrhovaná témata jsou dole (můžete přijít i s vlastním tématem), jedná se zejména o problémy z intervalového počítání, proto jsem sepsal pár základních informací a odkazů o intervalovém počítání. Může se také hodit pár užitečných odkazů.

  • Utažení pivota pro parametrické lineární soustavy rovnic [zabráno]

    • Utažení pivota je způsob jak zefektivnit (z hlediska výsledné obálky množiny řešení) metody na řešení soustav intervalových lineárních rovnic, a to konkrétně Gaussovy eliminace pro obecnou soustavu a Choleského rozklad pro soustavu s positivně definitní maticí. Cílem projektu je rozšířit tento způsob na intervalové soustavy s lineárními závislostmi. Součástí by mělo být i numerické porovnání s jinými metodami řešení. Programovací jazyk: Matlab/Octave + Intlab.

    Odkazy:

    1. J. Garloff. Pivot tightening for direct methods for solving symmetric positive definite systems of linear interval equations. Comput. 94(2-4):97-107, 2012.
    2. J. Garloff. Interval Gaussian elimination with pivot tightening. SIAM J. Matrix Anal. Appl. 30(4):1761-1772, 2009.
    3. M. Hladík. Enclosures for the solution set of parametric interval linear systems. Int. J. Appl. Math. Comput. Sci., 22(3):561–574, 2012.

  • Obraz boxu při bilineárním a kvadratickém zobrazení

    • Obraz intervalového boxu při bilineárním a kvadratickém zobrazení se dá snadno odhadnout vyhodnocením intervalovou aritmetikou, ale výsledek může být značně nadhodnocen. Cílem této práce je vylepšit tyto základní odhady použitím algebraických maticových dekompozic, linearizací používaných v optimalizaci, heuristik a jiných technik. Součástí by měla být implementace a numerické porovnání metod. Programovací jazyk: Matlab/Octave + Intlab.

    Odkazy:

    1. C. A. Floudas. Deterministic Global Optimization. Theory, Methods and Applications, Kluwer, 2000.
    2. Arnold Neumaier. Interval methods for systems of equations. Cambridge University Press, 1990.
    3. S. M. Rump. Verification methods: Rigorous results using floating-point arithmetic. Acta Numer., 19:287-­449, 2010.

  • Grafické znázornění komplexních vlastních čísel intervalové matice

    • Problém spočívá ve vykreslení množiny všech komplexních čísel všech matic, které se od zadané matice A liší v každé složce nanejvýš o nějaké δij. Tato množina není jednoduše popsatelná, a proto se musí aproximovat. Například metody založené na principu branch & bound aproximují množinu s libovolnou přesností. Cílem projektu je navrhnout a implementovat metodu, která vykreslí tyto množiny s předem danou přesností. Programovací jazyk: Matlab/Octave + Intlab.

    Odkazy:

    1. E. Garajová: Intervalový solver nelineárních podmínek, 2014.
    2. M. Hladík. Bounds on eigenvalues of real and complex interval matrices. Appl. Math. Comput., 219(10):5584–5591, 2013.
    3. M. Hladík, D. Daney, and E.P. Tsigaridas. A filtering method for the interval eigenvalue problem. Appl. Math. Comput., 217(12):5236–5242, 2011.
    4. J. Rohn. Checking properties of interval matrices. Technical Report 686, Institute of Computer Science, Academy of Sciences of the Czech Republic, 1996.
    5. J. Rohn. A handbook of results on interval linear problems. Technical Report 1163, Institute of Computer Science, Academy of Sciences of the Czech Republic, 2012.

  • Lokalizace vlastních čísel intervalových matic

    • Zde nás zajímá množina všech komplexních čísel všech matic, které se od zadané matice A liší v každé složce nanejvýš o nějaké δij. Cílem práce je zapouzdřit tuto množinu pomocí jednoduchých odhadů založených na Gerschgorinových discích, Cassiniho oválech a dalších pokročilých technik. Konkrétně, jedná se o adaptaci výše zmíněných metod na intervalové matice, porovnání metod a jejich implementace. Programovací část (jazyk Matlab/Octave + Intlab) zahrnuje i vizualizaci odhadů.

    Odkazy:

    1. H.-B. Li, T.-Z. Huang, and H. Li On some subclasses of P-matrices. Numer. Linear Algebra Appl., 14: 391–405, 2007.
    2. M. Hladík. Bounds on eigenvalues of real and complex interval matrices. Appl. Math. Comput., 219(10):5584–5591, 2013.
    3. M. Hladík, D. Daney, and E.P. Tsigaridas. A filtering method for the interval eigenvalue problem. Appl. Math. Comput., 217(12):5236–5242, 2011.
    4. J.M. Peña. On an alternative to Gerschgorin circles and ovals of Cassini. Numer. Math., 95(2): 337-­345 , 2003.
    5. J. Rohn. A handbook of results on interval linear problems. Technical Report 1163, Institute of Computer Science, Academy of Sciences of the Czech Republic, 2012.

  • AE řešitelnost intervalových soustav [zabráno]

    • Určité úlohy v robotice vedou na lineární systémy s intervalovými parametry, přičemž parametry jsou dvojího druhu. Cílem je otestovat, zda pro všechny hodnoty jednoho druhu existuje výběr hodnotu druhého druhu, aby systém byl přípustný. V řeči intervalového počítání: jde nám o to zjistit, zda je systém tzv. AE řešitelný. O AE řešitelnosti se neví mnoho. Cílem projetu je adaptovat a implementovat určité postačující/nutné podmínky na řešitelnost a případně je rozšířit na úlohy s lineárními závislostmi. Programovací jazyk: Matlab/Octave + Intlab.

    Odkazy:

    1. M. Hladík. AE solutions and AE solvability to general interval linear systems. Linear Algebra Appl., 465(0):221-238, 2015.
    2. M. Hladík. Weak and strong solvability of interval linear systems of equations and inequalities. Linear Algebra Appl., 438(11):4156-4165, 2013.
    3. L. Jaulin et al. Applied Interval Analysis. With examples in parameter and state estimation, robust control and robotics. Springer, London, 2001.

  • Vizualizace množiny řešení intervalových soustav

    • Pro soustavy lineárních rovnic a nerovnic s intervalovými koeficienty neexistuje jednoznačný koncept pojmu řešení, ale existuje několik možností, jak řešení definovat. Ve většině případů je množina řešení nekonvexní polyedrická množina. Cílem práce by bylo pro různé typy soustav a pro různé typy řešení graficky znázornit množinu řešení a její hlavní charakteristiky. Zatím se umí znázorňovat jen tzv. slabá množina řešení, viz např.: příklad 3D soustavy v Intlabu.

    Odkazy:

    1. M. Hladík. AE solutions and AE solvability to general interval linear systems. Linear Algebra Appl., 465(0):221-238, 2015.
    2. M. Hladík. Weak and strong solvability of interval linear systems of equations and inequalities. Linear Algebra Appl., 438(11):4156-4165, 2013.
    3. J. Rohn. A manual of results on interval linear problems. Technical Report 1164, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague, 2012.
    4. J. Rohn. A handbook of results on interval linear problems. Technical Report 1163, Institute of Computer Science, Academy of Sciences of the Czech Republic, 2012.
    5. I. Skalna and M. Hladík. Direct and iterative methods for interval parametric algebraic systems producing parametric solutions. Numer. Linear Algebra Appl., 26(3):e2229:1-e2229:24, 2019.

  • Plná sloupcová hodnost intervalové matice

    • Regularita intervalové matice je celkem probádané téma, ale pro plnou sloupcovou hodnost obdélníkové intervalové matice je známo jen několik podmínek. Cílem práce by bylo sepsat známé výsledky, rozšířit charakterizace a různé podmínky pro regularitu na případ plné sloupcové hodnosti. Výsledné podmínky by se pak implementovaly a porovnaly numericky. Programovací jazyk: Matlab/Octave + Intlab. Další možné rozšíření je tzv. AE kvantifikace intervalových parametrů.

    Odkazy:

    1. M. Hladík. AE regularity of interval matrices. Electron. J. Linear Algebra, 33:137-146, 2018.
    2. J. Rohn. Forty necessary and sufficient conditions for regularity of interval matrices: A survey. Electron. J. Linear Algebra, 18:500-512, 2009.
    3. J. Rohn. A handbook of results on interval linear problems. Technical Report 1163, Institute of Computer Science, Academy of Sciences of the Czech Republic, 2012.
    4. S.P. Shary. On full-rank interval matrices. Numer. Anal. Appl., 7(3):241-254, 2014.

  • Kontraktor pro třídy intervalových matic

    • Buď [A] intervalová matice a P nějaká maticová vlastnost. Některé matice v [A] vlastnost P mají, jiné nikoli. Úkolem kontraktoru je ořezat intervalovou matici [A] na nějakou menší (ve smyslu inkluze) co nejvíc a tak, abychom neodstranili žádnou matici s vlastností P. Vlastnost P bude zahrnovat základní maticové vlastnosti jako je positivní semidefinitnost, singularita, M-matice, P-matice, rank-one matice či různé druhy stability. Cílem práce je navrhnout co nejefektivnější kontraktor na vybrané typy maticových tříd a implementovat kontraktor v jazyku Matlab/Octave + Intlab.

    Odkazy:

    1. G. Chabert and L. Jaulin. Contractor programming. Artif. Intell. 173(11):1079-1100, 2009.
    2. J. Garloff, D. Al-Saafin and M. Adm. Further matrix classes possessing the interval property. Reliable Computing, to appear.
    3. M. Hladík and L. Jaulin. An eigenvalue symmetric matrix contractor. Reliab. Comput., 16:27-37, 2011.
    4. K. Krejčová. Ortogonální kontraktor. bakalářská práce, MFF UK, 2013.

  • Intervalové stochastické matice a markovské řetězce [zabráno]

    • Je-li [A] intervalová stochastická matice, pak ne každá její realizace je stochastická matice (množina [A] obsahuje i nestochastické matice). Proto se zaměříme jen na podmnožinu stochastických matic, a bude nás zajímat, jaké má vlastnosti. Speciálně, jestli základní vlastnosti stochastických matic a markovských řetězců platí pro všechny (resp. pro některé) realizace. Můžeme se zaměřit na vlastnost ireducibility, výpočet stacionárních vektorů atp. Výsledné podmínky a metody by se pak implementovaly v jazyku Matlab/Octave + Intlab.

    Odkazy:

    1. P. Diamond, P. Kloeden, and A. Pokrovskii. Interval stochastic matrices: A combinatorial lemma and the computation of invariant measures of dynamical systems. J. Dyn. Diff. Equat., 7:341-364, 1995.
    2. D. Hartman, M. Hladík, and D. Říha. Computing the spectral decomposition of interval matrices and a study on interval matrix powers. Appl. Math. Comput., 403:126174:1-13, 2021.
    3. A. Rivaz, M.M. Moghadam, and S.Z. Zadeh. Doubly Stochastic Interval Matrices. Çankaya Univ. J. Sci. Eng., 12(2):12-19, 2015.

  • Topologické vlastnosti zobecněných lineárních rovnic s absolutními hodnotami

    • Zobecněné lineární rovnice s absolutními hodnotami je soustava ve tvaru Ax+B|x|=b. Množina řešení je obecně nesouvislá či nekonvexí, ale představuje afinní podprostor v každém ortantu. Cílem práce by bylo vyšetřit nutné/postačující podmínky pro různé topologické vlastnosti množiny řešení, jako je například konvexita, souvislost, omezenost, konečný počet řešení, či řešitelnost jen v nezáporném ortantu. Výsledné podmínky a metody by se pak implementovaly v jazyku Matlab/Octave + Intlab.

    Odkazy:

    1. M. Hladík. Properties of the solution set of absolute value equations and the related matrix classes. SIAM J. Matrix Anal. Appl., 44(1):175-195, 2023.

  • Testování kopositivity pomocí branch & bound [zabráno]

    • Matice A je kopositivní pokud xTAx je nezáporné pro všechny nezáporné vektory x. Navzdory jednoduché definici je NP-těžké ověřit, zda je daná matice kopositivní. Cílem práce by bylo implementovat metodu branch & bound na testování kopositivity matice. Metoda by využila Čebyševovo znormování vektorů a intervalovou analýzu pro ověřování podmínky na subregionech. Výstupem by bylo numerické testování a porovnání s jinými metodami. Programovací jazyk: Matlab + Intlab.

    Odkazy:

    1. A. Berman et al. Open problems in the theory of completely positive and copositive matrices. Electron. J. Linear Algebra 29, 46-58, 2015.
    2. I.M. Bomze. Copositive optimization - recent developments and applications. Eur. J. Oper. Res., 216:509-520, 2012.
    3. M. Dür. Copositive Programming - a Survey In: Diehl M., Glineur F., Jarlebring E., Michiels W. (eds) Recent Advances in Optimization and its Applications in Engineering, pp. 3-20, Springer, Berlin, Heidelberg, 2010.

  • Doplňování a aktualizace prvků matice porovnání

    • Matice porovnání je standardní způsob získání preferencí mezi různými objekty od uživatele. Základní úloha pak zní určit váhy jednotlivým objektům. K tomuto existuje řada metod. Práce by měla rozšířit postupy na případ, kdy neznáme všechny prvky matice resp. uživatel je zadává postupně. Program by pak měl automaticky doplňovat prázdné políčka. Stejně tak by měl zareagovat na změnu hodnot a vydat nejlepší přibližné řešení. Cílem práce je implementace těchto metod ve formě online webové aplikace.

    Odkazy:

    1. M. Hladík, Vícekriteriální optimalizace, doprovodný text, sekce 5.2.
    2. R. Hlavatý, Saaty's matrix revisited: Securing the consistency of pairwise comparisons, proceedings of 32nd International Conference Mathematical Methods in Economics MME 2014, Olomouc, 2014.
    3. T. L. Saaty, Relative measurement and its generalization in decision making. Why pairwise comparisons are central in mathematics for the measurement of intangible factors. The analytic hierarchy/network process, RACSAM - Rev. R. Acad. Cien. Serie A. Mat., 102(2):251–318, 2008.
    4. T. L. Saaty and L. G. Vargas. Models, Methods, Concepts & Applications of the Analytic Hierarchy Process. Springer, New York, second edition, 2012.


    Ryze teoretické bakalářské práce

    Co to je teoretická bakalářka a mám se toho bát? Ne, rozhodně není třeba se bát. Pokud si student vybere téma, které ho baví a věnuje tomu přiměřené úsilí, pak je riziko neúspěchu minimální. Teoretická bakalářka je typicky zaměřená na speciální problém, který ještě nikdo neřešil, nebo na rozšíření známých výsledků na větší třídu úloh. Proto když student na začátku nastuduje problematiku, tak má připravenou půdu ke zdárnému výsledku. Zde samozřejmě závisí na invenci a píli studenta, a na kousku štěstí k jak velkým výsledkům se dostane. Historie ale ukazuje, že studenti naší katedry mají dobré výsledky, leckdy i publikovatelné v odborném tisku, a také bývají úspěšní v soutěžích typu SVOČ.

  • Geometrie intervalových lineárních soustav [zabráno]

    • Množina řešení čtvercové soustavy intervalových lineárních rovnic je tvořena polyedrem, který je obecně nekonvexní, ale je konvexní v každém ortantu. Pro tuto množinu jsou známy zajímavé geometrické vlastnosti a podmínky jak se dá vyjádřit její konvexní obal, nebo kdy je automaticky konvexní. Cílem práce prozkoumat zobecnění těchto výsledků na přeurčené intervalové soustavy rovnic a na soustavy nerovnic.

    Odkazy:

    1. M. Hladík. Weak and strong solvability of interval linear systems of equations and inequalities. Linear Algebra Appl., 438(11):4156-4165, 2013.
    2. J. Rohn. Systems of linear interval equations. Linear Algebra Appl., 126(C):39-78, 1989.
    3. J. Rohn. A manual of results on interval linear problems. Technical Report 1164, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague, 2012.

  • Zobecněná Perron-Frobeniova teorie pro intervalové matice

    • Perron-Frobeniova teorie říká, že nezáporné matice mají z hlediska vlastních čísel a vlastních vektorů speciální vlastnosti. Nezápornost matice A znamená, že A leží v kuželi nezáporných směrů. Jedno z možných rozšíření uvažuje obecný kužel a zobecňuje některé výsledky pro tento případ. Cílem práce je prozkoumat tuto zobecněnou teorii, adaptovat výsledky na intervalové matice a vyjádřit podmínky na ověření předpokladů.

    Odkazy:

    1. M. Hladík. An overview of polynomially computable characteristics of special interval matrices. preprint arXiv: 1711.08732, 2017.
    2. L. Hogben. Handbook of Linear Algebra. CRC Press, Second Edition, 2014

  • Celočíselné lineární programování s intervalovými koeficienty [zabráno]

    • Lineární programování (LP) a celočíselné LP jsou základní úlohy optimalizace, používané k řešení mnoha praktických úloh. Reálná data ale jsou často odhadnuta či známa jen s určitou přesností. To vede na úlohy s intervalovými daty. Zatímco intervalové LP je předmětem zkoumání řadu let, o celočíselném se ví mnohem méně. Cílem práce je prozkoumat, které výsledky z intervalového LP platí pro celočíselný případ a které již nikoliv. U těch druhých se pokusit je adaptovat na celočíselné prostředí.

    Odkazy:

    1. M. Hladík. Interval linear programming: A survey. In Zoltán Ádám Mann, editor, Linear Programming - New Frontiers in Theory and Applications, pp. 85–120, Nova Science Publishers, New York, 2012.
    2. J. Rohn. A manual of results on interval linear problems. Technical Report 1164, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague, 2012.
    3. J. Rohn. A handbook of results on interval linear problems. Technical Report 1163, Institute of Computer Science, Academy of Sciences of the Czech Republic, 2012.

  • Zobecněné lineární rovnice s absolutními hodnotami a singulárními maticemi

    • Zobecněné lineární rovnice s absolutními hodnotami je soustava ve tvaru Ax+B|x|=b. Vyřešit tuto soustavu nebo zjistit zda je řešitelná je tzv. NP-těžké. Existují však různé podmínky, které garantují řešitelnost i metody, které v mnohých případech rozumně fungují. Cílem práce by bylo zaměřit se na případ, kdy matice A,B jsou singulární. V této situaci některé podmínky selhávají, takže úkolem by bylo je adaptovat na naši situaci. Singularita matic by také mohla umožnit zredukovat dimenzi celého problému. Zajímavé by bylo prošetřit použití tzv. znaménkové Gaussovy eliminace.

    Odkazy:

    1. M. Hladík and M. Zamani. Absolute Value Programming. In P.M. Pardalos and O. Prokopyev, Encyclopedia of Optimization, third edition, to appear, 2022.
    2. O. L. Mangasarian and R. R. Meyer. Absolute value equations.. Linear Algebra Appl., 419(2):359-367, 2006.
    3. M. Radons and S.M. Rump. Convergence results for some piecewise linear solvers. Optimization Letters. in presss, 2022.
    4. S. Wu and S. Shen. On the unique solution of the generalized absolute value equation. Optimization Letters, 15:2017-2024, 2021.


    Diplomové práce

    Tématicky především z oblasti lineární algebry, intervalové analýzy a optimalizace. Některá témata jsou v SISu. Další navrhovaná témata (můžete přijít i s vlastním tématem):

  • Verifikace v lineárním programování

    • Používání floating-point aritmetiky vede k zaokrouhlovacím chybám a v důsledku toho mohou solvery na lineární programování dávat chybné výsledky. Verifikační metody jsou postupy, které dokážou potvrdit optimalitu vypočítaného řešení (resp. optimální báze) vhledem k dané přesnosti. Cílem práce by bylo zmapovat verifikaci v lineárním programování, porovnat a případně navrhnout vylepšení. Předpokládá se i implementace ve vhodném prostředí - nejspíše v Matlabu s použitím Intlabu.

    Odkazy:

    1. Christian Jansson. Rigorous Lower and Upper Bounds in Linear Programming, SIAM J. Optim. 14(3): 914-935, 2004.
    2. Arnold Neumaier and Oleg Shcherbina. Safe bounds in linear and mixed-integer linear programming, Math. Program., Ser. A, 99(2):283-296, 2004.
    3. Siegfried M. Rump. Verification methods: Rigorous results using floating-point arithmetic, Acta Numerica 19: 287-449, 2010.
    4. Jiří Rohn. VERSOFT: Verification software in MATLAB / INTLAB, version 10, 2009.
    5. Christian Keil and Christian Jansson. Computational Experience with Rigorous Error Bounds for the Netlib Linear Programming Library , Reliab. Comput. 12(4): 303-321, 2006.
    6. Christian Keil. Lurupa - Rigorous Error Bounds in Linear Programming, Dagstuhl Seminar Proceedings 05391, 2006.

  • Intervalová maticová norma

    • Jsou známy různé způsoby jak rozšířit maticové normy na intervalové matice. Cílem této práce by bylo porovnat různé normy mezi sebou, jak moc je těsná ekvivalence mezi nimi, zjistit jejich vlasnosti (konsistence, výpočetní složitost atp.). Zajímavým rozšířením by bylo zobecnění norem tak, aby měly intervalovou hodnotou.

    Odkazy:

    1. R. Farhadsefat, J. Rohn and T. Lotfi. Norms of interval matrices. Technical Report No. 1122, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague 2011.
    2. Behnam Hashemi and Hanieh Tavakolipour. A non-induced interval matrix norm. Reliable Computing 18, 144-146, 2013.
    3. Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University, 1985.

  • Exponenciála s intervalovou maticí

    • Exponent s maticí je definován přirozeně pomocí Taylorovy řady jako matice eA=∑k=0∞Ak/k!. Cílem je určit co nejlepší dolní a horní odhady na prvky eA pokud prvky matice A perturbujeme v rámci předem daných intervalů. Motivace tohoto problému pochází v mikro-robotiky, vzniká při hledání robustního řešení v teorii řízení robota.

    Odkazy:

    1. Micky Rakotondrabe, homepage.
    2. Alexandre Goldsztejn. On the Exponentiation of Interval Matrices, arXiv, 2009.
    3. M. Althoff, O. Stursberg, and M. Buss. Reachability analysis of linear systems with uncertain parameters and inputs. In Proc. of the 46th IEEE Conference on Decision and Control, 726-732, 2007.
    4. E.P. Oppenheimer and A.N. Michel. Application of Interval Analysis Techniques to Linear Systems. II. The Interval Matrix Exponential Function. IEEE Trans. Circuits Syst., 35(10):1230-1242, 1988.

  • Číslo podmíněnosti ve vícekriteriálním lineárním programování

    • Číslo podmíněnosti v optimalizaci kvantitativně udává, jak moc je daná úloha blízko "špatně podmíněné" úloze, tj. úloze, která je nepřípustná, neomezená či jinak nestabilní. Jiný přístup je měřit citlivost optimální hodnoty při lokální změně dat. Cílem práce je navrhnout a porovnat vhodné koncepty pro číslo podmíněnosti ve vícekriteriálním lineárním programování, případně i v kontextu výběru Pareto-optimálního řešení. Součástí práce by mohla být i analýza složitosti jednotlivých přístupů či alespoň diskuse algoritmického hlediska.

    Odkazy:

    1. D. Cheung, F. Cucker, and J. Peña. Unifying condition numbers for linear programming. Math. Oper. Res., 28(4):609-624, 2003.
    2. R. M. Freund and J. R. Vera. On the complexity of computing estimates of condition measures of a conic linear system. Math. Oper. Res., 28(4):625-648, 2003.
    3. M. Hladík. On relation of possibly efficiency and robust counterparts in interval multiobjective linear programming. In A. Sforza and C. Sterle, editors, Optimization and Decision Science: Methodologies and Applications, volume 217 of Springer Proceedings in Mathematics & Statistics, pages 335-343. Springer, Cham, 2017.
    4. J. Rohn. On sensitivity of the optimal value of a linear program. Ekonom.-Mat. Obzor, 25(1):105-107, 1989

  • Optimální partitioning a optimální support set invariance v intervalovém lineárním programování

    • Stabilita lineárních programů se tradičně studuje na základě zachování optimální báze. Není to však jediný možný přístup. Alternativně lze studovat zachování optimálního partitioningu nebo optimálního support setu. Práce by byla zaměřená na analýzu nových typů invariancí pro případ, že vstupní hodnoty lineárních programů se pohybují v rámci zadaných intervalů. Cílem je charakterizovat či navrhnout podmínky pro tyto invariance a prozkoumat speciální případy, které by mohly být řešitelné efektivně.

    Odkazy:

    1. M. Hladík. Multiparametric linear programming: support set and optimal partition invariancy. Eur. J. Oper. Res., 202(1):25-31, 2010
    2. M. Hladík. How to determine basis stability in interval linear programming. Optim. Lett., 8(1):375-389, 2014
    3. O. Král. Metody na výpočet optimálních hodnot intervalového lineárního programování. diplomová práce, MFF UK, 2020
    4. N. Mehanfar, A. Ghaffari-Hadigheh. Optimal partition invariancy in multi-parametric linear optimization. J. Math. Model., in press, 2022

  • Nejkratší cesta v grafu s více intervalovými kritérii [zabráno]

    • Hledání nejkratší cesty v grafu je známá úloha. My se ale zaměříme na případ, kdy máme více kritérií, navíc délky hran nejsou přesná čísla, ale známe jen jejich intervalový rozsah. Cílem práce je navrhnout a prozkoumat robustní řešení takovýchto úloh, například využít konceptu nutně eficientních řešení. Z algoritmického hlediska nás pak zajímá design příslušných metod a analýza jejich složitosti.

    Odkazy:

    1. I. Averbakh and V. Lebedev. Interval data minmax regret network optimization problems. Discrete Appl. Math., 138(3):289–301, 2004
    2. M. Hladík. Complexity of necessary efficiency in interval linear programming and multiobjective linear programming. Optim. Lett., 6(5):893-899, 2012
    3. H. Yaman. Essays on some combinatorial optimization problems with interval data. Department of Industrial Engineering, Bilkent University, 1999

  • Porovnání metod intervalového lineárního programování

    • Úlohou intervalového lineárního programování rozumíme množinu úloh lineárního programování, v nichž parametry nabývají hodnot z daných intervalů. Jedním z cílů tohoto problému je najít extrémní meze, ve kterých se nabývají optimální hodnoty jednotlivých lineárních programů. To lze řešit různými metodami, např. dekompozicí na exponenciálně mnoho lineárních programů, metodami globální optimalizace či nehladké nekonvexní optimalizace. Cílem práce je implementace a porovnání základních metod s využitím vhodných dolních a horních odhadů na meze optimálních hodnot. Programovací jazyk: Matlab/Octave + Intlab. Tato práce by byla více programovací a implementační.

    Odkazy:

    1. E. Hansen and G.W. Walster. Global optimization using interval analysis. 2nd ed., Marcel Dekker, 2004.
    2. M. Hladík. Interval linear programming: A survey. In Zoltán Ádám Mann, editor, Linear Programming - New Frontiers in Theory and Applications, pp. 85–120, Nova Science Publishers, New York, 2012.
    3. M. Hladík. On approximation of the best case optimal value in interval linear programming. Optim. Lett., 8(7):1985–1997, 2014.
    4. M. Hladík. Weak and strong solvability of interval linear systems of equations and inequalities. Linear Algebra Appl., 438(11):4156–4165, 2013.

  • Silné Nashovo ekvilibrium v intervalových maticových hrách

    • Nashovo ekvilibrium je takový rovnovážný výběr strategií, že žádnému hráči se nevyplatí jeho stretegii změnit, protože by si pohoršil. Silné Nashovo ekvilibrium je pak taková situace, že ani žádná koalice hráčů si nepolepší. Polepšením výplaty koalice myslíme, že by se mohli domluvit mezi sebou, změnit stretegii a každý ze členů koalice by měl větší výplatu. Zatímco Nashovo ekvilibrium existuje, silné již existovat nemusí. Cílem práce je prozkoumat silné Nashovo ekvilibrium pro hry s intervalovými maticemi, navrhnout postup jak určit, že existuje instance se silným ekvilibriem (resp., že všechny instance jej mají).

    Odkazy:

    1. R. Aumann. Acceptable points in general cooperative n-person games, Acceptable points in general cooperative n-person games, in "Contributions to the Theory of Games IV", Princeton Univ. Press, Princeton, N.J., 1959.
    2. M. Hladík. Interval valued bimatrix games. Kybernetika, 46(3):435-446, 2010.
    3. B. Kubica, A. Wozniak. Interval methods for computing strong Nash equilibria of continuous games. Decision Making in Manufacturing and Services, 9(1), 63-78, 2016.
    4. R. Nessah, G. Tian. On the existence of strong Nash equilibria. J. Math. Anal. Appl., 414(2), 871-885.


    Další užitečné odkazy