DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2024.18

Experimental Analysis of LP Scaling Methods Based on Circuit Imbalance Minimization

Authors: Jakub Komárek and Martin Koutecký

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract

Linear programming (LP) is a fundamental problem with rich theory and wide applications. A ubiquitous technique in LP is scaling, where the input instance is transformed in some way to make its solution easier. Dadush et al. [STOC '20] have recently devised an algorithm which scales the columns of the constraint matrix of a linear program in a way that aims to minimize the circuit imbalance measure, a matrix condition number of growing theoretical interest. They show that this rescaling achieves favorable theoretical guarantees for certain LP algorithms. We follow up on their work in an experimental manner. First, we have implemented their algorithm, overcoming several engineering obstacles. Next, we have used our implementation to obtain a rescaling of 142 publicly available instances. Finally, we have performed experiments evaluating the effects of the obtained rescalings on the runtime of real-world LP solvers, and we have evaluated their quality with regard to the circuit imbalance measure.

Cite as

Jakub Komárek and Martin Koutecký. Experimental Analysis of LP Scaling Methods Based on Circuit Imbalance Minimization. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 18:1-18:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{komarek_et_al:LIPIcs.SEA.2024.18,
  author =	{Kom\'{a}rek, Jakub and Kouteck\'{y}, Martin},
  title =	{{Experimental Analysis of LP Scaling Methods Based on Circuit Imbalance Minimization}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{18:1--18:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.18},
  URN =		{urn:nbn:de:0030-drops-203832},
  doi =		{10.4230/LIPIcs.SEA.2024.18},
  annote =	{Keywords: Linear programming, scaling, circuit imbalance measure}
}

Search Results

Documents authored by Komárek, Jakub

Experimental Analysis of LP Scaling Methods Based on Circuit Imbalance Minimization

Abstract

Cite as

Thanks for your feedback!

Could not send message