Abstract
Implied-integer detection is a 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. Despite the wide usage of implied integers, little research has been done on the topic, and only two methods are known, which both can only infer implied integrality of a single variable at a time. In this presentation, I highlight a polyhedral perspective on implied integrality, which lead to techniques that detect implied integrality of multiple variables at once. 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, 17.4% of the variables are classified as implied integer after presolving, compared to just 2.9% 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.8% to 60.5%.
