Kevin Cheung 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 … Read more
Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from programming or algorithmic errors, motivating the desire for a way to produce independently verifiable certificates of claimed results. Due to the complex nature of … Read more
We introduce a family of subadditive functions called Generator Functions for mixed integer linear programs. These functions were previously defined for pure integer programs with non-negative entries by Klabjan [13]. They are feasible in the subadditive dual and we show that they are enough to achieve strong duality. Several properties of the functions are shown. … Read more