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, xi∈{0,1}x_i \in \{0, 1\}. After the relaxation, 0≤xi≤10 \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)G = (V, E), for each vertex i∈Vi \in V, xi={1,if  i∈V′0,otherwisex_i = \begin{cases} 1, & if \; i \in V' \\ 0, & otherwise \end{cases}

The objective function: min∑i∈Vximin \sum\limits_{i \in V} x_i

The constraints:

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

  2. ∀i∈V,xi∈{0,1}\forall i \in V, x_i \in \{0, 1\}

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

Formulation for Set Cover

Given a set U={1,2,...,n}U = \{1, 2, ..., n\} and a collection MM of m subsets S1,S2,...,SmS_1, S_2, ..., S_m, is there a set of indices I⊆{1,...,m}I \subseteq \{1, ..., m\} such that ⋃i∈ISi=U\bigcup\limits_{i \in I} S_i = U ? (∣I∣≤K|I| \leq K in decision version)

For each subset Sj∈MS_j \in M, xj={1,if  j∈I0,otherwisex_j = \begin{cases} 1, & if \; j \in I \\ 0, & otherwise \end{cases}

The objective function: min∑Sj∈Mxjmin \sum\limits_{S_j \in M} x_j

The constraints:

  1. for each element eh∈Ue_h \in U, ∑{j∣eh∈Sj}xj≥1\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 ehe_h and more is fine too.

  2. ∀Sj∈M,  xj∈{0,1}\forall S_j \in M, \; x_j \in \{0, 1\}

Formulation for 3-SAT

References

PreviousLinear ProgrammingNextRandomized Algorithms

Last updated