Název: Experimentální analýza škálovacích metod pro lineární programování
Překlad názvu: Experimental Analysis of Scaling Methods for LP
Autoři: Komárek, Jakub ; Koutecký, Martin (vedoucí práce) ; Vegh, Laszlo (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2023
Jazyk: eng
Abstrakt: [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
Klíčová slova: Lineární programování|škálování; Linear programming|scaling|circuit imbalance measure

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/184426

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-534005


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce