3
$\begingroup$

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.

$\endgroup$
4
  • 4
  • $\begingroup$ If the LP has multiple optimal solutions, it must have non-integral optimal solutions, since every affine combination of optimal solutions (i.e., every point on the line segment connecting two optimal solutions) is also optimal, and the solutions must differ in at least one variable. $\endgroup$ Feb 27, 2021 at 11:14
  • $\begingroup$ @D.W., thank you for the links. While total unimodularity is the answer, I'm missing a point of the other two links (they are great, but I don't think they add anything new to this answer). Can you please clarify where exactly I should look at? $\endgroup$
    – user114966
    Feb 27, 2021 at 19:42
  • $\begingroup$ The notion of integrality gap is a generalization of your question #2; and there is a lot written on the integrality gap. $\endgroup$
    – D.W.
    Feb 27, 2021 at 21:19

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

This site is temporarily in read-only mode and not accepting new answers.