Original title:
Experimentální analýza simplexové metody na problému multikomoditního toku
Translated title:
Experimental analysis of the simplex method for the multicommodity flow problem
Authors:
Kubek, Dávid ; Koutecký, Martin (advisor) ; Borgwardt, Steffen (referee) Document type: Bachelor's theses
Year:
2023
Language:
cze Abstract:
[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.
Keywords:
simplex|linear programming|experiment|flow problem; simplex|experiment|tokový problém|linearární programování
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/183073