Linear Programming

• Maximizing or minimizing an objective function under a list of constraints
• Each constraint is a linear inequation forming a half-space
• Optimum is reached at vertices unless:
1. program is infeasible, e.g. \(x \leq 1, x \geq 2\)
2. program is unbounded, i.e. it's possible to reach arbitrarily high/low values

Simplex Algorithm

• Start at a vertex, looks at neighboring vertices for a higher value
• Does hill-climbing on the vertices.
• Local optimality implies global optimality
• • - if all neighbours are on one side of the "profit" plane, the rest must also be on the same side

Flows in Networks

• Maximize flow from vertices \(s\) to \(t\) in directed graph \(G = (V,E)\)
• Derived algorithm (what simplex is essentially doing)
• 1. Start with 0 flow
  2. Choose an appropriate path from s to t, and increase flow as much as possible along this path.
• Simplex allows paths to cancel existing flow
• For each iteration, the \(s-t\) path has edges \((u, v)\) that:
• 1. Are in the original network, and is not at full capacity, or
  2. Is the reverse of an edge \((v, u)\) in the network, and has flow along it
• Residual network \(G^f\)
• \(c^f = \begin{cases} c_{uv}-f_{uv} & \text{if $(u,v) \in E$ and $f_{uv} < c_{uv}$} \\ f_{vu} & \text{if $(v,u) \in E$ and $f_{vu}>0$} \end{cases}\)
• For any flow \(f\) and any \((s,t)\)-cut \((L,R)\), size(\(f\)) \(\leq\) capacity \((L,R)\)
• Max-flow min-cut theorem The size of the maximum flow in the network equals the capacity of the smallest \({s,t}\)-cut
• Min-cut \((L,R)\): \(L\) is all the nodes reachable in the residual graph \(G^f\) from \(s\) at final flow, \(R = V - L\). Any edge from \(L\) to \(R\) must have max flow, any edge from \(R\) to \(L\) must have 0 flow.
• Use residual network with derived algorithm instead
• \(O(|E|)\) to find \(s-t\) path for each iteration.
• Number of iterations is at most \(O(|V| \cdot |E|)\) if paths are found with BFS (path with fewest edges)
• Overall runtime for maximum flow:\(O(|V|\cdot |E|^2)\)
• Guarantees integrality if all edge capacities are integral. (see derived algorithm)

Bipartite Matching

• Can be cast to max-flow
• Add source node connected to one partition, sink to other; Set all capacities to 1.

Duality

• Every linear maximization problem has a dual linear minimization problem
• Variables of dual are multipliers of the inequalities of primal
• Example Problem
• • \(\begin{align} \text{max } x_1 &+ 6x_2 \\ x_1 &\leq 200 \\ x_2 &\leq 300 \\ x_1 + x_2 &\leq 400 \\ x_1, x_2 &\geq 0 \end{align}\)
  • \(\begin{alignat*}{3} \text{Multiplier}\qquad& \text{Inequality}&&\\ y_1\qquad& x_1&&\leq 200 \\ y_2\qquad& x_2 &&\leq 300 \\ y_3\qquad& x_1 + x_2 &&\leq 400 \\ \end{alignat*}\)
  • \((y_1 + y_3)x_1 + (y_2 + y_3)x_2 ≤ 200y_1 + 300y_2 + 400y_3\)
  • \( x_{1}+6 x_{2} \leq 200 y_{1}+300 y_{2}+400 y_{3} \quad \text { if } \quad \left\{\begin{array}{c}{y_{1}, y_{2}, y_{3} \geq 0} \\ {y_{1}+y_{3} \geq 1} \\ {y_{2}+y_{3} \geq 6}\end{array}\right\} \)
  • So the initial problem has a dual minimization problem:
    
    \( \begin{array}{c}{\min 200 y_{1}+300 y_{2}+400 y_{3}} \\ {y_{1}+y_{3} \geq 1} \\ {y_{2}+y_{3} \geq 6} \\ {y_{1}, y_{2}, y_{3} \geq 0}\end{array} \)
• Dual feasible values \(\geq\) Primal feasible values
• The optima for dual and primal coincide
• 
• Relation between Dual and Primal:
  \( \begin{array}{c}{\text { Primal LP: }} \\ { \text {max } \mathbf{c}^{T} \mathbf{x}} \\ {\mathbf{A} \mathbf{x} \leq \mathbf{b}} \\ {\quad\mathbf{x} \geq 0}\end{array} \qquad \begin{array}{c}{\text { Dual LP: }} \\ {\text { min } \mathbf{y}^{T} \mathbf{b}} \\ {\mathbf{y}^{T} \mathbf{A} \geq \mathbf{c}^{T}} \\ {\quad\mathbf{y} \geq 0}\end{array} \)
• Duality theorem If a linear program has a bounded optimum, then so does its dual, and the two optimum values coincide
• The dual of the max-flow problem is the min-cut problem

Bipartite Matching

• Match vertices in bipartite graphs / find set of edges \(M\) such that each vertex is adjacent to at most 1 edge in \(M\) and \(M\) has maximum size
• Alternating paths: paths that has edges alternating between \(M\) and \(E \setminus M\)