Implied integrality in mixed-integer optimization
Mathematical Programming · 13.07.2026
DOI: 10.1007/s10107-026-02389-3 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematical Programming, online erschienen am 13.07.2026. Verfasst von Rolf van der Hulst und 1 weiteren Autor:innen. Die Arbeit nennt 57 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Nederlandse Organisatie voor Wetenschappelijk Onderzoek.
Abstract (Originalsprache)
Implied-integer detection is a well-known presolving technique that is used by many Mixed-Integer Linear Programming solvers. Informally, a variable is said to be implied integer if its integrality is enforced implicitly by integrality of other variables and the constraints of a problem. In this case, algorithms used in MILP software can choose whether they treat it as an integer or continuous variable. In this work we formalize the definition of implied integrality by taking a polyhedral perspective. Our main result characterizes implied integrality as occurring when a subset of integer variables is fixed to integer values and the polyhedron on the remaining variables is integral. While integral polyhedra are well-understood theoretically, existing detection methods infer implied integrality only for one variable at a time. We introduce new detection methods based on the detection of integral polyhedra, extending existing techniques to multiple variables. Additionally, we discuss the computational complexity of recognizing implied integers. We conduct experiments using a new detection method that uses totally unimodular submatrices to identify implied integrality. For the MIPLIB 2017 collection dataset our results indicate that, on average, 18.8 % of the variables are classified as implied integer after presolving, compared to just 3.3 % identified by state-of-the-art techniques. Moreover, we are able to reduce the average percentage of variables whose integrality needs to be enforced after presolving from 70.2% to 59.0%.
Förderung
- Nederlandse Organisatie voor Wetenschappelijk Onderzoek
Zitieren
APA
Hulst, R. V. D., & Walter, M. (2026). Implied integrality in mixed-integer optimization. Mathematical Programming. https://doi.org/10.1007/s10107-026-02389-3
Vancouver
Hulst RVD, Walter M. Implied integrality in mixed-integer optimization. Mathematical Programming. 2026. doi:10.1007/s10107-026-02389-3
BibTeX
@article{Hulst2026,
author = {Hulst, Rolf van der and Walter, Matthias},
title = {Implied integrality in mixed-integer optimization},
journal = {Mathematical Programming},
year = {2026},
doi = {10.1007/s10107-026-02389-3}
}
EUVIMED