Conformal Prediction for Early Stopping in Mixed Integer Optimization

Mixed-integer optimization solvers often find optimal solutions early in the search, yet spend the majority of computation time proving optimality. We exploit this by learning when to terminate solvers early on distributions of similar problem instances. Our method trains a neural network to estimate the true optimality gap from the solver state, then uses conformal prediction to calibrate a stopping threshold with rigorous probabilistic guarantees on solution quality. On six problem families from the Distributional MIPLIB library, our method reduces solve time by over 60% while guaranteeing 0.1%-optimal solutions with 95% probability for new instances drawn from the same distribution.

Many real-world problems, like scheduling deliveries, dispatching power, or routing fleets, come down to choosing the best option from millions of possibilities. Standard algorithms find the best answer quickly, then spend most of their time proving it's best. It's like a chef who finds the perfect recipe in ten minutes, then checks every alternative for two hours. We trained a small neural network to spot, from how the solver runs, when its current answer is probably already optimal. Since the network alone isn't trustworthy, we pair it with conformal prediction: a calibration technique that turns unreliable predictions into provable guarantees using a sample of past problems. On six benchmark problem families, the method cuts solve time by over 60% on five of them while still returning solutions within 0.1% of optimal at least 95% of the time. Useful anywhere a formal optimality proof costs more than the answer is worth: high-frequency trading, real-time control, emergency dispatch.