2019/04/15 by Joseph Paat, Paat, Joseph, Miriam Schlöter +3
Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #cs.DS #math.OC
paper · pdf · doi:10.48550/arxiv.1904.06874
This is a preprint of an article published in Mathematical Programming. The final authenticated version is available online at: https://doi.org/10.1007/s10107-021-01651-0
arxiv created 2021/04/07 · arxiv updated 2021/04/08
We introduce the integrality number of an integer program (IP) in inequality form. Roughly speaking, the integrality number is the smallest number of integer constraints needed to solve an IP via a mixed integer (MIP) relaxation. One notable property of this number is its invariance under unimodular transformations of the constraint matrix. Considering the largest minor Δ of the constraint matrix, our analysis allows us to make statements of the following form: there exist numbers τ(Δ) and κ(Δ) such that an IP with n≥ τ(Δ) many variables and n + κ(Δ)⋅ √(n) many inequality constraints can be solved via a MIP relaxation with fewer than n integer constraints. From our results it follows that IPs defined by only n constraints can be solved via a MIP relaxation with O(√Δ) many integer constraints.