## Definition

• Linear Programming Problem: the problem of either minimizing or maximizing a linear function subject to a finite set of linear constraints
• feasible solution, feasible area, objective function, objective value, optimal solution, optimal objective value
• unbounded: have a infinite objective value
• infeasible: no feasible value
• Equivalent: for each feasible solution $\overline{x}$ to $L$ with objective value $z$, there is a corresponding feasible solution $\overline{x}'$ to $L'$ with objective value $z'$, and for each feasible solution $\overline{x}'$ to $L'$ with objective value $z'$, there is a corresponding feasible solution $\overline{x}$ to $L$ with objective value ́.

### Standard Form

• Maximize $\sum_{j=1}^nc_jx_j$
• subject to $\sum_{j=1}^na_{ij}x_j\leq b_i, x_{j}\geq 0$
• Converting to Stand Form
• Turn Minimize to Maximize
• $x=x_1-x_2,x_1>0,x_2>0$
• Turn equation to inequation
• Turn $\geq$ to $\leq$
• $(A,b,c)$
• Maximize $c^Tx$
• subject to $Ax\leq b,x\geq 0$

### Slack Form

• Maximize $\sum_{j=1}^nc_jx_j$
• subject to
• $x_{n+i}=\sum_{j=1}^nt_jx_j\geq0$
• $x_i\geq 0$
• basic variable: Left side of equation
• nonbasic variable: Right side of equation
• $(N,B,A,b,c,v)$
• Maximize $c^Tx+v$
• subject to
• $x_i=b_i-\sum_{j\in N}a_{ij}x_j,i\in B$
• $x_i\geq 0,i\in N$

## Simplex Algorithm

• pivot: choose a nonbasic varible(entering variable) and a basic variable(leaving variable) and exchange their roles.
• $(N,B,A,b,c,v)\rightarrow (\hat{N},\hat{B},\hat{A},\hat{b},\hat{c},\hat{v})$
• at most $\binom{n+m}{m}$ iterations, otherwise cycles
• Bland’s rule: choose smallest index then must terminate
//n: number of variable
//m: number of restriction

void pivot(int l, int e) {
// Update leaving basic variable
b[l] /= a[l][e];
for (int j = 1; j <= n; j++)
if (j != e) a[l][j] /= a[l][e];
a[l][e] = 1 / a[l][e];
// Update other basic variable
for (int i = 1; i <= m; i++)
if (i != l && fabs(a[i][e]) > 0) {
b[i] -= a[i][e] * b[l];
for (int j = 1; j <= n; j++)
if (j != e) a[i][j] -= a[i][e] * a[l][j];
a[i][e] = -a[i][e] * a[l][e];
}
// Update entering nonbasic variable
ans += c[e] * b[l];
for (int j = 1; j <= n; j++)
if (j != e) c[j] -= c[e] * a[l][j];
c[e] = -c[e] * a[l][e];
}

double simplex() {
while (true) {
int enter = 0, leave = 0;
// Select enter variable
for (enter = 1; enter <= n; ++enter)
if (c[enter] > eps) break;
if (enter == n + 1) return ans;
// Select leave variable
double mn = INF;
for (int i = 1; i <= m; ++i)
if (a[i][enter] > eps && mn > b[i] / a[i][enter]) {
mn = b[i] / a[i][enter];
leave = i;
}
if (mn == INF) return INF;
pivot(leave, enter);
}
}


## Formulating Problems

• Shortest Path
• Maximize $d_t$
• subject to $d_v\leq d_u+w(u,v),d_s=0$
• Maximum Flow
• Maximize $\sum_{v\in V}f_{sv}-\sum_{v\in V}f_{vs}$
• subject to $f_{uv}\leq c(u,v),\sum_{v\in V}f_{vu}=\sum_{v\in V}f_{uv},f_{uv}\geq 0$
• Minimum-cost Flow
• Minimize $\sum_{(u,v)\in E}a(u,v)f_{uv}$
• subject to $f_{uv}\leq c(u,v), \sum_{v\in V}f_{vu}-\sum_{v\in V}f_{uv}=0,f_{uv}\geq 0,\sum_{v \in V}f_{sv}-\sum_{v\in V}f_{vs}=d$
• Multicommodity Flow
• Minimize $0$
• subject to $\sum_{i=1}{k}f_{iuv}\leq c(u,v),\sum_{v\in V}f_{iuv}-\sum_{v\in V}f_{ivu} = 0,\sum_{v\in V}f_{is_iv}-\sum_{v\in V}f_{ivs_i}=d_i,f_{iuv}\geq 0$
• vertex cover

$$\min \sum_{v\in V}x_v\newline s.t. \sum_{v\in e}x_v\geq 1,e\in E\newline x_v\in {0,1},v\in V$$

• System of difference contraints
• subject to: $x_i-x_j\leq c_k$ ($m$ pairs)

## Duality

• Prime

$$\min c^Tx\newline s.t.\ Ax\geq b\newline x\geq 0$$

• Dual

$$\max b^Ty\newline s.t.\ y^TA\leq c^T\newline y\geq 0$$

prime dual
$\max c_1x_1+\cdots+c_nx_n$ $\min b_1y_1+\cdots+b_my_m$
$a^Tx\geq b$ $y_i\leq 0$
$a^Tx=b$ -
$a^Tx\leq b$ $y_i\geq 0$
- $y_i=0$
$x_i\geq 0$ $a^Ty\geq c$
$x_i\leq 0$ $a^Ty\leq c$
- $a^Ty=c$
$x_i=0$ -
• Weak Duality Theorem: $\forall$ feasible primal solution $x$ and dual solution $y$

$$y^Tb\leq y^TAx\leq c^Tx$$

• Strong Duality Theorem: Primal LP has finite optimal solution $x^*$ iff dual LP has finite optimal solution $y^{T}b=c^Tx^$
• Complementary Slackness Condition: $\forall$ feasible primal solution $x$ and dual solution $y$, both $x$ and $y$ are optimal iff

$$\forall i:A_{i\cdot}x=b_i\vee y_i=0\newline \forall j:y^TA_{\cdot j}=c_j\vee x_j=0$$

• Relaxed Complementary Slackness: $\forall$ feasible primal solution $x$ and dual solution $y$, for $\alpha,\beta\geq 1$

$$\forall i:A_{i\cdot}x\leq \alpha b_i\vee y_i=0\newline \forall j:y^TA_{\cdot j}=\frac{c_j}{\beta}\vee x_j=0\newline \Rightarrow c^Tx\leq\alpha\beta b^Ty\leq\alpha\beta\text{OPT}_{\text{IP}}$$

• Fundamental theorem of linear programming: Any linear program L, given in standard form, either:
• has an optimal solution with a finite objective value
• infeasible
• unbounded

## Primal-Dual Schema

• The Primal-Dual Schema
• Write down an LP-relaxation and its dual
• Start with a primal infeasible solution $x$ and a dual feasible solution $y$ (usually $x=0,y=0$)
• Raise $x$ and $y$ until $x$ is feasible:
• raise $y$ until some dual constrints gets tight $y^TA_{\cdot j}=c_j$
• raise $x_i$ (integrally) corresponding to the tight dual constraints
• Show the complementary slackness conditions
• $\forall i, A_{i\cdot}x\leq\alpha b_i$ or $y_i=0$
• $\forall j,y^TA_{\cdot j}=c_j$ or $x_j=0$
• $c^Tx\leq\alpha b^Ty\leq\alpha\text{OPT}$
• Integrality Gap: $\sup_I\frac{\text{OPT}(I)}{\text{OPT}_{\text{LP}}(I)}$

### Vertex Cover

• Primal

$$\min \sum_{v\in V}x_v\newline s.t.\ \sum_{v\in e}x_v\geq 1,\forall e\in E\newline x_v\in{0,1},\forall v\in V$$

• Dual

$$\max \sum_{e\in E}y_e\newline s.t.\ \sum_{e\owns v}y_e\leq 1,\forall v\in V\newline y_e\geq 0,\forall e\in E$$

• Initially $x=0,y=0$
• Raise $x$ and $y$ until $x$ is feasible
• pick an $e\in E$ and raise $y_e$ to 1, set $x_v=1$ for $v\in e$ and delete all $e\owns v$ from $E$
• Find a maximal matching and return the set of matched vertices
• Integrality Gap: $2$

### Facility Location

• Facility location $\in\text{NPH}$
• Instance
• $F$: Facilities
• $C$: clients
• $f: F\rightarrow[0,\infty)$: Facility opening costs
• $c: F\times C\rightarrow [0,\infty)$: Facility connecting cost
• total cost: $\sum_{j\in C}c_{\phi(j),j}+\sum_{i\in I}f_i$
• Find $I\subset F$ and $\phi:C\rightarrow I$ minimize total cost
• Metric Facility Location: $c_{\phi(j),j}=d_{\phi(j)j}$
• triangle inequality: $d_{i_1j_1}+d_{i_2j_1}+d_{i_2j_2}\geq d_{i_1j_2}$
• Primal

$$\min \sum_{i\in F,j\in C}d_{ij}x_{ij}+\sum_{i\in F}f_iy_i\newline s.t.\ y_i-x_{ij}\geq0,\forall i\in F,j\in C\newline \sum_{i\in F}x_{ij}\geq 1,\forall j\in C\newline x_{ij},y_i\in{0,1},\forall i\in F,j\in C$$

• Dual

$$\max\sum_{j\in C}\alpha_j\newline s.t.\ \alpha_j-\beta_{ij}\leq d_{ij},\forall i\in F,j\in C\newline \sum_{j\in C}\beta_{ij}\leq f_i,\forall i\in F\newline \alpha_j,\beta_{ij}\geq 0,\forall i\in F,j\in C$$

• Initially $\alpha=0,\beta=0$
• raise $\alpha_j$ for all client $j$ simultaneously at a uniform continous rate
• upon $\alpha_j=d_{ij}$ for a closed facility $i$: edge $(i,j)$ is paid, fix $\beta_{ij}=\alpha_j-d_{ij}$
• upon $\sum_{j\in C}\beta_{ij}=f_i$: tentatively open facility $i$; all unconnected clients $j$ with paid edge $(i,j)$ to facility $i$ are declared connected to facility $i$ and stop raising $\alpha_j$
• upon $\alpha_j=d_{ij}$ for an unconnected client $j$ and tentatively open facility $i$: client $j$ is declared connected to facility $i$ and stop raising $\alpha$
• Integrality Gap: $3$

## LP Relaxation & Rounding

• Represent problem as Integer Linear Program(ILP)
• Relaxation: relax ILP to LP
• Find the optimal fractional solution $x^*$ of LP
• ellipsoid
• interior-point
• Rounding: round the solution to a feasible integral solution $\hat x$
• Integrality Gap = $\sup_I\frac{\text{OPT}(I)}{\text{OPT}_{\text{LP}}(I)}$

### Vertex Cover

Rounding

$$\hat x_v=\begin{cases}1&x_v^*\geq 0.5\newline 0&o.w.\end{cases}$$

Integrality Gap: $2$

### MAX-SAT

#### Random solution

$$P(C_j\text{ is satisfied})\geq(1-2^{-k})y_j^*$$

$\frac{1}{2}$-approximation

#### LP relaxation and randomized roudning

$$\max \sum_{j=1}^my_j\newline s.t. \sum_{i\in S_j^+}x_i+\sum_{i\in S_j^-}(1-x_i)\geq y_j\newline x_i\in{0,1},y_j\in{0,1}$$

Random Rounding

$$\hat x_i=\begin{cases}1& w.p.\ x_i^\newline 0& w.p.\ 1-x_i^\end{cases}$$

Analysis

$$P(C_j\text{ is satisfied})\geq(1-(1-\frac{1}{k})^k)y_j^\geq(1-\frac{1}{e})y_j^\newline E[\text{# of satisfied clauses}]\geq(1-\frac{1}{e})\text{OPT}$$

$(1-\frac{1}{e})$-approximation

#### Combination

Sample random solution, satisfy $m_1$ clauses
Randomized rounding LP-relaxation, satisfy $m_2$ clauses

$$E[\max(m_1,m_2)]\geq E[\frac{m_1+m_2}{2}]\geq\frac{3}{4}\text{OPT}$$

Integrality gap: $\frac{3}{4}$
MAX-3SAT has a $\frac{7}{8}$-approximation algorithm by semidefinite programming and cannot have $>\frac{7}{8}$-approx unless NP=P