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

Permalink: http://www.nusl.cz/ntk/nusl-532191


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses