Bound Propagation for Linear Inequalities Revisited

In 2011, Korovin and Voronkov (Proceedings of the 23rd International Conference on Automated Deduction, vol. 6803 of Lecture Notes in Computer Science, pp. 369-383) proposed a method based on bound propagation for solving systems of linear inequalities. In this paper, an alternate description of their algorithm which also incorporates an addition that returns a certificate of infeasibility in the case when the system has no solution is provided. It is shown that the running time of the algorithm is exponential in the number of variables in the worst case. A method for using the algorithm to solve linear programming problems without having to specify the dual is proposed.

Article

Download

View PDF