Review of Linear Programming

Review of Linear Programming 1 Overview Describe LP and IP min cost flow as an LP Graphical solution Basic feasible solutions. Simplex Method Basic feasible solutions in matrix form Duality Note: this will cover lots of material. We will also have a recitation. 2 The Minimum Cost Flow Problem uij = capacity of arc (i,j). cij = unit cost of shipping flow from node i to node j on (i,j). xij = amount shipped on arc (i,j) ∑(i,j)∈A cijxij Minimize ∑j xij - ∑k xki = bi for all i ∈ N. and 0 ≤ xij ≤ uij for all (i,j) ∈ A. 3 Terminology xij = Decision variable. Describes a decision to be made Minimize ∑j xij - ∑(i,j)∈A cijxij ∑k xki = bi Objective Function for all i ∈ N. Constraints and 0 ≤ xij ≤ uij for all (i,j) ∈ A. 4 Terminology Minimize ∑j xij - ∑(i,j)∈A cijxij ∑k xki = bi Objective Function for all i ∈ N. Constraints and 0 ≤ xij ≤ uij for all (i,j) ∈ A. In a linear program, the objective function and the constraints are all linear. Typically, but not always, the variables are constrained to be non-negative. If variables are constrained to be integers, it is called an integer program. 5 Some Applications of LPs + IPs Production Planning: Given several products with varying production requirements and cost structures, determine how much of each product to produce in order to maximize profits. Scheduling: Given a staff of people, determine an optimal work schedule that maximizes worker preferences while adhering to scheduling rules. Portfolio Management: Determine bond portfolios that maximize expected return subject to constraints on risk levels and diversification. And an incredible number more. 6 Graphing 2-Dimensional LPs Optimal Solution y Example 1: 4 Maximize x+y Subject to: x + 2 y ≥ 2 x≤3 3 Feasible Region 2 y≤4 x≥0 y≥0 1 0 These LP animations were created by Keely Crowston. x 0 1 2 3 7 Graphing 2-Dimensional LPs y Example 2: 4 Minimize ** Multiple Optimal Solutions! x-y Subject to: 1/3 x + y ≤ 4 -2 x + 2 y ≤ 4 3 2 Feasible Region x≤3 x≥0 y≥0 1 0 0 1 2 3 x 8 Graphing 2-Dimensional LPs y Example 3: 40 Minimize x + 1/3 y Subject to: x + y ≥ 20 -2 x + 5 y ≤ 150 30 Feasible Region 20 x≥5 x≥0 y≥0 10 x Optimal Solution 0 0 10 20 30 40 9 Do We Notice Anything From These 3 Examples? y y y 4 4 40 3 3 30 2 2 20 1 1 10 0 0 1 2 3 x 0 0 1 2 3 x 0 x 0 10 20 30 40 A Fundamental Point y y y 4 4 40 3 3 30 2 2 20 1 1 10 0 0 1 2 3 x 0 0 1 2 3 x 0 x 0 10 20 30 40 If an optimal solution exists, there is always a corner point optimal solution! 11 Graphing 2-Dimensional LPs Second Corner pt. Example 1: Optimal Solution y 4 Maximize x+y Subject to: x + 2 y ≥ 2 x≤3 3 Feasible Region 2 y≤4 x≥0 y≥0 1 Initial 0 Corner pt. x 0 1 2 3 12 And We Can Extend this to Higher Dimensions 13 Then How Might We Solve an LP? † The constraints of an LP give rise to a geometrical shape - we call it a polyhedron. † If we can determine all the corner points of the polyhedron, then we can calculate the objective value at these points and take the best one as our optimal solution. † The Simplex Method intelligently moves from corner to corner until it can prove that it has found the optimal solution. 14 But an Integer Program is Different y h Feasible region is a set of discrete points. h Can’t be assured a 4 3 corner point solution. h There are no “efficient” 2 ways to solve an IP. h Solving it as an LP provides a relaxation and a bound on the solution. 1 0 0 1 2 3 x 15 Linear Programs in higher dimensions maximize z= subject to -4x1 + x2 - x3 + x4 -7x1 + 5x2 + x3 + x4 = 8 -2x1 + 4x2 + 2x3 - x4 x1, x2, x3, x4 ≥ = 10 0 We will describe LPs that start with the following form: •equality constraints •non-negative RHS •nonnegative variables 16 Basic Feasible Solutions maximize subject to z= -4x1 + x2 - x3 + x4 -7x1 + 5x2 + x3 + x4 = 8 -2x1 + 4x2 + 2x3 - x4 x1, x2, x3, x4 ≥ = 10 0 Suppose there are m constraints, n variables A basic solution is found by setting n-m variables to 0 and solving the remaining system with n variables and n constraints. •The n – m variables are called non-basic variables •The m variables are called basic variables 17 Basic Feasible Solutions maximize z= subject to -4x1 + x2 - x3 + x4 -7x1 + 5x2 + x3 + x4 = 8 -2x1 + 4x2 + 2x3 - x4 = 10 ≥ 0 1 = 0 1 1 = 8 2 -1 = 10 x1, x2, -z x1 x2 x3 x4 1 -4 1 -1 0 -7 5 0 -2 4 x3, x4 18 Basic Feasible Solutions -z x1 x2 x3 x4 1 -11 -4 1 6 -1 0 1 2 = 8 0 0 -7 5 1 1 = 8 0 12 -2 4 6 2 0 -1 -3 = 10 -6 Example: Suppose we want the solution with basic variables x3 and x4, and thus x1 and x2 are non-basic. We then perform pivot operations. 19 Basic Feasible Solutions -z x1 x2 x3 x4 1 -11 -4 -3 1 6 2 -1 0 1 2 0 = 0 4 8 0 -7 -3 5 3 1 1 0 = 8 6 0 12 -2 -4 4 6 2 2 0 -3 1 = 10 -6 2 Next pivot on the –3. 20 Basic Feasible Solutions Canonical form: basic variables have a single one in the column. -z x1 x2 x3 x4 reduced costs 1 -11 -4 -3 1 6 2 -1 0 1 2 0 = 0 4 0 -7 -3 5 3 1 1 0 = 8 6 0 12 -2 -4 4 6 2 2 0 -1 -3 1 = 10 -6 2 The basic solution is found by setting non-basic variables to 0. We get x1=0, x2=0, x3=6, x4=2. This solution also satisfies x ≥ 0. It is called a basic feasible solution. 21 More on Basic Feasible Solutions Each corner point solution of the polyhedron is a basic feasible solution. The simplex method is a systematic way of moving from one basic feasible solution to another, always improving the solution, until the optimum solution is obtained. The network simplex algorithm is a special case of the simplex algorithm. 22 The Simplex Algorithm z = -3x1 + 2x2 - 4 -z x1 x2 x3 x4 1 -3 2 0 0 = 4 0 -3 3 1 0 = 6 0 -4 2 0 1 = 2 The entering variable for a max problem is a variable with positive reduced cost. The pivot element is chosen uniquely in the column of the entering variable so that the next basis is feasible. 23 The Simplex Algorithm The pivot element is chosen according to a min ratio rule. -z x1 x2 x3 x4 1 -3 1 2 0 0 -1 0 = -2 4 0 -3 3 3 0 1 -1.5 0 = 6 3 0 -4 -2 2 1 0 .5 1 = 2 1 A pivot is carried out, leading to the next bfs. Variable x4 has left the basis. The new basis consists of x2 and x3. 24 The Simplex Algorithm Pivots are carried out until the bfs is optimal. -z x1 x2 x3 x4 1 -3 1 0 2 0 -1/3 0 -1/2 -1 0 = -2 -3 4 0 -3 3 1 3 0 1/3 1 -1/2 -1.5 0 = 6 3 1 0 -4 -2 0 2 1 2/3 0 -1/2 .5 1 = 2 1 3 z = -x3/3 – x4/2 + 3 This new bfs is optimal. Increasing x3 or x4 makes the solution worse. 25 The Simplex Algorithm -z x1 x2 x3 x4 1 -3 1 0 2 0 -1/3 0 -1/2 -1 0 = -2 -3 4 0 -3 3 1 3 0 1/3 1 -1/2 -1.5 0 = 6 3 1 0 -4 -2 0 2 1 2/3 0 -1/2 .5 1 = 2 1 3 Optimality conditions for a maximization problem: all reduced costs are non-positive. 26 Network Simplex We have already seen network simplex. In the following, we show a connection between network simplex and ordinary simplex. 27 Network Simplex Algorithm 1 1 -6 2 1 2 4 3 6 -4 5 3 In the min cost flow problem, there are n constraints, one for each node, but one constraint 7 3 is redundant. Basic solutions correspond to spanning trees. 28 We can calculate the bfs directly 1 1 4 3 -6 2 6 1 2 2 4 7 4 3 3 This corresponds to solving the system of equations. 6 -4 3 5 3 29 We calculate node potentials directly 1 5 -6 2 -4 3 3 -2 4 7 6 1 5 30 We calculate node potentials directly 5 -6 -5 2 -4 3 -2 3 -2 -4 4 Node potentials are chosen so that reduced costs of tree arcs are 0. 0 1 7 -6 6 -1 1 5 -1 We can then determine the reduced costs of non-basic arcs directly. cπij = cij – πi + πj. 31 Entering and Leaving variables The entering variable is chosen so that it violates its optimality condition. (same as for simplex) The exiting variable is chosen so that the next spanning tree solution is feasible. Determined by sending flow around a cycle. So, operations on the trees avoid all of the matrix manipulations. 32 Simplex Method in Matrix Form xB: basic variables of final tableau xL: non-basic variables of final tableau Rearranging columns, we can express the LP as: A = [B L]: the original constraint matrix c = [cB cL]: the original objective coefficient vector Initial Problem: Maximize z = cB xB + cL xL B x B + L xL = b x B , xL ≥ 0 33 Basic Feasible Solutions in Matrix Form Initial Problem: minimize z = cB xB + cL xL B x B + L xL = b x B , xL ≥ 0 Let the bar above a vector or matrix represent the updated values in the tableau after pivoting. Final System in canonical form (after pivoting): minimize - -z + ⎯cL xL = - z0 xB + ⎯L xL =⎯b x B, x L ≥ 0 34 ⎯L and⎯b Start with: B xB + L xL = b B-1B xB + B-1 L xL = B-1 b xB + B-1 L xL = B-1 b --> ⎯L= B-1 L, and ⎯b= B-1 b, The basic feasible solution is obtained by setting xL to 0. Therefore, xB = B-1 b. 35 ⎯cL Start with: z = cB xB + cL xL z = cB (B-1 b - B-1 L xL ) + cL xL z = cB B-1 b + (cL - cB B-1 L ) xL Î ⎯cL= cL - cB B-1 L and ⎯z= cB B-1 b, There is no coefficient for xB in the final system. So, we substitute for xB. 36 Notation: let π = cBB-1 Start with: z = cB xB + cL xL ⎯cL = cL - cB B-1 L and ⎯z= cB B-1 b, ⎯cL = cL - π L and ⎯z= π b, π is called the vector of simplex multipliers. 37 Duality via the Lagrangian Primal Problem minimize subject to P z = cx Ax = b x≥0 optimum value is z* Lagrangian Problem D(π) minimize subject to v(π)= cx - π(Ax – b) x≥0 optimum value is v*(π) Note: if x* is feasible for P, then it is also feasible for D(π). Thus v*(π) ≤ z*, and D(π) provides a lower bound for P. 38 Computing the Highest Lower Bound Lagrangian Problem D(π) minimize subject to v(π)= cx - π(Ax – b) = (c-πA)x + πb x≥0 v(π)= -∞ unless (c-πA) ≥ 0. v(π)= πb if (c-πA) ≥ 0 The highest lower bound is found by solving maximize v = πb subject to c-πA ≥ 0 39 Primal Problem P minimize z = cx subject to Ax = b x≥0 Dual Problem maximize subject to D v = πb πA ≤ c optimum value is z* optimum value is v* Theorem. (Strong Duality) If both P and D are feasible, then z* = v*. 40 PRIMAL PROBLEM: maximize subject to z= 3x1 + 4x2 +6x3 + 8x4 x1 + x2 + x3 + x4 2x1 + 3x2 +4x3 + 5x4 x1, x2, x3, x4 = = ≥ 1 3 0 Observation 1. DUAL PROBLEM: minimize y1 + 3y2 Subject to y1 + 2y2 ≥ 3 y1 + 3y2 ≥ 4 y1 + 4y2 ≥ 6 y1 + 5y2 ≥ 8 The constraint matrix in the primal is the transpose of the constraint matrix in the dual. Observation 2. The RHS coefficients in the primal become the cost coefficients in the dual. PRIMAL PROBLEM: maximize subject to z= 3x1 + 4x2 +6x3 + 8x4 x1 + x2 + x3 + x4 2x1 + 3x2 +4x3 + 5x4 x1, x2, x3, x4 DUAL PROBLEM: minimize y1 + 3y2 Subject to y1 + 2y2 ≥ 3 y1 + 3y2 ≥ 4 y1 + 4y2 ≥ 6 y1 + 5y2 ≥ 8 = = ≥ 1 3 0 Observation 3. The cost coefficients in the primal become the RHS coefficients in the dual. Observation 4. The primal (in this case) is a max problem with equality constraints and non-negative variables The dual (in this case) is a minimization problem with ≥ constraints and variables unconstrained in sign. The min cost flow problem and its dual ∑(i,j)∈A cijxij Minimize ∑j xij - and xij ≥ 0 for all (i,j) ∈ A. Minimize ∑ n i=1 ∑k xki = bi for all i ∈ N. π i bi Primal Dual subject to π i − π j ≤ cij for all ( i , j ) ∈ A 43 Summary Describe LP and IP min cost flow as an LP Graphical solution Basic feasible solutions. Simplex Method Basic feasible solutions in matrix form Duality 44