The integrality number of an integer program
成果类型：
Article
署名作者：
Paat, Joseph; Schloeter, Miriam; Weismantel, Robert
署名单位：
University of British Columbia; Swiss Federal Institutes of Technology Domain; ETH Zurich
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-021-01651-0
发表日期：
2022
页码：
271-291
关键词：
摘要：
We introduce the integrality number of an integer program (IP). 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 Delta of the constraint matrix, our analysis allows us to make statements of the following form: there exists a number tau(Delta) such that an IP with n many variables and n+root n/tau(Delta) 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(root Delta) many integer constraints.