Paralelní předzpracování úloh v lineárním programování
| advisor: | doc. Ing. Tomáš Oberhuber, Ph.D. |
| e-mail: | show e-mail |
| type: | bachelor thesis, master thesis |
| branch of study: | MI_MM, MI_AMSM, MINF |
| key words: | lineární programování, GPU |
| description: | Lineární programování (LP) představuje jeden z nejdůležitějších nástrojů moderní aplikované matematiky, informatiky a inženýrství. Denně se využívá v oblastech jako je: 1. Optimalizace dopravy a logistiky (např. rozvrhování tras a dodávek), 2. Plánování výroby (minimalizace nákladů, efektivní využití zdrojů), 3. Finanční modelování a řízení portfolia, 4. Energetika (např. optimalizace sítí a využití obnovitelných zdrojů), 5. Strojové učení a data science (např. SVM, robustní regrese). V reálných aplikacích však často čelíme velmi rozsáhlým úlohám se statisíci až miliony proměnných a omezení. Pro tyto případy klasické metody (např. Simplexová metoda nebo metoda vnitřního bodu) selhávají kvůli náročnosti na paměť i výpočetní čas. Moderní přístup představují metody prvního řádu jako je Primal–Dual Hybrid Gradient (PDHG), které umožňují řešit i extrémně rozsáhlé úlohy. Zvláště efektivní jsou v kombinaci s akcelerací pomocí grafických procesorů (GPU). Předzpracování (tzv. presolving) je klíčovou součástí řešení lineárních programovacích úloh. Jeho cílem je zjednodušit úlohu dříve, než je předána samotnému solveru – například odstraněním redundantních omezení, fixací proměnných, škálováním nebo detekcí degenerací. Kvalitní presolving může dramaticky snížit velikost úlohy i výpočetní čas. Zatímco samotné řešiče založené na PDHG již dokáží využít GPU, presolving bývá stále prováděn sekvenčně na CPU a jeho provedení pak trvá neúměrně dlouho vzhledem k následujícímu samotnému výpočtu. Cílem této práce je prozkoumat možnosti paralelizace vybraných presolvingových technik a jejich implementace na GPU, s důrazem na masivní paralelismus a efektivní práci s pamětí. Cíle práce: 1. Seznámit se s presolvingovými technikami v kontextu LP (např. fixed variable elimination, constraint aggregation, bound tightening, sparsity detection). 2. Vybrat vhodné techniky pro paralelizaci. 3. Navrhnout a implementovat jejich efektivní paralelní verzi pro GPU v knihovně TNL. 4. Otestovat na reálných LP úlohách (např. z knihoven Netlib, MIPLIB) a porovnat s existujícími nástroji (např. presolving ve SCIP nebo HiGHS). Přínosy pro studenta: 1. Získá znalosti o důležité, prakticky používané oblasti optimalizace. 2. Získá zkušenosti s návrhem paralelních algoritmů a programováním GPU. 3. Bude pracovat na tématu, které má reálné využití ve vědě i průmyslu. |
| references: | 1. Achterberg, Tobias. Constraint integer programming. Diss. 2007. 2. Achterberg, Tobias, et al. \"Constraint integer programming: A new approach to integrate CP and MIP.\" International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008. |
| last update: | 19.05.2025 10:58:47 |
administrator for this page:
Ľubomíra Dvořáková | last update: 09/12/2011