Integer Linear Programming

Intro

ILP adds an extra constraint that some or all variables must be integers. ILP is NP-hard. A special case, 0-1 ILP is NP-complete.

LP relaxation allows the variables to take on non-integral values. For example, in 0-1 ILP, $x_i \in \{0, 1\}$. After the relaxation, $0 \leq x_i \leq 1$. The relaxation can transform an NP-hard optimization problem to polynomial time. The trade-off is that we will only get a fractional optimal solution.

Formulation for Vertex Cover

Given an undirected graph $G = (V, E)$, for each vertex $i \in V$, $x_i = \begin{cases} 1, & if \; i \in V' \\ 0, & otherwise \end{cases}$

The objective function: $min \sum\limits_{i \in V} x_i$

The constraints:

1. At least one endpoint of each edge is in the subset $V'$. $\forall {e} = (u, v) \in E, x_u + x_v \geq 1$

2. $\forall i \in V, x_i \in \{0, 1\}$

In order to get a poly-time algorithm, we can "relax" the constrain 2 with $x_i \in [0, 1]$.

Formulation for Set Cover

Given a set $U = \{1, 2, ..., n\}$ and a collection $M$ of m subsets $S_1, S_2, ..., S_m$, is there a set of indices $I \subseteq \{1, ..., m\}$ such that $\bigcup\limits_{i \in I} S_i = U$ ? ($|I| \leq K$ in decision version)

For each subset $S_j \in M$, $x_j = \begin{cases} 1, & if \; j \in I \\ 0, & otherwise \end{cases}$

The objective function: $min \sum\limits_{S_j \in M} x_j$

The constraints:

1. for each element $e_h \in U$, $\sum\limits_{\{j | e_h \in S_j\}} x_j \geq 1$ // why we need the summation? cause we need at least one set covers the element $e_h$ and more is fine too.

2. $\forall S_j \in M, \; x_j \in \{0, 1\}$

Formulation for 3-SAT

References

• Wikipedia LP Relaxation

• UW-Madison CS787 Lecture 10

• UIUC CS598 Lecture 4