# Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions: A Survey
## 3 Solving ILPs with Explicit Restrictions  
Initial work on mapping the complexity of integer linear programming predominantly focused on identifying tractable classes by placing restrictions on explicit properties of instances, such as the number of variables or of constraints. [PERSON] (1975) showed that ILP can be solved by an algorithm which has an exponential dependency on the number of variables, but only a linear dependency on the size of the instance. His running time was subsequently improved by [PERSON] (1975) and [PERSON] and [PERSON] and [PERSON] (1999). Theorem 1 (([PERSON], 1975; [PERSON], 1975; [PERSON], 1999)): _An ILP instance \(\mathcal{I}\) with \(n\) variables can be solved in time \(\mathcal{O}(n^{2.5n+o(n)}\cdot|\mathcal{I}|)\); in other words, ILP is fixed-parameter tractable parameterized by \(n\)._  
[PERSON] showed that ILP is fixed-parameter tractable parameterized by \(m+\|A\|_{\infty}+\|\mathbf{b}\|\)[PERSON] and [PERSON] (1975). His result was recently improved by [PERSON] and [PERSON] and [PERSON] and [PERSON] (1975), and then further improved by [PERSON] and [PERSON] [PERSON] and [PERSON] (1975). Even more recently, [PERSON], [PERSON] and [PERSON] showed that the running time of this result cannot be substantially improved [PERSON] et al. (2017). Theorem 2 (([PERSON], 1975; [PERSON], 1975; [PERSON], 1975)): _An ILP\({}_{=}\) instance \(\mathcal{I}\) with \(m\) constraints can be solved in time \(\mathcal{O}((m\cdot\|A\|_{\infty})^{m}\cdot\log\|\mathbf{b}\|)\); in other words, ILP is fixed-parameter tractable parameterized by \(m+\|A\|_{\infty}\)._  
On the other hand, ILP remains intractable when all other obvious numerical measures are bounded. In particular, ILP remains **NP**-complete even when \(\|A\|_{\infty}=\|\mathbf{b}\|=\|\mathbf{u}\|=1\) and \(\|\mathbf{l}\|=0\), as witnessed by the folklore encoding of the Vertex Cover problem into ILP, i.e., given a graph \(G\) and an integer \(k\), the ILP instance has one binary variable for every vertex of \(G\) (representing of whether or not the vertex is chosen to be in a vertex cover) and for every edge between \(u\) and \(v\) a constraint ensuring that the sum of the variables for \(u\) and \(v\) is at least one (ensuring that the vertex cover contains at least one vertex from every edge). While this is not the focus of this survey, we also mention that there is a significant body of work on exploiting algebraic properties to solve ILP. Perhaps the most prominent example of a complexity result obtained in this vein is the well-known fact that instances \(\mathcal{I}\) whose matrix \(A\) is _totally unimodular_ (i.e., each of its square submatrices has a determinant in \(\{-1,0,1\}\)) can be solved in polynomial time ([PERSON], 1975). Theorem 3 (([PERSON], 1975; [PERSON], 1975)): _An ILP instance \(\mathcal{I}\) having a totally unimodular constraint matrix can be solved in polynomial-time._  
We say that an ILP instance is non-negative if all entries of \(A\) and \(b\) are non-negative. [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON] and [PERSON]  
The result follows from standard leaves-to-root dynamic programming along a tree decomposition of \(G_{P}(\mathcal{I})\), and can be straightforwardly adapted to also solve ILP. This result provides a useful tool for dealing with instances where all variables have bounded domain.