MIP-DD: Delta Debugging for Mixed-Integer Programming Solvers
提出首个开源Delta调试工具MIP-DD，通过简化MIP实例来隔离求解器错误，已成功帮助SCIP求解器修复24个bug，将复杂问题简化为少量变量和约束，便于手动追踪。
The recent performance improvements in mixed-integer programming (MIP) have been accompanied by a significantly increased complexity of the codes of MIP solvers, which poses challenges in fixing implementation errors. In this paper, we introduce MIP-DD, a solver-independent tool, which to the best of our knowledge is the first open-source delta debugger for MIP. Delta debugging is a hypothesis-trial-result approach to isolate the cause of a solver failure. MIP-DD simplifies MIP instances while maintaining the undesired behavior. Preliminary versions already supported and motivated fixes for many bugs in the SCIP releases 8.0.1 to 8.1.1. In these versions, MIP-DD successfully contributed to 24 out of all 51 documented MIP-related bugfixes even for some long-known issues. In selected case studies we highlight that instances triggering fundamental bugs in SCIP can typically be reduced to a few variables and constraints in less than an hour. This makes it significantly easier to manually trace and check the solution process on the resulting simplified instances. A promising future application of MIP-DD is the analysis of performance bottlenecks, which could very well benefit from simple adversarial instances. History: Accepted by Ted Ralphs, Area Editor for Software Tools. Funding: This work was partially supported by the German Research Foundation [Grant RA 1033/3-1] and the German Federal Ministry of Education and Research [Grant 05M20ZBM]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0844 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0844 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .