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

average

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