Safe bounds in linear and mixed-integer linear programming

Abstract. Current mixed-integer linear programming solvers are based on linear programming routines that use °oating-point arithmetic. Occasionally, this leads to wrong solutions, even for problems where all coe±cients and all solution components are small integers. An example is given where many state-of-the-art MILP solvers fail. It is then shown how, using directed rounding and interval arithmetic, cheap pre- and postprocessing of the linear programs arising in a branch-and-cut framework can guarantee that no solution is lost, at least for mixed-integer programs in which all variables can be bounded rigorously by bounds of reasonable size