期刊
OPERATIONS RESEARCH LETTERS
卷 40, 期 4, 页码 292-297出版社
ELSEVIER
DOI: 10.1016/j.orl.2012.03.004
关键词
Linear programming; Certified feasibility; Safe bounds; Rational arithmetic
资金
- German Research Council (DFG) as part of the Transregional Collaborative Research Center Automatic Verification and Analysis of Complex Systems [SFB/TR 14 AVACS]
- German Research Council (DFG) as part of its priority program SPP 1307: Algorithm Engineering [AL 1139/1-2]
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. (c) 2012 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据