MiniMIP: a Faster, More Reliable, and Easier Way to Maintain and Solve MIP Problems completed

The MiniMIP project aims to develop a modular, minimalistic, and robust Mixed-Integer Linear Programming (MILP) solver with a strong emphasis on correctness, readability, and efficiency. The primary objective is to ensure correctness through rigorous testing, including unit tests, randomized tests, and end-to-end tests. In this project, we are handling numerical issues proactively by increasing precision or notifying the user to avoid silent errors. A significant focus is placed on maintaining code readability. The project emphasizes simplicity and clarity in its codebase, even at the expense of initial performance optimizations. This approach facilitates easier maintenance and future enhancements, enabling the integration of new algorithms and concepts. We are employing continuous benchmarking on various MIP instances to identify and address performance bottlenecks. The solver is designed to handle large-scale problems, supporting continuous, integer, and implied integer variables, and linear constraints. In this project, we are utilizing Bazel as the build system, taking advantage of its capabilities to manage dependencies and streamline the build process. We provide CMake as an additional option for its widespread use in the industry. This choice ensures that the solver can be compiled and tested efficiently. Several innovative design principles drive MiniMIP. We are adopting a transactional internal API, where components propose modifications that are integrated into the global state by a dedicated component. The solver’s main entry point is a single-use method, Solve(), which runs the solver and returns the solution without preserving state. Future iterations may incorporate checkpointing for warm-starting and restarting. We are supporting recursive solving, allowing the solver to call new Solve() instances within its process. This feature is particularly useful for large neighborhood search heuristics. Although MiniMIP focuses on single-threaded performance, we are providing hooks for external parallelization and integration with other solving processes. The solver aims to be deterministic in its single-threaded mode, ensuring consistent results with the same input and parameters. We are tracking deterministic computation effort through a linear regression model to maintain performance consistency across different runs. For numerical precision, we are using double precision by default, with options for higher precision in specific sub-components. The solver supports global cuts but not local cuts due to the complexity of their management. MiniMIP interfaces with LP solvers through an abstract LP interface, initially supporting SoPlex and Glop. We also plan to integrate with presolvers through a similar abstract interface, initially considering SCIP and Glop presolvers. Overall, the MiniMIP project seeks to contribute significantly to the field of MILP solvers by offering a blend of simplicity, robustness, and efficiency. This initiative aims to advance the computational capabilities of MILP solvers and facilitate the development of new algorithms and solutions for complex optimization problems.