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:
- Optimalizace dopravy a logistiky (např. rozvrhování tras a dodávek),
- Plánování výroby (minimalizace nákladů, efektivní využití zdrojů),
- Finanční modelování a řízení portfolia,
- Energetika (např. optimalizace sítí a využití obnovitelných zdrojů),
- 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 (konkrétní zadání se domluví individuálně se studentem):
- Seznámit se s presolvingovými technikami v kontextu LP (např. fixed variable elimination, constraint aggregation, bound tightening, sparsity detection).
- Vybrat vhodné techniky pro paralelizaci.
- Navrhnout a implementovat jejich efektivní paralelní verzi pro GPU v knihovně TNL (tnl-project.org).
- 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:
- Získá znalosti o důležité, prakticky používané oblasti optimalizace.
- Získá zkušenosti s návrhem paralelních algoritmů a programováním GPU.
- Bude pracovat na tématu, které má reálné využití ve vědě i průmyslu.
Zdroje:
- Achterberg, Tobias. Constraint integer programming. Diss. 2007.
- 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.
