Original title: Experimentální analýza škálovacích metod pro lineární programování
Translated title: Experimental Analysis of Scaling Methods for LP
Authors: Komárek, Jakub ; Koutecký, Martin (advisor) ; Vegh, Laszlo (referee)
Document type: Bachelor's theses
Year: 2023
Language: eng
Abstract: [eng] [cze]
In his recent work, Dadush et al. introduced the condition number κ for constraint matrices of linear programming and devised an algorithm to approximately optimize κ by scaling columns of the constraint matrix. We follow up on his work by implementing this scaling algorithm. We have used our implementation to obtain an approximate rescaling of some linear programming instances available from public datasets. Finally, this work shows results of experiments evaluating the effects of the obtained rescalings on the runtime of some available linear programming solvers. 1 Ve své nedávné práci, Dadush představil kondiční číslo κ pro matice podmínek prob- lémů lineárního programování a navrhl algoritmus pro aproximaci optimálního škálování sloupců matice podmínek. My pokračujeme v jeho práci implementací navrženého algo- ritmu a experimenty s jeho výsledky v praxi. 1
Keywords: Linear programming|scaling|circuit imbalance measure; Lineární programování|škálová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/184426

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


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