























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\geq τ(Δ)$ many variables and $n + κ(Δ)\cdot \sqrt{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(\sqrtΔ)$ many integer constraints.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。