Numerically safe lower bounds for the Capacitated Vehicle Routing Problem


Floating point calculations are intrinsically subject to error. In the context of integer programming, these errors may lead to incorrect decisions in the branch-and-bound process, ultimately leading to incorrect optimal solutions. The typical approach is to use heuristic rules to mitigate those issues. This paper proposes a computationally efficient way to guarantee correctness of integer programming bounding decisions within the context of branch-and-price formulations of the vehicle routing problem.

INFORMS Journal on Computing, vol 29(3), pp.544-557, 2017