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).
Existující implementace řešiče lineárního programování metodou Primal–Dual Hybrid Gradient (PDLP) v knihovně TNL psaná v jazyce C++ nabízí vysoký výpočetní výkon a efektivitu, zejména na GPU. Její využití je však zatím omezené na technické uživatele schopné psát C++ kód a připravit vstupy ve vlastním formátu.
Cílem práce je umožnit použití vlastního řešiče založeného na metodě Primal–Dual Hybrid Gradient (PDHG) v jazyce C++ jako backend pro populární modelovací balíky jako CVXPY pro Python nebo Jump pro Julii. Solver bude orientován na řešení rozsáhlých úloh lineárního programování s pomocí akcelerace na GPU.
Cíle práce (konkrétní zadání se domluví individuálně se studentem):
- Seznámit s typickými úlohami lineráního programování.
- Seznámit se s nástroji pybind11 nebo CxxWrap.jl pro propojení C++ s jazyky. Python a Julia.
- Vytvořit v Pythonu (Julii) rozhraní, které umožní přístup k řešiči PDLP.
- Integrovat řešič do CVXPY v Pythou nebo JuMP v Julii.
- Ověřit funkčnost na příkladech a porovnat s jinými solvery (např. HiGHS, COPT).
Přínosy pro studenta:
- Získá znalosti o důležité, prakticky používané oblasti optimalizace.
- Získá zkušenosti s propojováním vyšších programovacích jazyků jako Python a Julia s C++.
- Bude pracovat na tématu, které má reálné využití ve vědě i průmyslu.
Zdroje:
- Bertsimas, Dimitris, and John N. Tsitsiklis. Introduction to linear optimization. Vol. 6. Belmont, MA: Athena scientific, 1997.
- CVXPY - https://www.cvxpy.org/
- JuMP - https://jump.dev/JuMP.jl/stable/
