[Algorithms II] Week 6-2 Linear Programming

Sun, 21 Feb 2016 Category notes algorithm Series Part 12 of «Algorithms Princeton MOOC II»

1. Brewer-'s Problem
2. Simplex Algorithm
3. Simplex Implementations
4. Linear Programming Reductions

simplex algo: top 10 algo of the 20th century (ever?).

what is linear programming:
a general problem-solving model that works for:
shortest-path, maxflow, MST, matching, assignment, ...

1. Brewer-'s Problem

toy example: choose products to maximize profit.
...
feasible region: a convex polygon.

⇒ optimum solution appears at an extreme point.

standard form of LP

n non-neg variables (j=1..n)
m linear euqations (i=1..m)
input: a_ij, c_j, b_i
output: x_j

to convert inequality to equality (as in the standard form above): add slack var!

def. convex set
for any a and b in set ⇒ 1/2(a+b) is also in set.

extreme point:

def. extreme point
is a point in set that cannot be written as 1/2(a+b) with a b distinct.

extreme point property:
if there exists an potimal solution, then there exists one that is an extreme point.

nb of extreme point is finite
but this nb can be exponential

greedy property:
extreme point is optimal iff no better adj extreme points.

2. Simplex Algorithm

algo. simplex

start at some point

pivot from one extreme point to an adj one (never decrease the obj fcn)

repeat until optimal

We're using the "basis" and "pivoting" to solve LP.

def. basis (基变量) is a subset (size=m) of the n variables.

vars in basis are always non-zero...

basic feasible solution:

set n-m non-basis vars to 0
solve for remaining m vars (with m constraints)
if unique and feasible (matrix invertable)

algo:

initial basic-feasible-solution: start slack vars as basis.
choose a non-basic var as pivot, add it into basis, take some basis var out

ex. pick B as pivot var using constraint 2 (2nd equation):

why picking var B? → its obj coeff is positive
why pivot on 2nd constraint (5A+15B+Sc=480)? →
- RHS > 0 (preserves feasibility)
- minimum ratio rule: min(480/15, 160/4, 1190/20)

stop when no obj-coeff is positive

3. Simplex Implementations

encode standard LP formulation into java 2d array:

public class Simplex{   
    private double[][] a;   
    private int m,n;   
    public Simplex(double[][] A, double[] b, double[] c){   
        m = b.length;   
        n = c.length;   
        a = new double[m+1][n+m+1];   
        for(int i=0; i<m; i++)   
            for(int j=0; j<n; j++)   
                a[i][j] = A[i][j];   
    for(int j=n; j<m+n; j++) a[j-n][j] = 1;      
    for(int j=0; j<m; j++) a[j][n+m] = b[j];    
    for(int j=0; j<n; j++) a[m][j] = c[j];    
    }   
}

simplex algo: just transform initial 2d array into final solution.

choosing pivot variable (find entering column)

Bland's rule. find the first column whose obj-coeff is positive.

private int bland(){   
    for(int q=0; q<m+n; q++)   
        if(a[m][q]>0) return q;   
    return -1;   
}

choosing pivot constraint (find entering row)

minimum ratio rule (if a tie, choose first row).

private int minRatioRule(int q){   
    int p = -1;   
    for(int i=0; i<m; i++){   
        if (a[i][q]<=0) continue;   
        else if (p==-1) p=i;   
        else if (a[i][m+n]/a[i][q] < a[p][m+n]/a[p][q])    
            p=i;   
    }   
    return p;   
}

do the pivot (column q, row p)

like Guassian elimination:

make var q disappear on each row (except for row p);
on row p: make var q's coeff become 1.

public void pivot(int p, int q){   
    for(int i=0; i<m; i++)   
        for(int j=0; j<m+n; j++)   
            if (i!=p && j!=q)   
                a[i][j] -= a[p][j]*a[i][q]/a[p][q];   
    for(int i=0; i<m; i++)    
        if(i!=p) a[i][q] = 0;   
        for(int j=0; j<m+n; j++)   
        if(j!=q) a[p][j] /= a[p][q];   
    a[p][q] = 1;   
}

so the simplex algo is:

public void solve(){   
    while(true){   
        int q = bland();    
        if(q==-1) break; // optimal if -1   
        int p = minRatioRule(q);   
        if(p==-1) break; // unbounded if -1   
        pivot(p,q);   
    }   
}

final solution is just in the array:

remarkable property
in typical applications, simplex terminates after at most 2(m+n) pivots. — whereas nb of extreme points is exp in n !!
ie. LINEAR time in practice!!

other pivot rules: