Presolve action sequencing speeds mixed integer programming solving times
ORDO: Operation-level Round-aware Dynamic Ordering for MIP Presolve
Artificial Intelligence
Summary
Mixed-integer programming is a way to solve complex decision problems, but it often spends a lot of time simplifying the problem first, called presolve. This paper shows that changing the order of these simplifications without care can make solving much slower. The authors propose a new approach called ORDO that learns smart sequences of simplifications that adapt over time, improving performance even on problems it hasn't seen before. Their method also runs multiple candidate sequences at once and picks the best one, leading to faster overall solutions.
What this means in practice
- •For optimization engineers: Deploy faster mixed-integer programming presolve sequences across diverse problem types without retraining.
- •For supply chain analysts: Speed up complex planning and scheduling models by improving presolve action ordering in optimization software.
Authors
Zehuan Chen, Chunhe Song
Abstract
Presolve strongly affects mixed-integer programming (MIP) performance, yet learning-based methods only optimize parameter configurations and cannot express the non-commutative temporal dependencies among actions, whose default order is nearly unique on most domains, yet functionally necessary: artificially shuffling the order of the same sequence inflates the tail of the solve-time distribution by up to several-fold. We recast presolve planning as autoregressive sequence generation over a unified atomic action space, moving the decision object to action sequences; we call this framework ORDO---Operation-level Round-aware Dynamic Ordering for MIP Presolve. Its payoff is cross-domain generalization: on multiple unseen domains it attains end-to-end zero-shot speedup---to our knowledge the first for presolve action sequences---varying by domain and not explained by corpus richness, the strongest domain reaching the largest speedup once racing is added. Deployment uses sequence racing, in which candidate sequences run concurrently and the winner is kept, enabled by an execution-and-observation facility, added by modifying the SCIP source, that injects sequences along the native path and records which actions actually execute and in which round.