Vincec's Dimension

# Algorithm Review Notes - Linear Programming

Word count: 503 / Reading time: 3 min
2018/11/26 Share

# Fundamental Theorem

• The solution of LP problem must occur at a vertex or corner point, of the feasible set S associated with the problem
• IIf the objective function P is optimized at two adjacent vertices of S, then it is optimized at every point on the line segment joining these vertices, infinitely many solutions to the problem.

# Exitence of Solution

Given a feasible set S and objective function P,

1. If S is bounded, LP has an optimal solution, P has a max
2. If S is unbounded, may or may not be the LP solution
3. If S is empty set, then LP has no solution: infeasible

# (Maximization) Standard LP Form

• max(c1x1 + … + cnxn)
• a11x1 + … + c1nxn ≤ b1
• am1x1 + … + cmnxn ≤ b1
• x1 ≥ 0, …, xn ≥ 0

# (Maximization) Standard LP in Matrix Form

• column vector c = (c1, …, cn)
• column vector x = (x1, …, xn)
• size of A is n*m, right hand side b = (b1, …, bm)
• max(cT * x)
• A*x ≤ b
• x ≥ 0

# Linear Programming

## Max-Flow

• max(Σfin-t) #all edge flow to the target(sink)
• 0 ≤ each edge (u, v) ≤ weight(edge)
• Conservation law: flow-in = flow-out for each vertex

## Shortest Path

da means the cost for start point to node a.

• max(dt), since dt ≤ du + c(u-t) always happen
• d1 ≤ ds + c(s-1), d1 ≤ d2 + c(2-1)…
• ds = , d1, …, dn, dt ≥ 0

When calculate max(dt), we can get d1, …, dn, the shorest path from s to v is v

## 0-1 Knapsack Problem (Integer Linear Programming problem)

1…n weight w1, w2, …, wn, value v1, v2, …, vn, Knapsack cap = W

• max(Σk = 1…nvk * xk), xk could be 0, or 1
• 0 ≤ Σk = 1…nwk * xk ≤ W
• xk is in {0, 1}
• k = 1, …, n

# Integer Linear Programming problem (ILP)

ILP is NP-Hard

Independent Set ≤p ILP

# Dual LP

To every linear program, there is a dual linear program

### Duality

• The dual of the standard maximum problem change to standard minimum problem, is important for the nonlinear LP
• Transform max(c1x1 + … + cnxn) to min(b1y1 + … + bmym)

### Weak duality

• opt(primal) ≤ opt(dual)
• If x is a feasible solution for P and y is a feasible solution for D, then cT x ≤ bT y
• If a standard problem and its dual are both feasible, then both are feasible bounded (F. B.), P, D feasible -> P, D feasible bounded
• If one problem has an unbounded solution, then the dual of that problem is infeasible, P unbounded -> D infeasible

Proof
cT x = xT c ≤ xT(AT y) = (A x)T y ≤ bT y

### Strong duality

• opt(primal) = opt(dual)
• If x is a feasible solution for P and y is a feasible solution for D, then cT x = bT y
1. P feasible bounded -> D feasible bounded
2. P infeasible -> D feasible unbounded
3. P feasible unbounded -> D infeasible
4. P infeasible -> D infeasible
5. Otherwise is false

Ax = b:

• Ax ≤ b
• -Ax ≤ -b

# NonLinear Optimization

Using Lagrange Multipliers

• slides

Author: VINCEC