Experimental Analysis of LP Scaling Methods Based on Circuit Imbalance Minimization

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10493517" target="_blank" >RIV/00216208:11320/24:10493517 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.4230/LIPIcs.SEA.2024.18" target="_blank" >https://doi.org/10.4230/LIPIcs.SEA.2024.18</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.SEA.2024.18" target="_blank" >10.4230/LIPIcs.SEA.2024.18</a>

Result language

angličtina

Original language name

Experimental Analysis of LP Scaling Methods Based on Circuit Imbalance Minimization

Original language description

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&apos;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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GA22-22997S" target="_blank" >GA22-22997S: Efficient and Realistic Models in Computational Social Choice</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2024

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Leibniz International Proceedings in Informatics, LIPIcs

ISBN

978-3-95977-325-6

ISSN

—

e-ISSN

—

Number of pages

21

Pages from-to

1-21

Publisher name

Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Place of publication

Dagstuhl

Event location

23.7.2024

Event date

Jul 26, 2024

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—