Exact Integer Programming
Description
Prof. Dr. Dr. h. c. Martin Grötschel; Zuse Institut Berlin
Project website
Available solvers for mixed-integer programs (MIPs) focus on finding close to optimal solutions for feasible instances. Users are aware that the answers are only accurate with respect to feasibility and optimality tolerances, but for many application, this is regarded to be acceptable.
This situation changes fundamentally when MIPs are used to study theoretical problems, when instances become pure feasibility questions (and are infeasible), and when wrong answers can have legal consequences. Examples for applications where inexact solvers are not adequate include combinatorial design theory, chip verification, and contracting by combinatorial auctions.
In this project, we develop and implement an approach for the exact solution of MIPs. By extending the constraint programming/MIP solver SCIP, we want to provide a tool, which is freely available to the scientific community, to compute exact optimal solutions or, perhaps even more important, exact certificates for infeasibility.
Publications
- A. M. Gleixner, D. E. Steffy and K. Wolter. "Improving the Accuracy of Linear Programming Solvers with Iterative Refinement". Zuse Institute Berlin. Tech. Rep. 12-19. 2012. [More]
- T. Koch et al. "MIPLIB 2010", Mathematical Programming Computation, Vol. 3. 2011, pp. 103-163. [More]
- W. Cook, T. Koch, D. E. Steffy and K. Wolter. "An Exact Rational Mixed-Integer Programming Solver". IPCO 2011: Proceedings of the 15th International Conference on Integer Programming and Combinatoral Optimization. O. Günlük and G. J. Woeginger eds. 2011. pp. 104-116. [More]
- D. E. Steffy and K. Wolter. "Valid Linear Programming Bounds for Exact Mixed-Integer Programming". Zuse Institute Berlin. Tech. Rep. 11-08. 2011. [More]
- T. Achterberg, T. Berthold, T. Koch and K. Wolter. "Constraint Integer Programming: A New Approach to Integrate CP and MIP". Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 5th International Conference, CPAIOR 2008. L. Perron and M. A. Trick eds. 2008. pp. 6-20. [More]