ML-Guided Primal Heuristics for Mixed Binary Quadratic Programs
Proceedings of the International Symposium on Combinatorial Search · 14.08.2026 · 19 (1) · 74-83
DOI: 10.1609/socs.v19i1.43075 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the International Symposium on Combinatorial Search, online erschienen am 14.08.2026. Verfasst von Weimin Huang und 4 weiteren Autor:innen.
Abstract (Originalsprache)
Mixed Binary Quadratic Programs (MBQPs) are an important and complex set of problems in combinatorial optimization. As solving large-scale combinatorial optimization problems is challenging, primal heuristics have been developed to quickly identify high-quality solutions within a short amount of time. Recently, a growing body of research has also used machine learning to accelerate solution methods for challenging combinatorial optimization problems. Despite the increasing popularity of these ML-guided methods, a large body of work has focused on Mixed-Integer Linear Programs (MILPs). MBQPs are challenging to solve due to the combinatorial complexity coupled with nonlinearities. This work proposes ML-guided primal heuristics for Mixed Binary Quadratic Programs (MBQPs) by adapting and extending existing work on ML-guided MILP solution prediction to MBQPs. We introduce a new neural network architecture for MBQP solution prediction and a new training data collection procedure. Moreover, we extend existing loss functions in solution prediction and propose to combine contrastive and weighted cross-entropy losses. We evaluate the methods on standard and real-world MBQP benchmarks and show that the developed ML-guided methods significantly outperform existing primal heuristics and state-of-the-art solvers. Furthermore, models trained with our proposed extension with combined losses outperform other ML-based methods adapted from MILPs and improve generalization in cross-regional inference on a real-world wind farm layout optimization problem.
Zitieren
APA
Huang, W., Isenberg, N. M., Drgoňa, J., Vrabie, D. L., & Dilkina, B. (2026). ML-Guided Primal Heuristics for Mixed Binary Quadratic Programs. Proceedings of the International Symposium on Combinatorial Search, 19(1), 74-83. https://doi.org/10.1609/socs.v19i1.43075
Vancouver
Huang W, Isenberg NM, Drgoňa J, Vrabie DL, Dilkina B. ML-Guided Primal Heuristics for Mixed Binary Quadratic Programs. Proceedings of the International Symposium on Combinatorial Search. 2026;19(1):74-83. doi:10.1609/socs.v19i1.43075
BibTeX
@article{Huang2026,
author = {Huang, Weimin and Isenberg, Natalie M. and Drgoňa, Ján and Vrabie, Draguna L and Dilkina, Bistra},
title = {ML-Guided Primal Heuristics for Mixed Binary Quadratic Programs},
journal = {Proceedings of the International Symposium on Combinatorial Search},
year = {2026},
volume = {19},
number = {1},
pages = {74--83},
doi = {10.1609/socs.v19i1.43075}
}
EUVIMED