> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-3/advanced_topics/linear_programming/integer_linear_programming.md).

# 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](https://en.wikipedia.org/wiki/Linear_programming_relaxation)
* UW-Madison CS787 [Lecture 10](http://pages.cs.wisc.edu/~shuchi/courses/787-F09/scribe-notes/lec10.pdf)
* UIUC CS598 [Lecture 4](https://courses.engr.illinois.edu/cs598csc/sp2011/Lectures/lecture_4.pdf)