6533b85ffe1ef96bd12c24f5

RESEARCH PRODUCT

Certifying feasibility and objective value of linear programs

Ernst AlthausErnst AlthausDaniel Dumitriu

subject

Set (abstract data type)Mathematical optimizationLinear programmingApplied MathematicsManagement Science and Operations ResearchValue (mathematics)Industrial and Manufacturing EngineeringSoftwareMathematics

description

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

yearjournalcountryeditionlanguage
2012-07-01Operations Research Letters
https://doi.org/10.1016/j.orl.2012.03.004