ID-PaS : Identity-Aware Predict-and-Search for General Mixed-Integer Linear Programs
This addresses the problem of efficiently solving general mixed-integer linear programs with heterogeneous variables for practitioners in combinatorial optimization, representing an incremental improvement over existing Predict-and-Search methods.
The paper tackled the limitation of Predict-and-Search methods to binary problems by extending it to parametric mixed-integer linear programs with ID-PaS, an identity-aware learning framework, and demonstrated superior performance over state-of-the-art solvers like Gurobi and PaS in experiments on real-world large-scale problems.
Mixed-Integer Linear Programs (MIPs) are powerful and flexible tools for modeling a wide range of real-world combinatorial optimization problems. Predict-and-Search methods operate by using a predictive model to estimate promising variable assignments and then guiding a search procedure toward high-quality solutions. Recent research has demonstrated that incorporating machine learning (ML) into the Predict-and-Search framework significantly enhances its performance. Still, it is restricted to binary problems and overlooks the presence of fixed variables that commonly arise in practical settings. This work extends the Predict-and-Search (PaS) framework to parametric MIPs and introduces ID-PaS, an identity-aware learning framework that enables the ML model to handle heterogeneous variables more effectively. Experiments on several real-world large-scale problems demonstrate that ID-PaS consistently achieves superior performance compared to the state-of-the-art solver Gurobi and PaS.