PDF of Eric’s written notes are here.

Max-flow via Linear Programming

Variables f_e for every e\in E. Objective function: \max\sum_{\overrightarrow{sz}\in E}f_{sz}. Constraints: for every e\in E, 0\le f_e\le c_e, for every v\in V-\{s,t\}, \sum_{\overrightarrow{wv}\in E}f_{wv}=\sum_{\overrightarrow{vz}\in E}f_{vz}.

Standard form for LP

n variables x=\begin{pmatrix} x_1\\\vdots\\x_n\end{pmatrix}, m constraints A=\begin{pmatrix} a_{11} & \cdots & a_{1n}\\ \vdots & \ddots & \vdots \\ a_{m1} & \cdots & a_{mn} \end{pmatrix}, objectives c=\begin{pmatrix} c_1\\\vdots\\c_n\end{pmatrix}, and b=\begin{pmatrix} b_1\\\vdots\\b_m\end{pmatrix}. We want to maximize c^Tx subject to Ax\le b, x\ge 0. (for example refer to the written notes)

                          Primal LP                                                    Dual LP

\begin{aligned}  \max c^Tx\text{ s.t. }Ax\le b, x\ge 0 &\qquad\overrightarrow{\text{dual}} & \min b^Ty\text{ s.t.}A^ty\ge c, y\ge 0\\  \uparrow\text{ standard form} & & \downarrow\text{ standard form} \\  \min -c^Tx\text{ s.t. }-Ax\ge -b, x\ge 0 &\qquad\underleftarrow{\text{dual}} & \max -b^Ty\text{ s.t.} -A^Ty\le -c, y\ge 0  \end{aligned}

So dual(dual)=primal.

For a LP, optimum is achieved at a vertex of the feasible region except if

  • it’s infeasible (e.g.: x_1\le 100 & x_1\ge 200), so feasible region is empty
  • it’s unbounded (e.g.: \max x_1+x_2 s.t. x_1, x_2\ge 0)

Weak duality theorem

For a LP whose primal and dual are feasible, their optimum x^* and y^* satisfy c^Tx^*\le b^Ty^*

Consequence: if we have a feasible x of primal LP and a feasible y of dual LP, and c^Tx=b^Ty, then x and y are optimal solutions.

Strong duality theorem

If primal LP has optimal x^* and dual LP has optimal y^*, then c^Tx^*=b^Ty^*.

If primal LP is unbounded, then dual LP is infeasible.

If dual LP is unbounded, then primal LP is infeasible.

Line fitting

Given points (x_1,y_1), (x_2,y_2),\dots,(x_n,y_n), find the line y=ax+b which minimizes the maximum distance.

Variables: a, b, e. Goal: minimize e where for all I, |y_i-(ax_i+b)|\le e

Example: (x_1,y_1)=(1,1), (x_2,y_2)=(2,1), (x_3,y_3)=(3,2).

LP Problem: variables a,b,e, minimize e s.t.

  • |1-a-b|\le e\longrightarrow 1-a-b\le e, 1-a-b\ge -e
  • |1-2a-b|\le e\longrightarrow 1-2a-b\le e, 1-2a-b\ge -e
  • |2-3a-b|\le e\longrightarrow 2-3a-b\le e, 2-3a-b\ge -e

In standard form, maximize -e, s.t.

  • -a-b-e\le -1
  • a+b-e\le 1
  • -2a-b-e\le -1
  • 2a+b-e\le 1
  • -3a-b-e\le -2
  • 3a+b-e\le 2

How to get nonnegative constraints? Make variables a^+,a^-,b^+,b^-,e^+,e^-, and replace a=a^+-a^-, b=b^+-b^-, e=e^+-e^-.

New LP becomes: maximize -e^++e^- s.t.

  • -(a^+-a^-)-(b^+-b^-)-(e^+-e^-)\le -1
  • (a^+-a^-)+(b^+-b^-)-(e^+-e^-)\le 1
  • -2(a^+-a^-)-(b^+-b^-)-(e^+-e^-)\le -1
  • 2(a^+-a^-)+(b^+-b^-)-(e^+-e^-)\le 1
  • -3(a^+-a^-)-(b^+-b^-)-(e^+-e^-)\le -2
  • 3(a^+-a^-)+(b^+-b^-)-(e^+-e^-)\le 2
  • a^+,a^-,b^+,b^-,e^+,e^-\ge 0

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s