# Structure, Duality, and Randomization - Common Themes in AI ... Explorations in Artificial Intelligence Prof. Carla P. Gomes [email protected] Module 7 Part 2 Solving Linear Programming Solving LP LP: Algorithms Simplex. (Dantzig 1947) Developed shortly after WWII in response to logistical problems: used for 1948 Berlin airlift. Practical solution method that moves from one extreme point to a neighboring extreme point. Finite (exponential) complexity, but no polynomial implementation known. LP: Polynomial Algorithms Ellipsoid. (Khachian 1979, 1980) Solvable in polynomial time: O(n4 L) bit operations. n = # variables L = # bits in input Theoretical tour de force.

Not remotely practical. Karmarkar's algorithm. (Karmarkar 1984) O(n3.5 L). Polynomial and reasonably efficient implementations possible. Interior point algorithms. O(n3 L). Competitive with simplex! will likely dominate on large problems soon Extends to even more general problems. Simplex Method Simplex Method in Practice The simplex method has exponential time complexity (cn) (worst case complexity). However, in practice it works well in general. Key advantage of simplex methods capability of

performing postoptimality / sensitivity analysis (duality); Key Notion in Simplex: Corner Point Solutions Corner-point feasible solution special solution that plays a key role when the simplex method searches for an optimal solution. Relationship between optimal solutions and CPF solutions: Any LP with feasible solutions and bounded feasible region (1) the problem must possess CPF solutions and at least one optimal solution (2) the best CPF solution must be an optimal solution f the problem has exactly one optimal solution it must be a CFP solution If the problem has multiple optimal solutions, at least two must be CPF solutions Wyndor Glass Production rate Let D = the number of doors to produce W = the number of windows to produce W for windows Maximize P = 3 D + 5 W 8

P = 3600 = 300D + 500W Z=30 Optimal solution 1 (2, 6) P = 3000 = 300D + 500W 6 2 Z=36 Edge of Feasible region Feasible 4 P = 1500 = 300D + 500W region Z=27 2

Z=0 CPF 0 0 2 4 Production rate for doors 6 8 10 D Simplex Key Concepts Concept 1 CPF solutions Simplex methods focuses only on CPF solutions (finite set) Concept 2 Flow of simplex method

Iterative procedure: Initialization find initial CPF solution Optimality test if optimal stop if not optimal go to next iteration Iteration find a better CPF solution; go to 2. Concept 3 Initialization Whenever possible pick the origin; otherwise special procedure Simplex Key Concepts (cont.) Concept 4 Path to optimal solution Simplex methods always chooses a CPF solution adjacent to the current one The entire path to the optimal solution is along the edges of the feasible solution Concept 5 Choice of new CPF solution

From a CPF solution consider all edges emanating from it but it does not solve for each adjacent CPF solution it simply identifies the rate of improvement in Z along a given edge and than it picks the one with the largest improvement Concept 6 Optimality Test From a given CPF solution check if there is an edge that gives a positive rate of improvement in Z. If not, current CPF is optimal. Wyndor Glass Production rate Let D = the number of doors to produce W = the number of windows to produce W for windows Maximize P = 3 D + 5 W 8 P = 3600 = 300D + 500W Z=30 Optimal solution

1 (2, 6) P = 3000 = 300D + 500W 6 2 Z=36 Edge of Feasible region Feasible 4 P = 1500 = 300D + 500W region Z=27 2 Z=0 CPF 0 0

2 4 Production rate for doors 6 8 10 D Augmented Form for Wyndor Glass Maximize Z= 3 x1 + 5 x2 subject to x1 2x2 12 3x1 + 2x2 and x1 0, x2 0 4 18 Maximize Z= 3 x1 + 5 x2 + 0 s1 + 0 s2 + 0 s3

subject to x1 + s1 =4 2x2 + s2 =12 3x1 + 2x2 + s3 = 18 and x1 0, x2 0, s1 0, s2 0, s3 0 Simplex as an algebraic procedure System of functional constraints n (5) variables (5) and m (3) equations 2 degrees of freedom, (i.e., we can set those two variables to any arbitrary values); they are the nonbasic variables; the other variables are the basic variables; Simplex chooses to set the non-basic variables to ZERO. Simplex solves the simultaneous equations to set the values of the basic variables; Properties of Basic Solutions A basic solution is composed of: Non-basic variables

number of non-basic variables equals (total number of variables - number of functional constraints) They are set to ZERO Basic variables number of basic variables equals number of functional constraints Their values results from solving the system of functional constraints (non-basic variables set to 0) They form the Basic Feasible solution it is a basic solution that satisfies the non-negativity constraints Adjacent basic feasible solutions all but one of their basic (non-basic) variables are the same moving from one basic feasible solution to an adjacent one involves switching one variable from non-basic to basic and one variable from basic to non-basic (check graph) Wyndor Glass Production rate Let D = the number of doors to produce W = the number of windows to produce W

for windows Maximize P = 3 D + 5 W 8 (2,4,2,0,0) P = 3600 = 300D + 500W Z=30 Optimal solution 1 (2, 6) P = 3000 = 300D + 500W 6 2 Z=36 (0,6,4,0,6) P = 1500 = 300D + 500W Edge of Feasible region

(4,3,0,3,0) Feasible 4 region Z=27 Maximize P = 3 D + 5 W 2 subject to Z=0 CPF 0 0 2 6 (4,0,0,12,6) (0,0,4,12,18) (x1,x2,s1,s2,s3)

4 Production rate for doors 8 D4 2W 1012D 3D + 2W 18 and D 0, W 0. Getting ready for the Simplex Standard form <= constraints Non-negativity constraints on all variables Positive right hand sides (if these assumptions are not valid additional adjustments need to be done) Transform the objective function and constraints into equalities (introduction of slack variables) Simplex Procedure Initialization origin whenever possible (decision variables 0) (okay if standard form with positive RHSs; basic feasible solution (BFS): each equation has a basic variable with coefficient 1 (slack variable = RHS) and the variable does not appear in any other eq; the

decision variables are the non-basic variables set to 0) Optimality test is current BFS optimal? (the coefficients of the objective function of the non-basic variables gives the rate of improvement in Z ) Simplex Procedure (cont.) Iteration move to a better adjacent BFS a)Variable entering the basis Consider non-basic variables (Graphically - Consider edges emanating from current CPF solution) Pick the variable that increases Z at a faster rate b)Variable leaving the basis One of the basic variables will become non-basic; write all the basic variables as a function of the entering variable; the most stringent value (i.e., smallest) will be the value for the new entering variable; the basic variable associate with the most stringent constraint will become non-basic, leaving the basis. (Graphically where to stop? As much as possible without leaving the feasible region) c)Solving for the new BFS Objective of this step: convert the system of equations into a more convenient form: (1) to perform optimality test an

(2) to perform next iteration if necessary New basic variable should have coefficient 1 in the equation of the leaving variable and 0 in all the other equations, including the objective function; Valid operations: Multiplication (or division) of an equation by a non-zero constant Addition (or subtraction) of a multiple of an equation to (from) another eqution Wyndor Glass Production rate Let D = the number of doors to produce W = the number of windows to produce W for windows Maximize P = 3 D + 5 W 8

(2,4,2,0,0) P = 3600 = 300D + 500W Z=30 Optimal solution 1 (2, 6) P = 3000 = 300D + 500W 6 2 Z=36 (0,6,4,0,6) P = 1500 = 300D + 500W Edge of Feasible region (4,3,0,3,0) Feasible 4

region Z=27 Maximize P = 3 D + 5 W 2 subject to Z=0 CPF 0 0 2 6 (4,0,0,12,6) (0,0,4,12,18) (x1,x2,s1,s2,s3) 4 Production rate for doors

8 D4 2W 1012D 3D + 2W 18 and D 0, W 0. Wyndor Glass 1st Simplex Tableau Coefficients of Variables Bas Var Z x3 x4 x5 equation Z 0 1 2 3 x1 1 0 0

0 basic variables non-basic variables Optimal? Entering Variable? x2 -3 1 0 3 x3 -5 0 2 2 x3=4 x4=12 x5=18 x1=0 x2=0 x4 0 1 0 0 x5

0 0 1 0 RHS 0 0 0 1 0 4 12 18 Coefficients of Variables ratio Bas Var Z x3 x4 x5 equation Z 0 1 2

3 x1 1 0 0 0 basic variables non-basic variables pivot column/row pivot number x2 -3 1 0 3 x3 -5 0 2 2 x4 0 1 0 0

x5 0 0 1 0 RHS 0 0 0 1 0 4 12 12/2=6 18 18/2=9 x3=4 x4=12 x5=18 x1=0 x2=0 What variable will enter the basis? Why? What variable will leave the basis? Why? What transformations do we need to perform to the tableau to get the new basic variable into the right format? Coefficients of Variables Bas Var Z x3

x4 x5 Z x3 x2 x5 equation Z x1 x2 x3 x4 x5 RHS 0 1 2 3 1

0 0 0 -3 1 0 3 -5 0 2 2 0 1 0 0 0 0 1 0 0 0 0 1 0

4 12 18 0 1 2 3 1 0 0 0 -3 1 0 3 0 0 1 0 0 1 0 0 2 1/2

0 1/2 -1 0 0 0 1 30 4 6 6 What operations did we perform? 1 divide the pivot row by 2; 2 multiplied the new pivot row by (-2) and added it to eq. 3 3 multiplied the new pivot row by (5) and added it to eq. 0 What are the new basic / non-basic variables? Coefficients of Variables ratio Bas Var Z x3 x4 x5 Z x3

x2 x5 equation Z x1 x2 x3 x4 x5 RHS 0 1 2 3 1 0 0 0 -3

1 0 3 -5 0 2 2 0 1 0 0 0 0 1 0 0 0 0 1 0 4 12 12/2=6 18 18/2=9 0

1 2 3 1 0 0 0 -3 1 0 3 0 0 1 0 0 1 0 0 2 1/2 0 1/2 -1 0

0 0 1 30 4 4/1=4 6 6 6/3=2 basic variables non-basic variables x3=4 x2=6 x5=18 x1=0 x4=0 Optimal? Entering Variable? Coefficients of Variables ratio Bas Var Z x3 x4 x5 equation Z

x1 x2 x3 x4 x5 RHS 0 1 2 3 1 0 0 0 -3 1 0 3 -5 0 2

2 0 1 0 0 0 0 1 0 0 0 0 1 0 4 12 12/2=6 18 18/2=9 Z x3 x2 x5 0 1 2

3 1 0 0 0 -3 1 0 3 0 0 1 0 0 1 0 0 2 1/2 0 1/2 -1 0 0 0

1 30 4 4/1=4 6 6 6/3=2 Z x3 x2 x1 0 1 2 3 1 0 0 0 0 0 0 1 0 0 1

0 0 1 0 0 1 1/2 1/3 1/2 - 1/3 1 - 1/3 0 1/3 basic variables non-basic variables pivot column/row pivot number 36 2 6 2 x3=4 x2=6 x5=18 x1=0 x4=0

What operations did we perform? 1 divide the pivot row by ; 2 multiplied the new pivot row by ( ) and added it to eq. 1 3 multiplied the new pivot row by ( ) and added it to eq. 0 What are the new basic / non-basic variables? Coefficients of Variables ratio Bas Var Z x3 x4 x5 equation Z x1 x2 x3 x4 x5 RHS

0 1 2 3 1 0 0 0 -3 1 0 3 -5 0 2 2 0 1 0 0 0 0 1 0

0 0 0 1 0 4 12 12/2=6 18 18/2=9 Z x3 x2 x5 0 1 2 3 1 0 0 0 -3 1 0 3

0 0 1 0 0 1 0 0 2 1/2 0 1/2 -1 0 0 0 1 30 4 4/1=4 6 6 6/3=2 Z x3 x2 x1

0 1 2 3 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 1/2 1/3 1/2 - 1/3

1 - 1/3 0 1/3 basic variables non-basic variables Optimal? x1=2 x2=6 x3=2 x4=0 x5=0 36 2 6 2 Simplex Method in Tabular Form Coefficients of Variables ratio Bas Var Z x3 x4 x5 equation

Z x1 x2 x3 x4 x5 RHS 0 1 2 3 1 0 0 0 -3 1 0 3 -5

0 2 2 0 1 0 0 0 0 1 0 0 0 0 1 0 4 12 12/2=6 18 18/2=9 Z x3 x2 x5 0

1 2 3 1 0 0 0 -3 1 0 3 0 0 1 0 0 1 0 0 2 1/2 0 1/2 -1 0

0 0 1 30 4 4/1=4 6 6 6/3=2 new-pivot-row*5+eq0 same pivot-row(eq 2)/2 new-pivot-row*(-2)+eq3 Z x3 x2 x1 0 1 2 3 1 0 0 0 0

0 0 1 0 0 1 0 0 1 0 0 1 1/2 1/3 1/2 - 1/3 1 - 1/3 0 1/3 36 2 6 2 new-pivot-row*3+eq0

new-pivot-row*(-1)+eq1 same pivot-row(eq3)/3 Modeling Languages Modeling Languages A mathematical language that has been designed to efficiently formulate large mathematical models (with thousand of variables/constraints). Examples of modeling languages: AMPL; MPL; GAMS; LINGO. Textbook (CD-ROM): MPL (student version; also from www.maximalsoftware.com) It provides an interface to to Excel (importing and exporting Excel ranges) Powerful state-of-the-art LP based solver CPLEX LINDO (also available from www.lindo.com) LINDO (Traditional optimizer) Whats Best spreadsheet optimizer LINGO (Linear and Non-liner programming) Formulations in MPL, LINGO, LINDO and Whats best for all the examples in the book. MPL: Just ignore the message MPL/CPLEX Activating the license Acknowledgment from Cplex

MODEL MAX Z = 3 X1 + 5 X2; SUBJECT TO X1 <= 4; 2 X2 <= 12; 3 X1 + 2 X2 <= 18; END Note: default assumption non-negativity constraints (can be changed) MPL: Solution Options Checking Syntax and Runnig Syntax Solving it with Cplex Optimal Solution Solution File MPL Modeling System -

Copyright (c) 1988-2000, Maximal Software, Inc. -------------------------------------------------------------------------------MODEL STATISTICS Problem name: WyndorGlass Filename: Date: Time: Parsing time: my-wyndor.mpl February 24, 2005 11:57 0.05 sec Solver: Objective value: Iterations: Solution time: CPLEX 36.0000000000 0 0.00 sec Constraints: Variables: Nonzeros:

Density: 3 2 4 67 % SOLUTION RESULT Optimal solution found MAX Z = 36.0000 Solution File (cont.) DECISION VARIABLES PLAIN VARIABLES Variable Name Activity Reduced Cost -----------------------------------------------------X1 2.0000 0.0000 X2 6.0000 0.0000 -----------------------------------------------------CONSTRAINTS

PLAIN CONSTRAINTS Constraint Name Slack Shadow Price -----------------------------------------------------c1 2.0000 0.0000 c2 0.0000 1.5000 c3 0.0000 1.0000 -----------------------------------------------------RANGES OBJECTIVE PLAIN VARIABLES Variable Name Coefficient Lower Range Upper Range ----------------------------------------------------------------------X1 3.0000 0.0000 7.5000 X2 5.0000 2.0000 1E+020 ----------------------------------------------------------------------RANGES RHS PLAIN CONSTRAINTS Constraint Name

RHS Value Lower Bound Upper Bound ----------------------------------------------------------------------c1 4.0000 2.0000 1E+020 c2 12.0000 6.0000 18.0000 c3 18.0000 12.0000 24.0000 ----------------------------------------------------------------------END MPL: A more compact version (good for large-scale problems) TITLE WyndorGlass; INDEX product := (Door, Window); plant := 1..3; DATA TimeAvail[plant] := (4, 12, 18);

ProdTime[plant, product] := (1, 0, 0, 2, 3, 2); Profit[product] := (3.00, 5.00); VARIABLES Produce[product] -> Prod; MODEL MAX TotalProfit = SUM(product: Profit * Produce); SUBJECT TO TimeCapacity[plant] -> TimeCap: SUM(product: ProdTime * Produce) <= TimeAvail; END Excel Developing a Spreadsheet Model Step #1: Data Cells (parameters) Enter all of the data (parameters) for the problem on the spreadsheet. Make consistent use of rows and columns. It is a good idea to color code these data/parameter cells (e.g., light blue).

Step #2: Changing Cells Add a cell in the spreadsheet for every decision variable. If you dont have any particular initial values, just enter 0 in each. It is a good idea to color code these changing cells (e.g., yellow with border). B 3 4 5 6 7 8 9 10 11 12 Unit Profit Plant 1 Plant 2 Plant 3 Units Produced C

D Doors \$300 Windows \$500 Hours Used Per Unit Produced 1 0 0 2 3 2 Doors 0 Windows 0 E F G Hours Available 1

12 18 Developing a Spreadsheet Model Step #3: Target Cell Develop an equation that defines the objective of the model. Typically this equation involves the data cells and the changing cells in order to determine a quantity of interest (e.g., total profit or total cost). It is a good idea to color code this cell (e.g., orange with heavy border). B 3 4 5 6 7 8 9 10 11 12 Unit Profit Plant 1

Plant 2 Plant 3 Units Produced C D Doors \$300 Windows \$500 Hours Used Per Unit Produced 1 0 0 2 3 2 Doors 1 Windows 1 E

F G Hours Available 1 12 18 Total Profit \$800 G 11 Total Profit 12 =SUMPRODUCT(UnitProfit,UnitsProduced) Developing a Spreadsheet Model Step #4: Constraints For any resource that is restricted, calculate the amount of that resource used in a cell on the spreadsheet (an output cell). Define the constraint in three consecutive cells. For example, if Quantity A Quantity B, put these three items (Quantity A, , Quantity B) in consecutive cells. B 3 4 5

6 7 8 9 10 11 12 Unit Profit Plant 1 Plant 2 Plant 3 Units Produced C D Doors \$300 Windows \$500 E Hours Used 1

2 5 Hours Used Per Unit Produced 1 0 0 2 3 2 Doors 1 Windows 1 F G <= <= <= Hours Available 1 12 18 Total Profit

\$800 E 5 6 7 8 9 Hours Used =SUMPRODUCT(C7:D7,UnitsProduced) =SUMPRODUCT(C8:D8,UnitsProduced) =SUMPRODUCT(C9:D9,UnitsProduced) A Trial Solution B 3 4 5 6 7 8 9 10 11 12 Unit Profit Plant 1

Plant 2 Plant 3 Units Produced C D Doors \$300 Windows \$500 Hours Used Per Unit Produced 1 0 0 2 3 2 Doors 4 Windows 3 E

Hours Used 4 6 18 F G <= <= <= Hours Available 1 12 18 Total Profit \$2,700 The spreadsheet for the Wyndor problem with a trial solution (4 doors and 3 windows) entered into the changing cells. Identifying the Target Cell and Changing Cells Choose the Solver from the Tools menu. Select the cell you wish to optimize in the Set Target Cell window. Choose Max or Min depending on whether you want to maximize or minimize the target cell.

Enter all the changing cells in the By Changing Cells window. B 3 4 5 6 7 8 9 10 11 12 Unit Profit Plant 1 Plant 2 Plant 3 Units Produced C D Doors \$300 Windows \$500

Hours Used Per Unit Produced 1 0 0 2 3 2 Doors 1 Windows 1 E Hours Used 1 2 5 F G <= <= <=

Hours Available 1 12 18 Total Profit \$800 Adding Constraints To begin entering constraints, click the Add button to the right of the constraints window. Fill in the entries in the resulting Add Constraint dialogue box. B 3 4 5 6 7 8 9 10 11 12 Unit Profit Plant 1 Plant 2 Plant 3

Units Produced C D Doors \$300 Windows \$500 Hours Used Per Unit Produced 1 0 0 2 3 2 Doors 1 Windows 1 E Hours Used 1

2 5 F G <= <= <= Hours Available 1 12 18 Total Profit \$800 The Complete Solver Dialogue Box Some Important Options Click on the Options button, and click in both the Assume Linear Model and the Assume Non-Negative box. Assume Linear Model tells the Solver that this is a linear programming model. Assume Non-Negative adds nonnegativity constraints to all the changing cells. The Solver Results Dialogue Box

The Optimal Solution B 3 4 5 6 7 8 9 10 11 12 Unit Profit Plant 1 Plant 2 Plant 3 Units Produced C D Doors \$300 Windows \$500

Hours Used Per Unit Produced 1 0 0 2 3 2 Doors 2 Windows 6 E Hours Used 2 12 18 F G <= <= <=

Hours Available 1 12 18 Total Profit \$3,600 Requesting the Sensitivity Analysis Report Sensitivity Analysis Report Duality Duality Every maximization LP problem in the standard form gives rise to a minimization LP problem called the dual problem Every feasible solution in one yields a bound on the optimal value of the other If one of the problems has an optimal solution, so does the other and the two optimal values coincide These results have very interesting economic interpretations Bounds on the optimal value Let x1 = the number of doors to produce x2= the number of windows to produce Maximize Z= 3 x1 + 5 x2 subject to

x1 4 2x2 12 3x1 + 2x2 18 and x1 0, x2 0. Lower bound (LB) on Z* Z* LB any feasible solution Upper bound (UB) on Z* Z* UB how do we come up with upper bounds for Z* for a maximization LP problem? Let x1 = the number of doors to produce x2= the number of windows to produce Guessing upper bounds Maximize Z= 3 x1 + 5 x2 subject to x1 4 2x2 12 3x1 + 2x2 18 and x1 0, x2 0. 1 multiplying the 3rd costraint by 3 9x1 + 6x2 54 Z= 3 x1 + 5 x2 9x1 + 6x2 54 Z* 54 2 multiplying the 3rd constraint by 2.5 7.5 x1 + 5 x2 45 Z= 3 x1 + 5 x2 7.5 x1 + 6x2 45

Z* 45 3 multiplying the 2nd constraint by 2 and add it to the 3rd 3x1 + 6x2 42 Z= 3 x1 + 5 x2 3x1 + 6x2 54 Z* 42 4 multiplying the 2nd constraint by 1.5 and add it to the 3rd 3x1 + 5x2 36 Z= 3 x1 + 5 x2 3x1 + 5x2 54 Z* 36 A principled way of finding upper-bounds on Z* Dual Problem Let x1 = the number of doors to produce x2= the number of windows to produce Maximize Z= 3 x1 + 5 x2 subject to x1 4 y1 2x2 12 y2 3x1 + 2x2 18 y3 and

x1 0, x2 0. We construct linear combinations of constraints Minimize W= 4 y1 + 12 y2 + 12 y3 subject to y1 + 3 y3 3 2 y2 + 2 y3 5 and y 0, y 0, y 0 We want to minimize the biund The sum of the coefficients at least equal the corresponding one for objective function Each multiplier must be non-negative Primal vs. Dual Problem Maximize Z= 3 x1 + 5 x2 Minimize W= 4 y1 + 12 y2 + 12 y3 subject to x1

4 2x2 12 3x1 + 2x2 18 subject to y1 + and x1 0, x2 0. 3 y3 3 2 y 2 + 2 y3 5 and y1 0, y2 0, y3 0 Primal vs. Dual Max Z = c1 x1 + c2x2 + . + cnxn Min W = b1 y1 + b2y2 + . + bmym Subject to: Subject to: a11 x1 + a12 x2 + + a1n xn b1 a11 y1 + a21 y2 + + am1 ym c1

a21 x1 + a22 x2 + + a2n xn b2 a12 y1 + a22 y2 + + am2 ym c2 am1 x1 + am2 x2 + + amn xn bm x1, x2, , xn 0 a1n y1 + a2n y2 + + amn yn cn y1, y2, , ym 0 Dual Primal n Max c x j j j 1 m Min b y i i i 1 s.t

n aij x j bi (i 1, 2,, m) j1 x 0 ( j 1, 2,, n) j m aij yi c j ( j 1, 2,, n) i1 y 0 ( i 1, 2,, m) i Every feasible dual solution yields an upper-bound on Z* of the primal and every feasible primal solution yields a lower-bound on Z* of the dual Weak duality property Dual feasible solutions (Minimization) Upper Bounds on Primal Optimum Primal feasible solutions (Maximization) Lower Bounds on Dual Optimum Z*

Weak duality property n m c j x j bi yi j 1 i 1 Weak duality property Every feasible dual solution yields an upper-bound on Z* of the primal and every feasible primal solution yields a lower-bound on Z* of the dual Strong Duality Property n m * * c x b y j j i i j 1 i 1 Every feasible dual solution yields an upper-bound on Z* of the primal and every feasible

primal solution yields a lower-bound on Z* of the dual Weak duality property Dual feasible solutions (Minimization) Z* Upper Bounds on Primal Optimum Primal Opt. = Dual Opt. Primal feasible solutions (Maximization) Lower Bounds on Dual Optimum Strong duality property Complementary Slackness Optimal solutions Let x1*, x2*, xn* be a primal feasible solution and a y1*, y2*, ym* dual feasible solution. Necessary and sufficient conditions for simultaneous optimality of x 1*, x2*, xn* and y1*, y2*, ym* are: n * b or y* 0 (or both) (i 1, 2,, m) a

x ij j i i j 1 m * c or x* 0 (or both) ( j 1, 2,, n) b y i i j j i 1 This result is very useful for checking the optimality of solutions Relationships between the primal and dual problems If one problem has feasible solutions and a bounded objective function (and therefore an optimal solution), then so does the other problem (both weak and strong duality apply) If one problem has feasible solutions and an unbounded objective function (therefore no optimal solution) then the other problem has no feasible solutions If one problem has no feasible solutions than the other problem has no feasible solutions or an unbounded objective function. Complementary Slackness Optimal solutions Primal-Dual Combinations Adapting to Other Forms

What if our problem is not in standard form? We can always transform it to the standard form and then construct the dual; Dual of the dual Note: it is not important which problem we call dual and which problem we call primal given the symmetry property of the primal dual relationships. In general we call primal the model formulated to fit the actual problem. Complexity of Simplex Method Primal vs. Dual How long does it take to solve an LP using the simplex method? Several factors but the most important one seems to be the number of functional constraints. Computation tends to be proportional to the cube of the number of functional constraints in an LP. The number of variables is a relatively minor factor (assuming revised simplex method) The density of the matrix of technological coefficients is also a factor the sparser the matrix (i.e., the larger the number of zeroes) the faster the simplex method; Real world problems tend to be sparse, i.e., sparcity of 5% or even 1%, which leads to fast runs. Primal vs. Dual?

So, the size of the problem, may determine whether to use the simplex method on the primal or dual problem. If the primal has a large number of constraints and a small number of variables it is better to apply the simplex method to the dual (since it will have a small number of constraints). Dual Simplex Method This method is based on the duality results. It is a mirror image of the simplex method: the simplex method deals with primal feasible solutions (but not dual feasible), moving toward a solution that is dual feasible; the dual method deals with basic solutions in the primal problem that are dual feasible but not primal feasible. It moves toward an optimal solution by striving to achieve primal feasibility as well. Post-optimality Analysis and Economic Interpretation of Duality Post-optimality Analysis Post-optimality very important phase of modeling. Duality plays and important role in post-optimality analysis Simplex provides several tools to perform post-optimality analysis Economic Interpretation of Duality

LP problems quite often can be interpreted as allocating resources to activities. Lets consider the standard form: xi >= 0 , (i =1,2,,n) Resources m (plants) Activities n (2 products) Wyndor Glass problem optimal product mix --- allocation of resources to activities i.e., choose the levels of the activities that achieve best overall measure of performance What if we change our resources can we improve our optimal solution? Sensitivity Analysis How would changes in the problems objective function coefficients or right-hand side values change the optimal solution? Dual Variables (Shadow Prices) y1*= 0 dual variable (shadow price) for resource 1 y2*= 1.5 dual variable (shadow price) for resource 2 y3*= 1 dual variable (shadow price) for resource 3 How much does Z increase if we increase resource 2 by 1 unit (i.e., b2 = 12 b2=13)? Graphical Analysis of Dual variables Variation in RHS Increasing level of resource 2 (b2)

Production rate for windows W 10 3 D + 2 W = 18 8 (5/3,13/2) D=4 2w=13 Z=3(5/3)+5(13/2)=37.5 6 2 W =12 Z=3(2)+5(6)=36 (2,6) Z=1.5 = y2 * 4 Why is y1*=0? Feasible 2

0 region 2 4 Production rate for doors 6 8 D Economic Interpretation of Dual Variables The dual variable associated with resource i (also called shadow price), denoted by yi*, measures the marginal value of this resource, i.e., the rate at which Z could be increased by (slightly) increasing the amount of this resource (bi), assuming everything else stays the same. The dual variable yi* is identified by the simplex method as the coefficient of the ith slack variable in row 0 of the final simplex tableau. Dual Variables: binding and non-binding constraints The shadow prices (dual variables) associated with non-binding constraints are necessarily 0 (complementary optimal slackness) there is a surplus of nonbinding resource and therefore increasing it will not increase the optimal solution. Economist refer to such resources as free resources (shadow price

=0) Binding constraints on the other hand correspond to scarce resources there is no surplus. In general they have a positive shadow price. Does Z always increase at the same rate if we keep increasing the amount of resource 2? Production rate for windows W 10 (0,9) b2=18 3 D + 2 W = 18 8 (5/3,13/2) D=4 2w=13 Z=3(5/3)+5(13/2)=37.5 6 2 W =12 Z=3(2)+5(6)=36 (2,6)

Z=1.5 = y2 * 4 What if b2 > 18 (i.e., 2W>18)? Feasible 2 0 region 2 4 Production rate for doors 6 8 D the optimal solution will stay at (0,9) for b2>=18 Does Z always decrease at the same rate if we decrease resource 2?

Production rate for windows W 10 3 D + 2 W = 18 8 (5/3,13/2) D=4 2w=13 Z=3(5/3)+5(13/2)=37.5 6 2 W =12 (2,6) 4 Feasible 2 0 b2=6 region 2 4

Production rate for doors 6 Z=3(2)+5(6)=36 Z=1.5 = y2 * If b2 < 6 the solution will no longer vary proportionally. The optimal solution varies proportionally to the variation in b2 only if 6 <= b2 <=18. In other words, the current basis remains optimal for 6 b2 18, but the decision variable values and z-value will change. 8 D A dual variable yi* gives us the rate at which Z could be increased by increasing the amount of resource i slightly. However this is only true for a small increase in the amount of the resource. I.e., this definition applies only if the change in the RHS of constraint i leaves the current basis optimal. It also assumes everything else stays the same. Another interpretation of yi* is: if a premium price must be paid for the resource i in the market place, yi* is the maximum premium (excess over the regular price) that would be worth paying.

Optimal Basis in the Wyndor Glass Problem How can we characterize (verbally) the optimal basis of the Wyndor Glass problem? Plant 1 unutilized capacity (non-binding constraint) Plant 2 fully utilized capacity (binding constraint) Plant 3 - fully utilized capacity (binding constraint) How do we interpret the intervals? If we change one coefficient in the RHS, say capacity of plant 2, by the basis remains optimal, that is, the same equations remain binding. So long as the basis remains optimal, the shadow prices are unchanged. The basic feasible solution varies linearly with. If is big enough or small enough the basis will change. Sensitivity analysis for c1 How much can we vary c1 without changing the current basic optimal solution? Sensitivity analysis for c1 Production rate W for windows 8 P = 3600 = 300D + 500W

Our objective function is: Z= c1 D+5W=k slope of iso-profit line is: c1 D 5 Optimal solution (2, 6) P = 3000 = 300D + 500W 6 Feasible 4 P = 1500 = 300D + 500W region 2 isoprofit line 0 2

4 Production rate for doors 6 8 10 D How much can c1 vary until the slope of the iso-profit line equals the slope of constraint 2 and constraint 3? How much can c1 vary until the slope of the iso-profit line equals the slope of constraint 2 and constraint 3? Slope of constraint 2 0 Slope of constraint 3 -3/2 c1 D 0 c10 5 c1 D 3 c115 5 2 2 0 c17.5

Importance of Sensitivity Analysis Sensitivity analysis is important for several reasons: Values of LP parameters might change. If a parameter changes, sensitivity analysis shows it is unnecessary to solve the problem again. For example in the Wyndor problem, if the profit contribution of product 1 changes to 5, sensitivity analysis shows the current solution remains optimal. Uncertainty about LP parameters. In the Wyndor problem for example, if the capacity of plant 1 decreases to 2, the optimal solution remains a weekly rate of 2 doors and 6 windows. Thus, even if availability of capacity of plant 1 uncertain, the company can be fairly confident that it is still optimal to produce a weekly rate of 2 doors and 6 windows. It allows us to solve very large LPs column generation approaches Reduced Costs Glass Example x1 = # of cases of 6-oz juice glasses (in 100s) x2 = # of cases of 10-oz cocktail glasses (in 100s) x3 = # of cases of champagne glasses (in 100s) max 5 x1 + 4.5 x2 + 6 x3 (\$100s) s.t 6 x1 + 10 x1 + x1 5 x2 + 8 x3 60 (prod. cap. in hrs)

20 x2 + 10 x3 150 (wareh. cap. in ft2) 8 (6-0z. glass demand) x1 0, x2 0, x3 0 (from AMP and slides from James Orlin) Z* = 51.4286 Decision Variables x1 = 6.4286 (# of cases of 6-oz juice glasses (in 100s)) x2 = 4.2857 (# of cases of 10-oz cocktail glasses (in 100s)) x3 = 0 (# of cases of champagne glasses (in 100s)) Slack Variables s1 * = 0 s2 * = 0 s3* = 1.5714 Dual Variables y1* = 11/4 = 0.7857 y2* = 0.0286 y3* = 0 Complementary optimal slackness conditions Do the non-negativity constraints also have shadow prices?

Yes. They are very special and are called reduced costs? Look at the reduced costs for Juice glasses reduced cost = 0 Cocktail glasses reduced cost = 0 Champagne glasses red. cost = -4/7 What is the managerial interpretation of a reduced cost? There are two interpretations. Here is one of them. We are currently not producing champagne glasses. How much would the profit of champagne glasses need to go up for us to produce champagne glasses in an optimal solution? The reduced cost for champagne classes is 4/7. If we increase the revenue for these glasses by 4/7 (from 6 to 6 4/7), then there will be an alternative optimum in which champagne glasses are produced. Why are they called the reduced costs? Nothing appears to be reduced The reduced costs can be obtained by treating the shadow prices are real costs. This operation is called pricing out. Pricing Out max 5 x1 + 4.5 x2 + 6 x3 (\$100s) s.t 6 x1 +

5 x2 + 8 x3 60 10 x1 + 20 x2 + 10 x3 150 1 x1 8 x1 0, x2 0, x3 0 Pricing out treats shadow prices as though they are real prices. The result is the reduced costs. shadow price 11/14 1/35 .0 Pricing Out of x1 shadow price max 5 x1 + 4.5 x2 + 6 x3 (\$100s) s.t 6 x1 +

5 x2 + 8 x3 60 10 x1 + 20 x2 + 10 x3 150 1 x1 8 11/14 1/35 .0 x1 0, x2 0, x3 0 Reduced cost of x1 = 5 - 6 x 11/14 - 10 x 1/35 - 1 x0 = 5 33/7 2/7 = 0 Pricing Out of x2 shadow price max 5 x1 + 4.5 x2 + 6 x3 (\$100s) s.t

6 x1 + 5 x2 + 8 x3 60 10 x1 + 20 x2 + 10 x3 150 1 x1 8 11/14 1/35 .0 x1 0, x2 0, x3 0 Reduced cost of x2 = 4.5 - 5 x 11/14 - 20 x 1/35 - 0 x0 = 4.5 55/14 4/7 = 0 Pricing Out of x3

shadow price max 5 x1 + 4.5 x2 + 6 x3 (\$100s) s.t 6 x1 + 5 x2 + 8 x3 60 10 x1 + 20 x2 + 10 x3 150 1 x1 8 11/14 1/35 .0 x1 0, x2 0, x3 0 Reduced cost of x3 = 6 - 8 x 11/14 - 10 x 1/35 - 0 x0

= 6 44/7 2/7 = -4/7 Can we use pricing out to figure out whether a new type of glass should be produced? shadow price max 5 x1 + 4.5 x2 + 7 x4 (\$100s) s.t 6 x1 + 5 x2 + 8 x4 60 10 x1 + 20 x2 + 20 x4 150 1 x1 8 11/14 1/35 .0 x1 0, x2 0, x4 0 Reduced cost of x4 =

7 - 8 x 11/14 - 20 x 1/35 - 0 x0 = 7 44/7 4/7 = 1/7 Pricing Out of xj shadow price max 5 x1 + 4.5 x2 + cj xj (\$100s) s.t 6 x1 + 5 x2 + a1j xj 60 10 x1 + 20 x2 + a2j xj 150 .. . + amjxj = bm x1 0, x2 0, x3 0 Reduced cost of xj = ? y1 y2

ym Brief summary on reduced costs The reduced cost of a non-basic variable xj is the increase in the objective value of requiring that xj >= 1. The reduced cost of a basic variable is 0. The reduced cost can be computed by treating shadow prices as real prices. This operation is known as pricing out. Pricing out can determine if a new variable would be of value (and would enter the basis). Summary The shadow price is the unit change in the optimal objective value per unit change in the RHS. The shadow price for a 0 constraint is called the reduced cost. Shadow prices usually but not always have economic interpretations that are managerially useful. Non-binding constraints have a shadow price of 0. The sign of a shadow price can often be determined by using the economic interpretation Shadow prices are valid in an interval. Reduced costs can be determined by pricing out Implications of Reduced Costs We can compute the reduced cost of any variable if we know the original column and if we know the prices for each constraint.

FACT: We can compute the reduced cost of a new variable. If the reduced cost is positive, it should be entered into the basis. Sensitivity Analysis Computer Analysis The Computer and Sensitivity Analysis If an LP has more than two decision variables, the range of values for a rhs (or objective function coefficient) for which the basis remains optimal cannot be determined graphically. These ranges can be computed by hand but this is often tedious, so they are usually determined by a packaged computer program. MPL and LINDO will be used and the interpretation of its sensitivity analysis discussed. Note: sometimes Excel provides erroneous results MPL Sensitivity analysis info Dual or Shadow prices are the amount the optimal z-value improves if the rhs of a

constraint is increased by one unit (assuming no change in basis). Dual variables c1 cost Reduced is the amount the objective function coefficient for variable i would have to be increased for there to be an b2 alternative optimal solution. More later MPL Sensitivity analysis info c1 Allowable ranges (w/ o changing basis) for the x1 coefficient (c1) is:

0 c1 7.5 b2 What about c2? And b1 and b3? Allowable range (w/o changing basis) for the rhs (b2) of the second constraint is: 6 b2 18 Lindo Sensitivity Analysis Allowable ranges in terms of increase and decrease (w/o changing basis) for the x1 coefficient (c1) is: 0 c1 7.5 The Computer and Sensitivity Analysis Consider the following maximization problem. Winco sells four types of products. The resources needed to produce one unit of each are: Product 1 Product 2 Product 3

Product 4 Available Raw material 2 3 4 7 4600 Hours of labor 3 4 5 6 5000 Sales price

\$4 \$6 \$7 \$8 To meet customer demand, exactly 950 total units must be produced. Customers demand that at least 400 units of product 4 be produced. Formulate an LP to maximize profit. Let xi = number of units of product i produced by Winco. The Winco LP formulation: max z = 4x1 + 6x2 +7x3 + 8x4 s.t. x1 + x2 + x3 + x4 = 950 x4 400 2x1 + 3x2 + 4x3 + 7x4 4600 3x1 + 4x2 + 5x3 + 6x4 5000 x1,x2,x3,x4 0 LINDO output and sensitivity analysis

example(s). Reduced cost is the amount the objective function coefficient for variable i would have to be increased for there to be an alternative optimal solution. MAX 4 X1 + 6 X2 + 7 X3 + 8 X4 SUBJECT TO 2) X1 + X2 + X3 + X4 = 950 3) X4 >= 400 4) 2 X1 + 3 X2 + 4 X3 + 7 X4 <= 4600 5) 3 X1 + 4 X2 + 5 X3 + 6 X4 <= 5000 END LP OPTIMUM FOUND AT STEP 4 OBJECTIVE FUNCTION VALUE 1) 6650.000 VARIABLE X1

X2 X3 X4 ROW 2) 3) 4) 5) NO. ITERATIONS= 4 VALUE 0.000000 400.000000 150.000000 400.000000 REDUCED COST 1.000000 0.000000 0.000000 0.000000 SLACK OR SURPLUS 0.000000 0.000000 0.000000 250.000000

DUAL PRICES 3.000000 -2.000000 1.000000 0.000000 RANGES IN WHICH THE BASIS IS UNCHANGED: LINDO sensitivity analysis example(s). OBJ COEFFICIENT RANGES VARIABLE Allowable range (w/o changing basis) for the x2 coefficient (c2) is: CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE

X1 4.000000 1.000000 INFINITY X2 6.000000 0.666667 0.500000 X3 7.000000 1.000000 0.500000 X4 8.000000 2.000000

INFINITY 5.50 c2 6.667 RIGHTHAND SIDE RANGES Allowable range (w/o changing basis) for the rhs (b1) of the first constraint is: 850 b1 1000 ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 950.000000

50.000000 100.000000 3 400.000000 37.500000 125.000000 4 4600.000000 250.000000 150.000000 5 5000.000000 INFINITY 250.000000 Shadow prices are shown in the

Dual Prices section of LINDO output. Shadow prices are the amount the optimal zvalue improves if the rhs of a constraint is increased by one unit (assuming no change in basis). MAX 4 X1 + 6 X2 + 7 X3 + 8 X4 SUBJECT TO 2) X1 + X2 + X3 + X4 = 950 3) X4 >= 400 4) 2 X1 + 3 X2 + 4 X3 + 7 X4 <= 4600 5) 3 X1 + 4 X2 + 5 X3 + 6 X4 <= 5000 END LP OPTIMUM FOUND AT STEP 4 OBJECTIVE FUNCTION VALUE 1) 6650.000 VARIABLE X1

X2 X3 X4 ROW 2) 3) 4) 5) NO. ITERATIONS= 4 VALUE 0.000000 400.000000 150.000000 400.000000 REDUCED COST 1.000000 0.000000 0.000000 0.000000 SLACK OR SURPLUS 0.000000 0.000000 0.000000 250.000000

DUAL PRICES 3.000000 -2.000000 1.000000 0.000000 Shadow price signs (MAXIMIZATION) 1. Constraints with symbols will always have nonpositive shadow prices. 2. Constraints with will always have nonnegative shadow prices. 3. Equality constraints may have a positive, a negative, or a zero shadow price. Interpretation of shadow prices for the Winco LP ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.000000 (overall demand)

3) 0.000000 -2.000000 (product 4 demand) 4) 0.000000 1.000000 (raw material availability) 5) 250.000000 0.000000 (labor availability) Assuming the allowable range of the rhs is not violated, shadow (Dual) prices show: \$3 for constraint 1 implies that each one-unit increase in total demand will increase net sales by \$3. The -\$2 for constraint 2 implies that each unit increase in the requirement for product 4 will decrease revenue by \$2. The \$1 shadow price for constraint 3 implies an additional unit of raw material (at no cost) increases total revenue by \$1. Finally, constraint 4 implies any additional

labor (at no cost) will not improve total revenue. Shadow price signs 1. Constraints with symbols will always have nonpositive shadow prices. 2. Constraints with will always have nonnegative shadow prices. 3. Equality constraints may have a positive, a negative, or a zero shadow price. Managerial Use of Shadow Prices The managerial significance of shadow prices is that they can often be used to determine the maximum amount a manager should be willing to pay for an additional unit of a resource. Reconsider the Winco to the right. What is the most Winco should be willing to pay for additional units of raw material or labor? MAX 4 X1 + 6 X2 + 7 X3 + 8 X4

SUBJECT TO 2) X1 + X2 + X3 + X4 = 950 3) X4 >= 400 4) 2 X1 + 3 X2 + 4 X3 + 7 X4 <= 4600 5) 3 X1 + 4 X2 + 5 X3 + 6 X4 <= 5000 END raw material labor LP OPTIMUM FOUND AT STEP 4 OBJECTIVE FUNCTION VALUE 1) 6650.000 VARIABLE COST X1 X2 X3 X4 VALUE ROW 2) 3)

4) 5) NO. ITERATIONS= 4 REDUCED 0.000000 400.000000 150.000000 400.000000 1.000000 0.000000 0.000000 0.000000 SLACK OR SURPLUS 0.000000 0.000000 0.000000 250.000000 DUAL PRICES 3.000000 -2.000000 1.000000 0.000000

Managerial Use of Shadow Prices The shadow price for raw material constraint (row 4) shows an extra unit of raw material would increase revenue \$1. Winco could pay up to \$1 for an extra unit of raw material and be as well off as it is now. Labor constraints (row 5) shadow price is 0 meaning that an extra hour of labor will not increase revenue. So, Winco should not be willing to pay anything for an extra hour of labor. MAX 4 X1 + 6 X2 + 7 X3 + 8 X4 SUBJECT TO 2) X1 + X2 + X3 + X4 = 950 3) X4 >= 400 4) 2 X1 + 3 X2 + 4 X3 + 7 X4 <= 4600 5) 3 X1 + 4 X2 + 5 X3 + 6 X4 <= 5000 END LP OPTIMUM FOUND AT STEP 4 OBJECTIVE FUNCTION VALUE

1) 6650.000 VARIABLE COST X1 X2 X3 X4 VALUE ROW 2) 3) 4) 5) NO. ITERATIONS= 4 REDUCED 0.000000 400.000000 150.000000 400.000000 1.000000 0.000000 0.000000

0.000000 SLACK OR SURPLUS 0.000000 0.000000 0.000000 250.000000 DUAL PRICES 3.000000 -2.000000 1.000000 0.000000