An integer program is a linear program with an integral coefficient constraint.
$$ \begin{align*} \min_{x \in \R^n} \quad & a_0^T x \\ \text{subject to} \quad & Ax = b \\ & Cx \leq d \\ & x_i \in \Z, \hspace{15pt} i \in [n] \end{align*} $$
Any integer program has convex relaxation to a linear program by converting the integer constraint to a continuous constraint.
<aside> <img src="/icons/castle_yellow.svg" alt="/icons/castle_yellow.svg" width="40px" />
Linear Program with Integral Vertices is Exact Convex Relaxation. If the vertices of the linear program $(1)$ found by relaxing an integer program $(2)$ are integral, then the convex relaxation is exact. In other words, a vertex solution of $(1)$ is a solution to $(2)$ and the optimal objective values are the same.
Given $n$ people and $n$ tasks, where $c_{ij}$ is the time for person $i$ to do task $j$, find an assignment which minimizes the total time required to complete all tasks.
$$
\begin{align*} \min {x \in \R^{n^2}} \quad & \sum {i=1}^n \sum {j=1}^n c{ij} x{ij} \\ \text{subject to} \quad & \sum {i=1}^n x{ij} = 1 \hspace{15pt} i \in [n] \hspace{15pt} \text{all tasks assigned} \\ & \sum {j=1}^n x{ij} = 1 \hspace{15pt} j \in [n] \hspace{15pt} \text{all people assigned} \\ & x{ij} \geq 0 \hspace{32pt} i,j \in [n]\\ & x_{ij} \in \Z, \hspace{27pt} i,j \in [n] \hspace{15pt} \text{$x_{ij} := \mathbf{1}_{\{\text{person i works on task j\}}}$} \end{align*} $$
<aside> <img src="/icons/castle_yellow.svg" alt="/icons/castle_yellow.svg" width="40px" />
All Vertices of LP Relaxation are Integral.
</aside>
Given $m$ suppliers, which each have $s_i$ items, and $n$ customers, which each need $d_j$ items, where $c_{ij}$ is the cost to ship any item from supplier $i$ to customer $j$, find a configuration of item shipments which minimizes the total cost required to meet the total demand.
$$
\begin{align*} \min {x \in \R^{mn}} \quad & \sum {i=1}^m \sum {j=1}^n c{ij} x{ij} \\ \text{subject to} \quad & \sum {j=1}^n x{ij} \leq s_i \hspace{15pt} i \in [n] \hspace{15pt} \text{shipment does not exceed supply} \\ & \sum {i=1}^m x{ij} = d_j \hspace{15pt} j \in [n] \hspace{15pt} \text{demand is met} \\ & x{ij} \geq 0 \hspace{32pt} i,j \in [n]\\ & x_{ij} \in \Z, \hspace{27pt} i,j \in [n] \hspace{15pt} \text{$x_{ij} :=$ \# of items shipped from $i$ to $j$ } \end{align*} $$
<aside> <img src="/icons/castle_yellow.svg" alt="/icons/castle_yellow.svg" width="40px" />
Supply Equals Demand Implies Exact LP Relaxation. If $s_1, \dots, s_m, d_1, \dots, d_n \in \Z$ and we have that $\sum_{i=1}^m s_i = \sum _{j=1}^n d_j$, then the LP relaxation is exact.
</aside>
Suppose that we have measurements $Ax = b$, where $m < n$ so that there exists infinitely many solutions for $x$. Compressed sensing recovers the sparsest possible $x$.
$$ \begin{align*} \min_{x \in \R^n} \quad & ||x||_0 \\ \text{subject to} \quad & Ax = b \\
\end{align*} $$
Since $||x||_1 \leq ||x||_0$ in $[-1, 1]^n$, we have the following convex relaxation in the unit cube.