EUVIMEDEUVIMED entdecken
Crossref

ML-Guided Primal Heuristics for Mixed Binary Quadratic Programs

Weimin Huang, Natalie M. Isenberg, Ján Drgoňa, Draguna L Vrabie, Bistra Dilkina

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →