# Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions: A Survey
## 2 Preliminaries
### Integer Linear Programming  
We consider instances of Integer Linear Programming (ILP) in the following two normal forms. In the first case, which we call the equality normal form, instances consist of a matrix \(A\in\mathbb{Z}^{m\times n}\) with \(m\) rows (constraints) and \(n\) columns (variables) and vectors \(\mathbf{c},\mathbf{b}\in\mathbb{Z}^{m},\mathbf{l},\mathbf{u}\in\mathbb{Z}^{n} \cup\{\infty,-\infty\}\). The set of solutions for the equality normal form is given by:  
\[\{\,\mathbf{y}\mid A\mathbf{y}=\mathbf{b},\,\mathbf{l}\leq\mathbf{y}\leq \mathbf{u}\,\}\] (EQ)  
In the second case, which we call the inequality normal form, instances consist of a matrix \(A\in\mathbb{Z}^{m\times n}\) with \(m\) rows (constraints) and \(n\) columns (variables) and vectors \(\mathbf{c},\mathbf{b}\in\mathbb{Z}^{m}\). Here, the set of solutions is given by:  
\[\{\,\mathbf{y}\mid A\mathbf{y}\leq\mathbf{b}\,\}\] (INEQ)  
We denote by \(\mathrm{ILPF}_{=}\) and \(\mathrm{ILPF}_{\leq}\) the feasibility problem for ILPs, whose sets of solutions are given in the equality respectively the inequality form, e.g., \(\mathrm{ILPF}_{=}\) is the problem of deciding whether \(\{\,\mathbf{y}\mid A\mathbf{y}=\mathbf{b},\,\mathbf{l}\leq\mathbf{y}\leq \mathbf{u}\,\}\) is non-empty and if so to output a vector \(\mathbf{y}\) in \(\{\,\mathbf{y}\mid A\mathbf{y}=\mathbf{b},\,\mathbf{l}\leq\mathbf{y}\leq \mathbf{u}\,\}\). Moreover, \(\mathrm{ILP}_{=}\) and \(\mathrm{ILP}_{\leq}\) denote the corresponding minimization versions, e.g., \(\mathrm{ILP}_{=}\) is the problem of deciding whether \(\mathbf{y}\in\{\,\mathbf{y}\mid A\mathbf{y}=\mathbf{b},\,\mathbf{l}\leq \mathbf{y}\leq\mathbf{u}\,\}\) contains a vector \(\mathbf{y}\) that minimizes \(\mathbf{c}\) and if so outputs such a vector. For the matrix \(A\) of an instance \(\mathcal{I}\), we let \(\mathbf{x}=(x_{1},\ldots,x_{n})\) be a vector representing the columns in \(A\) and let the variable set, denoted \(\mathrm{var}(\mathcal{I})\), be the set of such columns. If \(\mathcal{I}\) is given in equality normal form, then its constraint set denoted by \(\mathrm{con}(\mathcal{I})\) contains one equation for every equation in the system \(A\mathbf{x}=\mathbf{b}\) respectively one inequality for every inequality in the system \(A\mathbf{x}\leq\mathbf{b}\), if \(\mathcal{I}\) is given in inequality normal form. We will also make use of the following notions which describe specific properties of ILP instances. We denote by \(\|A\|_{\infty}\), \(\|\mathbf{b}\|\), and \(\|\mathbf{c}\|\) the maximum absolute value of any coefficient (entry) in the matrix \(A\), in the vector \(\mathbf{b}\), and in the vector \(\mathbf{c}\), respectively. For an ILP instance \(\mathcal{I}\) in inequality form, we say that the domain of the variable \(x_{i}\) is _bounded_ if there are constraints \(p\) and \(r\) of the form \(x_{i}\leq b_{p}\) and \(-x_{i}\leq b_{r}\), otherwise we say that its domain is _unbounded_. Moreover, we denote by \(\|x_{i}\|\) the maximum _domain span_ of the \(i\)-th variable, i.e., given by \(\|b_{p}-b_{r}\|\) if \(x_{i}\) has bounded domain and \(\infty\) otherwise. We denote by \(\|\mathbf{x}\|_{\infty}\) the maximum domain span of any variable, i.e., \(\max_{i}\|x_{i}\|\). On the other hand, if \(\mathcal{I}\) is in equality form, we say that the domain of the \(i\)-th variable \(x_{i}\) is _bounded_ if \(l_{i},u_{i}\
ot\in\{-\infty,\infty\}\), where \(l_{i},u_{i}\) are the \(i\)-th entries of \(\mathbf{l}\), \(\mathbf{u}\), respectively; otherwise, we say that the domain of \(\mathbf{x}\) is _unbounded_. Moreover, we denote by \(\|x_{i}\|\) the maximum _domain span_ of the \(i\)-th variable, i.e., \(\|u_{i}-l_{i}\|\) any variable, and by \(\|\mathbf{x}\|_{\infty}\) the maximum domain span of any variable, i.e., \(\max_{i}\|x_{i}\|\). In either case, we say that an ILP instance has _bounded domain_ if all variables have bounded domain, and we say that the instance has _unary bounded domain_ if the coefficients bounding the domain of variables are encoded in unary.