ID-PaS+: Identity-Aware Predict-and-Search for Solving General Mixed-Integer Linear Programs

Abstract

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-only problems and overlooks the presence of fixed variables structure that commonly arise in real-world settings. This work extends the current Predict-and-Search (PaS) framework to parametric general 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.