MIP-DD: Delta Debugging for Mixed-Integer Programming Solvers

References

• Achterberg T (2007) Constraint integer programming. PhD thesis, Technische Universität Berlin, Berlin.Google Scholar
• Achterberg T, Bixby RE, Gu Z, Rothberg E, Weninger D (2019) Presolve reductions in mixed integer programming. INFORMS J. Comput. 32(2):473–506.Link, Google Scholar
• Amaldi E, Pfetsch ME, Trotter LE Jr (2003) On the maximum feasible subsystem problem, IISs and IIS-hypergraphs. Math. Programming 95:533–554.Crossref, Google Scholar
• Bolusani S, Besançon M, Bestuzheva K, Chmiela A, Dionísio J, Donkiewicz T, van Doornmalen J, et al. (2024) The SCIP optimization suite 9.0. Preprint, submitted February 27, https://arxiv.org/abs/2402.17702.Google Scholar
• Brummayer R, Biere A (2009) Fuzzing and delta-debugging SMT solvers. Dutertre B, Strichman O, eds. SMT ‘09 Proc. 7th Internat. Workshop Satisfiability Modulo Theories (Association for Computing Machinery, New York), 1–5.Google Scholar
• Brummayer R, Lonsing F, Biere A (2010) Automated testing and debugging of SAT and QBF solvers. Strichman O, Szeider S, eds. Theory Appl. Satisfiability Testing SAT 2010 (Springer, Berlin), 44–57.Google Scholar
• Cheung KKH, Gleixner A, Steffy DE (2017) Verifying integer programming results. Eisenbrand F, Koenemann J, eds. Integer Programming Combin. Optim. 19th Internat. Conf. IPCO 2017 (Springer, Cham, Switzerland), 148–160.Google Scholar
• Chinneck JW (1997) Finding a useful subset of constraints for analysis in an infeasible linear program. INFORMS J. Comput. 9(2):164–174.Link, Google Scholar
• Chinneck JW, Dravnieks EW (1991) Locating minimal infeasible constraint sets in linear programs. INFORMS J. Comput. 3(2):157–168.Link, Google Scholar
• Cook W, Koch T, Steffy DE, Wolter K (2013) A hybrid branch-and-bound approach for exact rational mixed-integer programming. Math. Programming Comput. 5(3):305–344.Crossref, Google Scholar
• Eifler L, Gleixner A (2023) A computational status update for exact rational mixed integer programming. Math. Programming 197:793–812.Crossref, Google Scholar
• Eifler L, Gleixner A (2024) Safe and verified Gomory mixed-integer cuts in a rational mixed-integer program framework. SIAM J. Optim. 34(1):742–763.Crossref, Google Scholar
• European Parliament and Council of the European Union (2016) Regulation (EU) 2016/679 of the European Parliament and of the Council. Accessed March 24, 2025, https://data.europa.eu/eli/reg/2016/679/oj.Google Scholar
• Exact SCIP (2024) A development version of SCIP with exact rational arithmetic. https://github.com/scipopt/scip/tree/exact-rational.Google Scholar
• Gleeson J, Ryan J (1990) Identifying minimally infeasible subsystems of inequalities. ORSA J. Comput. 2(1):61–63.Link, Google Scholar
• Gleixner A, Gottwald L, Hoen A (2023) PaPILO: A parallel presolving library for integer and linear programming with multiprecision support. INFORMS J. Comput. 35(6):1329–1341.Link, Google Scholar
• Gleixner A, Hendel G, Gamrath G, Achterberg T, Bastubbe M, Berthold T, Christophel PM, et al. (2021) MIPLIB 2017: Data-driven compilation of the 6th mixed-integer programming library. Math. Programming Comput. 13:443–490.Crossref, Google Scholar
• Goldberg D (1991) What every computer scientist should know about floating-point arithmetic. ACM Comput. Surveys 23(1):5–48.Crossref, Google Scholar
• Gomory RE (1958) Outline of an algorithm for integer solutions to linear program. Bull. Amer. Math. Soc. 64(5):275–278.Crossref, Google Scholar
• Gomory RE (1963) An algorithm for integer solutions of linear programs. Graves R, Wolfe P, eds. Recent Advances in Mathematical Programming (McGraw-Hill, New York), 269–302.Google Scholar
• Hoen A, Kamp D, Gleixner A (2025) MIP-DD: Delta debugging for mixed integer programming solvers. http://dx.doi.org/10.1287/ijoc.2024.0844.cd, https://github.com/INFORMSJoC/2024.0844.Google Scholar
• Kaufmann D, Biere A (2022) Fuzzing and delta debugging and-inverter graph verification tools. Kovács L, Meinke K, eds. Tests Proofs TAP 2022 (Springer, Cham, Switzerland), 69–88.Google Scholar
• Klotz E (2014) Identification, assessment, and correction of ill-conditioning and numerical instability in linear and integer programs. INFORMS Tutorials Oper. Res. 54–108.Google Scholar
• Koch T, Berthold T, Pedersen J, Vanaret C (2022) Progress in mathematical programming solvers from 2001 to 2020. EURO J. Comput. Optim. 10:1–18.Crossref, Google Scholar
• Margot F (2010) Symmetry in integer linear programming. Jünger M, Liebling TM, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G, Wolsey LA, eds. 50 Years of Integer Programming 1958–2008 (Springer, Berlin), 647–686.Crossref, Google Scholar
• Niemetz A, Biere A (2013) ddSMT: A delta debugger for the SMT-LIB v2 format. Bruttomesso R, Griggio A, eds. Proc. 11th Internat. Workshop Satisfiability Modulo Theories SMT 2013 Affiliated 16th Internat. Conf. Theory Appl. Satisfiability Testing SAT 2013, 36–45.Google Scholar
• Paxian T, Biere A (2023) Uncovering and classifying bugs in MaxSAT solvers through fuzzing and delta debugging. Järvisalo M, Le Berre D, eds. Proc. 14th Internat. Workshop Pragmatics SAT Co-Located 26th Internat. Confer. Theory Appl. Satisfiability Testing (SAT 2003), 59–71.Google Scholar
• Savelsbergh MWP (1994) Preprocessing and probing techniques for mixed integer programming problems. ORSA J. Comput. 6(4):445–454.Link, Google Scholar
• Steffy DE (2011) Topics in exact precision mathematical programming. PhD thesis, Georgia Institute of Technology, Atlanta.Google Scholar
• Zeller A (1999) Yesterday, my program worked. Today, it does not. Why? Nierstrasz O, Lemoine M, eds. Software Engrg. ESEC/FSE ‘99 (Springer, Berlin), 253–267.Google Scholar