Introduction
Numerical instability is a persistent challenge in mathematical optimization, often leading to incorrect results, solver crashes, or misleading infeasibility reports. This paper presents a machine learning-based approach to automatically select optimal scaling strategies for Mixed-Integer Programs (MIPs). By predicting a novel "attention level" metric, the proposed model—now integrated into the FICO Xpress solver—significantly enhances numerical robustness and computational efficiency.
The Scaling Challenge
Linear Programs (LPs) and MIPs rely on floating-point arithmetic, making them susceptible to round-off errors and cancellation effects, especially when coefficients span multiple orders of magnitude. Scaling is a standard preconditioning technique used to mitigate these issues. While Standard Scaling (ST) is computationally inexpensive and effective for many problems, Curtis-Reid (CR) scaling offers greater robustness for difficult instances at the cost of a 2–3% performance overhead. The primary challenge lies in determining the most appropriate scaling method at the start of the solution process without incurring unnecessary overhead.
Methodology: Predicting "Attention Level"
Rather than training a model to minimize solve time—which can be an unreliable metric if a solver terminates early due to numerical errors—the authors focus on minimizing the "Attention Level" ($\alpha$). This metric, ranging from 0 to 1, quantifies the numerical "suspiciousness" of a solve based on the condition numbers of basis matrices encountered during the process.
Model and Features
The researchers implemented a regression model using a concise 3-dimensional feature vector. These features capture the logarithmic range of matrix coefficients, objective coefficients, and right-hand side values after the problem has undergone presolving. While more complex models like Random Forests were tested, a Linear Regressor was ultimately selected for production due to its interpretability, minimal memory footprint, and competitive performance.
Experimental Setup
The model was trained and validated on a diverse dataset of 1,199 MIP problems, including the standard MIPLIB 2017 benchmark and confidential industrial data. To enhance diversity, instances were permuted with different random seeds, resulting in a total of 3,235 training and test examples.
Key Insights
- Stability Over Speed: Prioritizing numerical integrity via the Attention Level proxy prevents the model from favoring "fast but wrong" solutions.
- Post-Presolve Features: Extracting features after presolving is essential, as presolve transformations significantly alter the numerical properties of the constraint matrix.
- Conservative Switching: A threshold-based logic ensures the solver only switches to the more expensive Curtis-Reid scaling when a substantial improvement in stability is predicted.
Results and Solver Integration
The "autoscaling" feature in FICO Xpress 8.9 has demonstrated significant improvements in both robustness and performance, particularly on numerically challenging problem sets.
As shown in the results, dual failures were reduced by over 55%, and primal failures by nearly 60% on difficult numerical instances. Furthermore, the model achieved a 4.4% overall speedup for hard LP instances by reducing the time spent in expensive numerical recovery procedures.
Conclusion
By framing scaling selection as a regression problem targeting numerical stability, this work provides a practical and effective solution to a long-standing issue in optimization. Future research may extend this methodology to Quadratic Programming (QP) and explore more complex matrix features to further refine selection accuracy.
Summary updated