Why MILP Solvers Can't Be Trusted (Even When They're Right)

Do mixed-integer linear programming (MILP) solvers tell the truth? Even when a solver returns the correct optimal solution, does it make illegal decisions along the branch-and-bound search tree due to floating-point rounding errors? In this episode of Solver Reading Club, we do a deep dive into solver internals to explore how numerical tolerances impact the correctness of mathematical optimization solvers. We unpack a fascinating paper from the Zuse Institute Berlin that audits SCIP's internal decisions using pure exact rational arithmetic. We cover the taxonomy of solver errors (weak vs. strong), discuss ways to catch those errors, analyze the impact of those errors on benchmark problems, and explain the counterintuitive reason why tightening solver tolerances doesn’t work as expected. Paper Details: Title: Analyzing the Numerical Correctness of Branch-and-Bound Decisions for Mixed-Integer Programming Authors: Alexander Hoen and Ambros Gleixner Github repo: https://github.com/alexhoen/bnbanalyzer If you are an Operations Research (OR) student, professional, or developer interested in mathematical programming, and solver architecture, this paper is a must-read. Timestamps 0:00 Intro 3:05 Types of errors 11:14 How to catch the errors 16:10 Benchmark results 19:49 What we can do? #OperationsResearch #MathematicalOptimization #MILP #BranchAndBound #SolverInternals #SCIP #DataScience #IndustrialEngineering #LinearProgramming Free linear programming course:    • Linear Programming Basics   Buy me a coffee: https://www.buymeacoffee.com/krooonal