Název:
Experimentální analýza simplexové metody na problému multikomoditního toku
Překlad názvu:
Experimental analysis of the simplex method for the multicommodity flow problem
Autoři:
Kubek, Dávid ; Koutecký, Martin (vedoucí práce) ; Borgwardt, Steffen (oponent) Typ dokumentu: Bakalářské práce
Rok:
2023
Jazyk:
cze
Abstrakt: [cze][eng] Tato práce se zabývá problémem multikomoditního toku minimální ceny (MMCF). Naším cílem je přispět k hledání kombinatorického algoritmu pro MMCF. Použili jsme simplexovou metodu k experimentálnímu prozkoumání vrcholů polyedru přípustných řešení na sadě veřejně dostupných instancí MMCF. K dosažení tohoto cíle jsme vyvinuli řešič, který je schopen sledovat řešení v každé iteraci algoritmu v přesné aritmetice; tato funkcionalita ne- byla k dispozici v existujících řešičích. Zaměřujeme se na zlomkovost MMCF instancí a vliv volby pivotovacího pravidla, zejména zda je zlomkovost expo- nenciální nebo polynomiální s ohledem na rostoucí dimenzi problému. Naše zjištění naznačují, že zlomkovost vykazuje exponenciální chování.This thesis investigates the multicommodity min-cost flow (MMCF) prob- lem. We aim to contribute to the search for a combinatorial algorithm for MMCF. The simplex method is employed to examine the vertices of the poly- hedron of feasible solutions using experimental analysis on a set of publicly available MMCF instances. To achieve this, we develop a solver capable of tracing solutions in each iteration of the algorithm in exact arithmetic, which was not available in existing solvers. Our investigation focuses on the frac- tionality of MMCF problems and the impact of different pivoting rules, par- ticularly whether the fractionality is exponential or polynomial with respect to increasing dimension. Our findings suggest that fractionality exhibits ex- ponential behavior.
Klíčová slova:
simplex|experiment|tokový problém|linearární programování; simplex|linear programming|experiment|flow problem