ID-PaS+: Identity-Aware Predict-and-Search for Solving General Mixed-Integer Linear Programs
Proceedings of the International Symposium on Combinatorial Search · 14.08.2026 · 19 (1) · 20-28
DOI: 10.1609/socs.v19i1.43069 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the International Symposium on Combinatorial Search, online erschienen am 14.08.2026. Verfasst von Junyang Cai und 3 weiteren Autor:innen.
Abstract (Originalsprache)
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.
Zitieren
APA
Cai, J., Raqabi, E. M. E., Hentenryck, P. V., & Dilkina, B. (2026). ID-PaS+: Identity-Aware Predict-and-Search for Solving General Mixed-Integer Linear Programs. Proceedings of the International Symposium on Combinatorial Search, 19(1), 20-28. https://doi.org/10.1609/socs.v19i1.43069
Vancouver
Cai J, Raqabi EME, Hentenryck PV, Dilkina B. ID-PaS+: Identity-Aware Predict-and-Search for Solving General Mixed-Integer Linear Programs. Proceedings of the International Symposium on Combinatorial Search. 2026;19(1):20-28. doi:10.1609/socs.v19i1.43069
BibTeX
@article{Cai2026,
author = {Cai, Junyang and Raqabi, El Mehdi Er and Hentenryck, Pascal Van and Dilkina, Bistra},
title = {ID-PaS+: Identity-Aware Predict-and-Search for Solving General Mixed-Integer Linear Programs},
journal = {Proceedings of the International Symposium on Combinatorial Search},
year = {2026},
volume = {19},
number = {1},
pages = {20--28},
doi = {10.1609/socs.v19i1.43069}
}
EUVIMED