6533b86dfe1ef96bd12c93ce

RESEARCH PRODUCT

Fast and Accurate Bounds on Linear Programs

Daniel DumitriuErnst Althaus

subject

Set (abstract data type)Mathematical optimizationInequalityLinear programmingmedia_common.quotation_subjectLinear-fractional programmingmedia_commonMathematics

description

We present an algorithm that certifies the feasibility of a linear program while using rational arithmetic as little as possible. Our approach relies on computing a feasible solution of the linear program that is as far as possible from satisfying an inequality at equality. To realize such an approach, we have to detect the set of inequalities that can only be satisfied at equality. Compared to previous approaches for this problem our algorithm has a much higher rate of success.

yearjournalcountryeditionlanguage
2009-01-01
https://doi.org/10.1007/978-3-642-02011-7_6