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)


source

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

Dual equality form

Ax = b:

  • Ax ≤ b
  • -Ax ≤ -b

Dual relationships


source

NonLinear Optimization

Using Lagrange Multipliers

Reference

  • slides
CATALOG
  1. 1. Fundamental Theorem
  2. 2. Exitence of Solution
  3. 3. (Maximization) Standard LP Form
  4. 4. (Maximization) Standard LP in Matrix Form
  5. 5. Linear Programming
    1. 5.1. Max-Flow
    2. 5.2. Shortest Path
    3. 5.3. 0-1 Knapsack Problem (Integer Linear Programming problem)
  6. 6. Integer Linear Programming problem (ILP)
  7. 7. Dual LP
    1. 7.0.1. Duality
    2. 7.0.2. Weak duality
    3. 7.0.3. Strong duality
    4. 7.0.4. Dual equality form
    5. 7.0.5. Dual relationships
  • 8. NonLinear Optimization
  • 9. Reference