If you have read my (early draft of an) article about how to interface modern C++ with MILP solvers, you know that many commercial MILP solvers offer free versions for evaluation/non-commerical usage that are restricted by the number of inequalities/variables that a problem instance may have. To “circumvent” these restrictions, we state the following problem:

Problem: Let a finite set \(S \subseteq \mathbb{Z}^d\) (\(d \in \mathbb{Z}_{\geq 0}\)) be given such that \(S = (\operatorname{conv} S) \cap \mathbb{Z}^d\). We want to find \(A \in \mathbb{Q}^{k \times d}\) and \(b \in \mathbb{Q}^k\) (\(k \in \mathbb{Z}_{\geq 0}\)) such that \(S = \{x \in \mathbb{Z}^d: A x \leq b\}\) and \(k\) is as small as possible.

Of course, this problem can easily be generalized, but for this text, this simple form suffices.

In the following theorem, we consider the situation if \(S = \{0,1\}^d\) (i.e. the integral vertices of the unit cube in dimension \(d \in \mathbb{Z}_{\geq 1}\)). Trivially, the natural inequality description for \(S = \{0,1\}^d\) needs \(2 d\) inequalities. We show that \(d+1\) inequalities suffice.

Theorem: Let \(d \in \mathbb{Z}_{\geq 1}\), \(A^d \in \mathbb{Z}^{(d+1) \times d}\) and \(b^d \in \mathbb{Z}^{d+1}\), where \begin{align*} A^d_{i,j} & := \begin{cases} 0 & \text{if } i < j, \\ -2^{j-1} & \text{if } i = j, \\ 2^{j-1} & \text{if } i > j, \end{cases} \\ b^d_i & := 2^{i-1}-1 \\ \end{align*} for \(i \in \{1, \ldots, d+1\}\), \(j \in \{1, \ldots, d\}\). Then $$\{x \in \mathbb{Z}^d: A^d x \leq b^d\} = \{0,1\}^d.$$

Proof: For \(\{x \in \mathbb{Z}^d: A^d x \leq b^d\} \supseteq \{0,1\}^d\): Let \(x \in \{0,1\}^d\) and let \(i \in \{1, \ldots, d+1\}\). If \(i \in \{1, \ldots, d\}\), we have \[ A^d_{i,*} x = \sum_{j=1}^{i-1} 2^{j-1} x_j - 2^{i-1} x_i \leq \sum_{j=1}^{i-1} 2^{j-1} = 2^{i-1}-1 = b^d_i. \] On the other hand, if \(i=d+1\), we obtain \[ A^d_{d+1,*} x = \sum_{j=1}^d 2^{j-1} x_j \leq \sum_{j=1}^d 2^{j-1} = 2^d-1 = b^d_{d+1}. \]

For \(\{x \in \mathbb{Z}^d: A^d x \leq b^d\} \subseteq \{0,1\}^d\): By induction on \(d\), we show two statements:

1. \(\{x \in \mathbb{Z}^d: A^d x \leq b^d\} \subseteq \{0,1\}^d\),
2. \(\{x \in \mathbb{Z}^d: A^d x \leq b^d - 1^{d+1}\} = \emptyset\).

The induction basis clearly holds for \(d=1\). So for the induction step:

For 1: Consider an \(x \in \mathbb{Z}^d\) that satisfies \(A^d x \leq b^d\). It is a consequence of \(A^d_{1,*} x \leq b^d_1\) that \(x_1 \geq 0\).

• If \(x_1 = 0\), we have $$\underbrace{A^d_{(2, \ldots, d+1), (2, \ldots, d)}}_{= 2 A^{d-1}} x_{(2, \ldots, d)} = A^d_{(2, \ldots, d+1), *} x \leq \underbrace{b^d_{(2, \ldots, d+1)}}_{= 2 b^{d-1} + 1^d}.$$ Thus $$A^{d-1} x_{(2, \ldots, d)} \leq b^{d-1} + \frac{1}{2} \cdot 1^d.$$ Since \(x\) and \(A\) are integral, we conclude $$A^{d-1} x_{(2, \ldots, d)} \leq \left\lfloor b^{d-1} + \frac{1}{2} \cdot 1^d\right\rfloor = b^{d-1},$$ which by item 1 of the induction hypothesis implies \(x_{(2, \ldots, d)} \in \{0,1\}^{d-1}\), thus \(x \in \{0,1\}^d\).
• If \(x_1 = 1\), we have $$\underbrace{A^d_{(2, \ldots, d+1), (2, \ldots, d)}}_{= 2 A^{d-1}} x_{(2, \ldots, d)} = A^d_{(2, \ldots, d+1), *} x - 1^d \leq \underbrace{b^d_{(2, \ldots, d+1)} - 1^d}_{= 2 b^{d-1}}.$$ Thus $$A^{d-1} x_{(2, \ldots, d)} \leq b^{d-1},$$ which by item 1 of the induction hypothesis implies \(x_{(2, \ldots, d)} \in \{0,1\}^{d-1}\), thus \(x \in \{0,1\}^d\).
• If \(x_1 \geq 2\), we have $$\underbrace{A^d_{(2, \ldots, d+1), (2, \ldots, d)}}_{= 2 A^{d-1}} x_{(2, \ldots, d)} = A^d_{(2, \ldots, d+1), *} x - 2 \cdot 1^d \leq \underbrace{b^d_{(2, \ldots, d+1)}}_{= 2 b^{d-1} + 1^d} - 2 \cdot 1^d = 2 b^{d-1} - 1^d.$$ Thus $$A^{d-1} x_{(2, \ldots, d)} \leq b^{d-1} - \frac{1}{2} \cdot 1^d.$$ Since \(x\) and \(A\) are integral, we conclude $$A^{d-1} x_{(2, \ldots, d)} \leq \left\lfloor b^{d-1} - \frac{1}{2} \cdot 1^d\right\rfloor = b^{d-1} - 1^d.$$ But by item 2 of the induction hypothesis, no such \(x_{(2, \ldots, d)}\) exists.

For 2: Consider an \(x \in \mathbb{Z}^d\) that satisfies \(A^d x \leq b^d - 1^{d+1}\). Since \(A^d_{1,*} x \leq b^d_1 - 1\), we have \(x_1 \geq 1\). On the other hand, \(x\) satisfies the weaker statement \(A^d x \leq b^d\). This, by 1 (which we just showed), implies \(x_1 = 1\). So we have $$\underbrace{A^d_{(2, \ldots, d+1), (2, \ldots, d)}}_{= 2 A^{d-1}} x_{(2, \ldots, d)} = A^d_{(2, \ldots, d+1), *} x - 1^d \leq \underbrace{b^d_{(2, \ldots, d+1)}}_{= 2 b^{d-1} + 1^d} - 1^d - 1^d = 2 b^{d-1} - 1^d.$$ Now by the same argument that we used for showing 1 in the case \(x_1 \geq 2\), no such \(x\) exists.

On the other hand, it is easy (though somewhat tedious) to see that for \(S = \{0,1\}^d\) (\(d \in \mathbb{Z}_{\geq 1}\)), \(d\) inequalities will not suffice. So we have indeed found the best possible bound.

Update from 2018-08-28

For all the people who took the idea of “circumventing” the restrictions of evaluation versions of commercial (M)ILP solvers via this construction seriously: this was simply quite a funny motivation (I think) for such a “boring looking” math problem. Thus bringing it up was too compelling. :-)

This formulation will probably not work too well in practise - the very different magnitudes of coefficients will likely cause numerical issues for (M)ILP solvers (on the other hand: this property might make it quite a nice test problem).

Also the restrictions of (M)ILP solvers on the number of variables/inequalities are much more subtle than what we stated in the problem statement. It is quite typical in interfaces for (M)ILP solvers that for each variable, one may impose an upper and a lower bound or one can setup variables as binary. It would not surprise me if these bounds do not count towards the restriction on the maximum number of allowed inequalities. If this is the case, we can simply formulate the integral points in the unit cube \([0,1]^d\) (\(d \in \mathbb{Z}_{\geq 1}\)) by defining \(d\) binary variables (or integral variables with a lower bound of \(0\) and an upper bound of \(1\)).