The Integrality Number of an Integer Program

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 \(\varDelta \) of the constraint matrix, our analysis allows us to make statements of the following form: there exist numbers \(\tau (\varDelta )\) and \(\kappa (\varDelta )\) such that an IP with \(n\ge \tau (\varDelta )\) many variables and \(n + \kappa (\varDelta )\cdot \sqrt{n}\) many inequality constraints can be solved via a MIP relaxation with fewer than n integer constraints. A special instance of our results shows that IPs defined by only n constraints can be solved via a MIP relaxation with \(O(\sqrt{\varDelta })\) many integer constraints.

The authors wish to thank Helene Weiß and Stefan Weltge for their help that led to major improvements of the manuscript. We are also grateful to the anonymous referees for their comments that improved the presentation of the material. The third author acknowledges the support from the Einstein Foundation Berlin.

Authors and Affiliations

1. Department of Mathematics, ETH Zürich, Zürich, Switzerland

   Joseph Paat, Miriam Schlöter & Robert Weismantel

Corresponding author

Correspondence to Miriam Schlöter .

Editors and Affiliations

1. Department of IEOR, Columbia University, New York, NY, USA

   Daniel Bienstock

2. Department of Management, London School of Economics and Political Science, London, UK

   Giacomo Zambelli

Appendix

Proof

(of Lemma 2). Let \(W \in \mathbb {Z}^{k\times n}\) be a matrix with minimal k such that all vertices of \(W\!\text {-}\text {MIP}_{A,c}(b)\) are integral. Set \(\overline{A} := AU\), \(\overline{c} := c^\intercal U\), and \(\overline{W} := WU\). The matrix \(U^{-1}\) maps the vertices of \(W\!\text {-}\text {MIP}_{A,c}(b)\) to those of \(\overline{W}\!\text {-}\text {MIP}_{\overline{A}, \overline{c}}(b)\), and \(U^{-1}\) maps \(\mathbb {Z}^n\) to \(\mathbb {Z}^n\). Thus, \(\overline{W} \in \mathbb {Z}^{k\times n}\) and the vertices of \(\overline{W}\!\text {-}\text {MIP}_{\overline{A}, \overline{c}}(b)\) are integral. Hence, \(i_{A}(b) \ge i_{\overline{A}}(b)\). To see why the reverse inequality holds, it is enough to notice that \(U^{-1}\) is also unimodular.    \(\square \)

Proof

(of Lemma 4). By Ghouila-Houri (see, e.g.,[17, §19]) it is enough to show

for a subset \(\widehat{W}\) of the rows of W. Recall that every column u of \(C = (B ~~ T ) W\) can be written as \(u = v+t\) for some \(v \in B\) and \(t \in T \cup \{0\}\). Hence, a column of W has at most two non-zero entries, where a non-zero entry equals 1. One of these entries is in the rows of \(W^B\) while the other is in \(W^T\). This shows \(y \in \{-1,0,1\}^n\).    \(\square \)

Proof

(of Lemma 5). Let z be a column of \(A_I^1\). If \(z \in \{z^1, \dotsc , z^{\ell }\}\), then \(z = z+0 \in B+(T \cup \{0\})\). Else, \(z \in \{0,...,\alpha _1-1\} \times ... \times \{0,...,\alpha _\ell -1\}\). Define

We have \(v_i \in \{0,\ldots ,k_i\}\) for each \(i \in \{0,\ldots ,\ell \}\), so \(v := (v_0, \ldots , v_\ell )^\intercal \in B\). To see that \((t_1,\ldots ,t_\ell )^\intercal \in T\) note that \(t_i \le \beta _i\cdot (k_i+1)\) for each \(i \in \{1,\ldots , \ell \}\).

It is left to choose \(k_1, \dotsc , k_{\ell }\) such that \(|B|+|T| \le 6{\delta }^{1/2}+\log _2({\delta }) \). Note \(\ell \le \log _2({\delta })\) as \(\alpha _1, \dotsc , \alpha _{\ell } \ge 2\). By permuting rows and columns we assume \(\alpha _1 \le \alpha _2\le \ldots \le \alpha _{\ell }\). We consider two cases.

Case 1. Assume \(\alpha _\ell = {\delta }^\tau \) for \(\tau \ge 1/2\). This implies \(\prod _{i=1}^{\ell -1} \alpha _i = {\delta }^{1 - \tau } \le {\delta }^{1/2}\). Let \(\sigma \ge 0\) such that \(1-\tau + \sigma = 1/2\). For each \(i \in \{1, \dotsc , \ell -1\}\) define \(k_i := \alpha _i-1\) and set \(k_{\ell } := \lceil {\delta }^\sigma \rceil \). The value \(\beta _{\ell }\) in (9) satisfies

Define \(B = \overline{B} \cup \{z^1, \dotsc , z^{\ell }\}\), where \( \overline{B} := \{0, \dotsc , k_1\} \times \dotsc \times \{0, \dotsc , k_{\ell }\}, \) and the set T via (9). A direct computation reveals that \(|B| + |T| = |\overline{B}|+|T|+\ell \) is upper bounded by

Case 2. Assume \(\alpha _{\ell } < {\delta }^{1/2} \), which implies \({\delta }^{1/2} < \prod _{i=1}^{\ell -1} \alpha _i \). Let \(j \in \{1, \dotsc , \ell -2\}\) be the largest index with \(\gamma := \prod _{i = 1}^j \alpha _i \le {\delta }^{1/2}\). Let \(\sigma \ge 0\) be such that \(\gamma \cdot {\delta }^ \sigma = {\delta } ^ {1/2}\) and \(\tau < 1/2\) be such that \(\alpha _{j+1} = {\delta }^\tau \). Note that \(0 \le \sigma < \tau \) and \({\delta }^{\tau - \sigma } \cdot \prod _{i = j+2}^\ell \alpha _i = {\delta }^{1/2}\). For each \(i \in \{1, \dotsc , j\}\) define \(k_i := 0\), for each \(i \in \{j+2, \dotsc , \ell \}\) define \(k_i := \alpha _i - 1\), and set \(k_{j+1} := \lceil {\delta }^{\tau - \sigma } \rceil \). The value \(\beta _{j+1}\) in (9) satisfies

Define \(B = \overline{B} \cup \{z^1, \dotsc , z^{\ell }\}\), where \( \overline{B} := \{0, \dotsc , k_1\} \times \dotsc \times \{0, \dotsc , k_{\ell }\}, \) and the set T via (9). In this case we have \(|B| + |T| = |\overline{B}|+|T|+l \) is upper bounded by

   \(\square \)

Proof

(of Lemma 7). Let \(x^* := A_I^{-1} b_I\) be the feasible vertex solution to \({\text {LP}}_{A,c}(b)\) with respect to the basis I. Applying Theorem 1 in [6] to the simplicial problems \({\text {LP}}_{A_I,c}(b)\) and \({\text {IP}}_{A_I,c}(b)\) shows that \(z^*\) satisfies \(\Vert z^* - x^*\Vert _{\infty } \le n\varDelta ^{\max }\). Thus, for every \(j \in \{1, \dotsc , m\}\setminus I\) we have

The assumption \(A_jA_I^{-1} b_I+ (n\varDelta ^{\max })^2 < b_j \) implies

Thus, \(z^*\) is feasible for \(W\!\text {-}\text {MIP}_{A,c}(b)\).    \(\square \)

Proof

(of Lemma 8). Let \(b \in \mathbb {Z}^m \setminus \mathcal {G}\). Therefore, there exists a feasible \({\text {LP}}_{A,c}(b)\) basis \(I \subseteq \{1,\ldots ,m\}\) and \(j \in \{1,\ldots ,m\} \setminus I\) such that \(b_j \le A_jA_I^{-1} b_I + (n\varDelta ^{\max })^2\). Recall \(A_jA_I^{-1} b_I \le b_j\) because \(A_I^{-1} b_I\) is feasible for \({\text {LP}}_{A,c}(b)\). Thus, \(\mathbb {Z}^m\setminus \mathcal {G}\) is in

Cramer’s Rule implies that \(\varDelta _I \cdot A_jA_I^{-1} b_I \in \mathbb {Z}\) for all \(j \in \{1,\ldots ,m\} \setminus I\). Thus,

   \(\square \)

Reprints and permissions

© 2020 Springer Nature Switzerland AG

Policies and ethics