Linear Programming

1.  Linear programming:

    --  Problem-solving model for optimal allocation of scarce resources, among a number of competing activities.

    --  Fast commercial solvers available.

    --  Widely applicable problem-solving model.

    --  Key subroutine for integer programming solvers.

 

2.  brewer’s problem: choose product mix to maximize profits.

    --  formulation:

        --  Let A be the number of barrels of ale.

        --  Let B be the number of barrels of beer.

        --  maximize 13A + 23B subject to the constraints :

            -  5A + 15B ≤ 480

            -  4A + 4B ≤ 160

            -  35A + 20B ≤ 1190

            -  A , B ≥ 0

     --  feasible region:

    --  Optimal solution occurs at an extreme point.(intersection of 2 constraints in 2d)

3.  Standard form linear program：

    --  Maximize linear objective function of n nonnegative variables, subject to m linear equations. (linear means no x^2, xy, arccos(x), etc.)

    --  Input: real numbers aij, cj, bi.

    --  Output: real numbers xj.

4.  Converting the brewer’s problem to the standard form:

    --  Original formulation:

        maximize 13A + 23B subject to the constraints:

        -  5A + 15B ≤ 480

        -  4A + 4B ≤ 160

        -  35A + 20B ≤ 1190

        -  A , B ≥ 0

    --  Transformation:

        -  Add variable Z and equation corresponding to objective function.

        -  Add slack variable to convert each inequality to an equality.

        -  Now a 6-dimensional problem:

5.  Geometry of Linear Programming:

    --  Inequalities define halfspaces; feasible region is a convex polyhedron.

    --  A set is convex if for any two points a and b in the set, so is ½ (a + b).

    --  An extreme point of a set is a point in the set that can't be written as ½ (a + b), where a and b are two distinct points in the set.

    --  Extreme point optimal iff no better adjacent extreme point. ( local optima are global optima because objective function is linear and feasible region is convex)

 

6.  Simplex algorithm

    -- Generic algorithm:

        --  Start at some extreme point.

        --  Pivot from one extreme point to an adjacent one. (never decreasing objective function)

        --  Repeat until optimal.

    -- BFS:

        --  A basis is a subset of m of the n variables.

        --  Basic feasible solution (BFS):

            --  Set n – m nonbasic variables to 0, solve for remaining m variables.

            --  Solve m equations in m unknowns.

            --  If unique and feasible ⇒ BFS.

            --  BFS ⇔ extreme point.

    --  initialization:

        --  Start with slack variables { SC , SH , SM } as the basis.

        --  Set non-basic variables A and B to 0.

        --  3 equations in 3 unknowns yields SC = 480, SH = 160, SM = 1190.

    --  Pivot

        --  use the variable whose coefficient in objective function is positive to replace some one in the basis. (each unit increase in that variable from 0 increases objective value due to positive coefficient)

        --  which variable to replace: Preserves feasibility by ensuring RHS ≥ 0. Minimum ratio rule: min { 480/15, 160/4, 1190/20 }.

        --  when to stop: When no objective function coefficient is positive.

        --  pivot 1: substitute B = (1/15) (480 – 5A – SC) and add B into the basis (rewrite 2nd equation, eliminate B in 1st, 3rd, and 4th equations)

 

        --  pivot 2: substitute A = (3/8) (32 + (4/15) SC – SH ) and add A into the basis (rewrite 3rd equation, eliminate A in 1st, 2nd, and 4th equations)

     --  Why optimal: Z = 800 – SC – 2 SH, optimal objective value Z* ≤ 800 since SC , SH ≥ 0. Thus, current BFS has value 800 ⇒ optimal.

 

7.  Java Implementation of Simplex:

    --  Encode standard form LP in a single 2D array.

    --  Simplex algorithm transforms initial 2D array into solution:

    --  Implementation:

public class Simplex
{
    private double[][] a; // simplex tableaux
    private int m, n; // M constraints, N variables

    public Simplex(double[][] A, double[] b, double[] c)
    {
        m = b.length;
        n = c.length;
        a = new double[m+1][m+n+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.0;
        for (int j = 0; j < n; j++) a[m][j] = c[j];
        for (int i = 0; i < m; i++) a[i][m+n] = b[i];
    }

    //Find entering column q using Bland's rule: index of first column whose objective function coefficient is positive.
    private int bland()
    {
        for (int q = 0; q < m + n; q++)
            if (a[M][q] > 0) return q;
                return -1;
    }

    //Find leaving row p using min ratio rule.
    private int minRatioRule(int q)
    {
        int p = -1;//leaving row
        for (int i = 0; i < m; i++)
        {
            if (a[i][q] <= 0) continue; //consider only positive entries
            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;
    }

    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.0;
        for (int j = 0; j <= m+n; j++)
            if (j != q) a[p][j] /= a[p][q];
        a[p][q] = 1.0;
    }

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

    --  Performance: In typical practical applications, simplex algorithm terminates after at most 2 (m + n) pivots.

    --  Pivoting rules: Carefully balance the cost of finding an entering variable with the number of pivots needed.

        -  No pivot rule is known that is guaranteed to be polynomial.

        -  Most pivot rules are known to be exponential (or worse) in worst-case.

 

8.  Reduction to standard form:

    --  Minimization problem. Replace min 13A + 15B with max – 13A – 15B.

    --  ≥ constraints. Replace 4A + 4B ≥ 160 with 4A + 4B – SH = 160, SH ≥ 0.

    --  Unrestricted variables. Replace B with B = B0 – B1, B0 ≥ 0 , B1 ≥ 0.

 

9.  Modeling of LP:

    --  1. Identify variables.

    --  2. Define constraints (inequalities and equations).

    --  3. Define objective function.

    --  4. Convert to standard form.

 

10.  Maxflow problem reduces to LP:

    --  Variables. xvw = flow on edge v→w.

    --  Constraints. Capacity and flow conservation.

    --  Objective function. Net flow into t.

11.  bipartite matching reduces to LP:

    --  LP formulation. One variable per pair.

    --  Interpretation. xij = 1 if person i assigned to job j.