When LP solution is ILP solution?

Question

For many discrete problems, it's natural to consider their continuous relaxations. A common case is when instead of $x_i \in \{0, 1\}$ we allow $x_i \in [0, 1]$. In certain cases, the original problem is an integer linear programming (ILP) problem, and its relaxed version becomes a linear programming (LP) problem, which we can efficiently solve.

Questions: Are there common techniques which show that, for a particular problem:

1. An LP solution will always be an ILP solution?
2. There exists an LP solution that is also an ILP solution?
3. A particular LP algorithm (e.g. simplex method) finds an ILP solution.

By "solution", I, of course, mean a vector on which the objective reaches its optimum.

Answer 1

Consider a linear program of the following form: maximize $c^Tx$ over $Ax \leq b$, where $x \in \mathbb{R}^n$ and $b$ has integer entries.

The simplex algorithm finds a solution of the form $x = A_S^{-1} b_S$, where $A_S$ is a submatrix consisting of $n$ rows, and $b_S$ are the corresponding entries of $b$. Each entry of $A_S^{-1}$ is a ratio of two determinants: the determinant of some $(n-1)\times(n-1)$ submatrix of $A$ (namely, minors of $A_S$), and the determinant of some $n \times n$ submatrix of $A$ (namely, $A_S$). If the entries of $A$ are integers and every $n \times n$ submatrix has determinant $0,\pm 1$, then $A_S^{-1}b$ is integral.

The condition that any square submatrix has determinant $0,\pm 1$ is known as total unimodularity. If the constraint matrix $A$ is totally unimodular, then the simplex algorithm will always find an integral solution.

A more general condition is total dual integrality, which just states that for every integral $c$, the linear program has an integer optimal solution. If the system satisfies TDI then the simplex algorithm is also guaranteed to find an integral solution.