Report

Readings Readings Chapter 7 Integer Linear Programming BA 452 Lesson B.3 Integer Programming 1 Overview Overview BA 452 Lesson B.3 Integer Programming 2 Overview Rounding Off solutions in continuous variables to the nearest integer (like 2.67 rounded off to 3) is an unreliable way to solve a linear programming problem when decision variables should be integers. Sensitivity Analysis with Integer Variables is more important than with continuous variables because a small change in a constraint coefficient can cause a relatively large change in the optimal solution. Assignment Problems with Valuable Time minimize the total time of assigning workers to jobs. Minimizing total time is appropriate when each worker has the same value of time. Assignment Problems with Supply and Demand are Transportation Problems of suppliers to demanders except that each demand is assigned to exactly one supplier. BA 452 Lesson B.3 Integer Programming 3 Overview Tool Summary Do not make integer restrictions, and maybe the variables at an optimum will be integers. • First Example: Pi = (integer) number of producers in month i. Use compound variables: • First Example: Pi = number of producers in month i Use dynamic or recursive constraints: • First Example: Define the constraint that the number of apprentices in a month must not exceed the number of recruits in the previous month: A2 - R1 < 0; A3 - R2 < 0 Constrain one variable to be a proportional to another variable: • First Example: Define the constraint that each trainer can train two recruits: 2T1 - R1 > 0; 2T2 - R2 > 0 Use inventory variables: • Second Example: P2 + I1–I2 = 150 (production-net inventory = demand) BA 452 Lesson B.3 Integer Programming 4 Tool Summary Tool Summary Use binary variables to model fixed cost constraints. • For example, consider a linear programming problem with a constraint • M1 < 15 • Introduce binary variable U1 and constraints: • M1 > 5 U1 • 15U1 > M1 • Then, U1 = 1 if M1 > 0, and either M1 = 0 or M1 > 5. Do not try to solve an integer linear program by rounding off (up or down) a solution to the problem without integer constraints. Rather, graph all feasible integer solutions and use iso-value linear, or use the Management Scientist module. BA 452 Lesson B.3 Integer Programming 5 Rounding Off Rounding Off BA 452 Lesson B.3 Integer Programming 6 Rounding Off Overview Rounding Off solutions in continuous variables to the nearest integer (like 2.67 rounded off to 3) is an unreliable way to solve a linear programming problem when decision variables should be integers. BA 452 Lesson B.3 Integer Programming 7 Rounding Off A LP in which all the variables are restricted to be integers is called an all-integer linear program (ILP). The LP that results from dropping the integer requirements is called the LP Relaxation of the ILP. If only a subset of the variables are restricted to be integers, the problem is called a mixed-integer linear program (MILP). Binary variables are variables whose values are restricted to be 0 or 1. If all variables are restricted to be 0 or 1, the problem is called a 0-1 or binary integer linear program. BA 452 Lesson B.3 Integer Programming 8 Rounding Off Solve the following all-integer linear program, and compare that solution to the problem where the decision variables do not have to be integers: Max 3x1 + 2x2 s.t. 3x1 + x2 < 9 x1 + 3x2 < 7 -x1 + x2 < 1 x1, x2 > 0 and integer BA 452 Lesson B.3 Integer Programming 9 Rounding Off LP Relaxation. If we drop the integer constraints, we can graph the optimal solution to the linear program. And the optimal solution has fractional values: x1 = 2.5, x2 = 1.5, Max 3x1 + 2x2 = 10.5 x2 5 - x1 + x2 < 1 4 3x1 + x2 < 9 3 Max 3x1 + 2x2 Max s.t. 3x1 + 2x2 3x1 + x2 < 9 x1 + 3x2 < 7 -x1 + x2 < 1 x1, x2 > 0 and integer LP Optimal (2.5, 1.5) 2 x1 + 3x2 < 7 1 x1 1 2 3 4 5 6 7 BA 452 Lesson B.3 Integer Programming 10 Rounding Off Rounding Up. If we round up the fractional solution (x1 = 2.5, x2 = 1.5) to the previous relaxed LP problem, we get x1 = 3 and x2 = 2. But the graph shows those values are infeasible. x2 - x1 + x2 < 1 5 Max s.t. 3x1 + 2x2 3x1 + x2 < 9 x1 + 3x2 < 7 -x1 + x2 < 1 x1, x2 > 0 and integer 3x1 + x2 < 9 4 Max 3x1 + 2x2 3 ILP Infeasible (3, 2) LP Optimal (2.5, 1.5) 2 x1 + 3x2 < 7 1 x1 1 2 3 4 5 6 7 BA 452 Lesson B.3 Integer Programming 11 Rounding Off Rounding Down. By rounding the non-integer solution down to x1 = 2, x2 = 1, we have a feasible solution, with objective function 3x1 + 2x2 = 8. But that solution is not optimal for the integer program. x2 - x1 + x2 < 1 5 Max s.t. 3x1 + 2x2 3x1 + x2 < 9 x1 + 3x2 < 7 -x1 + x2 < 1 x1, x2 > 0 and integer 3x1 + x2 < 9 4 Max 3x1 + 2x2 3 x1 + 3x2 < 7 2 ILP Optimal (3, 0) 1 Optimal ILP solution. The optimal ILP solution (3,0) is not the closest feasible point to the non-integer solution (2.5,1.5). x1 1 7 2 3 4 5 6 BA 452 Lesson B.3 Integer Programming 12 Rounding Off Exhaustive Search. One way to solve the integer linear program is to evaluate the objective function at each feasible solution. There are 8 alternative feasible solutions in Example 1. 1. 2. 3. 4. 5. 6. 7. 8. x1 x2 0 1 2 3 0 1 2 1 0 0 0 0 1 1 1 2 3x1 + 2x2 0 3 6 9 2 5 8 7 Max s.t. 3x1 + 2x2 3x1 + x2 < 9 x1 + 3x2 < 7 -x1 + x2 < 1 x1, x2 > 0 and integer optimal solution BA 452 Lesson B.3 Integer Programming 13 Rounding Off Max s.t. 3x1 + 2x2 3x1 + x2 < 9 x1 + 3x2 < 7 -x1 + x2 < 1 x1, x2 > 0 and integer BA 452 Lesson B.3 Integer Programming 14 Rounding Off Max s.t. 3x1 + 2x2 3x1 + x2 < 9 x1 + 3x2 < 7 -x1 + x2 < 1 x1, x2 > 0 and integer ILP Optimal (3, 0) BA 452 Lesson B.3 Integer Programming 15 Sensitivity Analysis with Integer Variables Sensitivity Analysis with Integer Variables BA 452 Lesson B.3 Integer Programming 16 Sensitivity Analysis with Integer Variables Overview Sensitivity Analysis with Integer Variables is more important than Sensitivity Analysis with Continuous Variables because a small change in a constraint coefficient can cause a relatively large change in the optimal solution, and in the objective-function value of the optimal solution. BA 452 Lesson B.3 Integer Programming 17 Sensitivity Analysis with Integer Variables Sensitivity analysis often is more crucial for ILP problems than for LP problems. A small change in a constraint coefficient can cause a relatively large change in the optimal solution, and the objective-function value of the optimal solution. Recommendation: Resolve the ILP problem several times with slight variations in the coefficients before choosing the “best” solution for implementation. BA 452 Lesson B.3 Integer Programming 18 Sensitivity Analysis A small change in the constraints (adding the red feasible area) can cause a jump in the objective function at the optimum, from 9 to 10. x2 5 Max 3x1 + 2x2 = 9 at old optimum (3,0) 4 3 Max 3x1 + 2x2 = 10 at new optimum (2,2) 2 1 x1 1 7 2 3 4 5 6 BA 452 Lesson B.3 Integer Programming 19 Assignment with Valuable Time Assignment with Valuable Time BA 452 Lesson B.3 Integer Programming 20 Assignment with Valuable Time Overview Assignment Problems with Valuable Time minimize the total time of assigning workers to jobs. Minimizing total time is appropriate when each worker has the same value of time. BA 452 Lesson B.3 Integer Programming 21 Assignment with Valuable Time Question: The NPD Group is a market research firm with three clients that each request the firm conduct a sample survey. Four statisticians can be assigned to these three projects; however, all four are busy, and therefore can handle only one client. The following are the number of hours required for each statistician to complete each job. The differences in time are based on experience and ability of the statisticians. Client A Client B Client C Statistician 1 150 210 270 Statistician 2 170 230 220 Statistician 3 180 230 225 Statistician 4 160 240 230 BA 452 Lesson B.3 Integer Programming 22 Assignment with Valuable Time What is the most natural objective function for the firm to optimize? Formulate the firm’s optimization problem. Are there any implicit assumptions in your formulation? BA 452 Lesson B.3 Integer Programming 23 Assignment with Valuable Time Answer: Linear programming formulation (supply inequality, demand equality). Variables: Xij = 1 if Statistician i is assigned to Client j, else 0 Objective (minimize time, assuming all time values equal): Min 150X11 + 210X12 + 270X13 + 170X21 + 230X22 + 220X23 + 180X31 + 230X32 + 225X33 + 160X41 + 240X42 + 230X43 Supply Constraints (Statisticians to at most 1 Client): X11 + X12 + X13 < 1, X21 + X22 + X23 < 1, X31 + X32 + X33 < 1, X41 + X42 + X43 < 1 Demand Constraints (each Client served): X11 + X21 + X31 + X41 = 1 X12 + X22 + X32 + X42 = 1 X13 + X23 + X33 + X43 = 1 BA 452 Lesson B.3 Integer Programming 24 Assignment with Supply and Demand Assignment with Supply and Demand BA 452 Lesson B.3 Integer Programming 25 Assignment with Supply and Demand Overview Assignment Problems with Supply and Demand are Transportation Problems of suppliers to demanders except that each demand is assigned to exactly one supplier. BA 452 Lesson B.3 Integer Programming 26 Assignment with Supply and Demand Question: Dow Chemical uses the chemical Rbase in production operations at five divisions. Only six suppliers of Rbase meet Dow’s quality standards. The quantity of Rbase needed by each Dow division and the price per gallon charged by each supplier are as follows: Demand (1000s of gallons) Div 1 40 Div 2 45 Div 3 50 Div 4 35 Div 5 45 Price per Gallon ($) Sup 1 12.60 Sup 2 14.00 Sup 3 10.20 Sup 4 14.20 Sup 5 12.00 Sup 6 13.00 BA 452 Lesson B.3 Integer Programming 27 Assignment with Supply and Demand The cost per gallon ($) for shipping from each supplier to each division are as follows: Cij Div 1 Div 2 Div 3 Div 4 Div 5 Sup 1 2.75 0.80 4.70 2.60 3.40 Sup 2 2.50 0.20 2.60 1.80 0.40 Sup 3 3.15 5.40 5.30 4.40 5.00 Sup 4 2.80 1.20 2.80 2.40 1.20 Sup 5 2.75 3.40 6.00 5.00 2.60 Sup 6 2.75 1.00 5.60 2.80 3.60 BA 452 Lesson B.3 Integer Programming 28 Assignment with Supply and Demand Dow wants to diversify by spreading its business so that each division’s demand is assigned to exactly one supplier. Formulate the optimal assignment of suppliers to divisions as a linear-programming problem. BA 452 Lesson B.3 Integer Programming 29 Assignment with Supply and Demand Answer: Linear programming formulation (supply inequality, demand equality). Variables: Xij = 1 if Supplier i is assigned to Division j, else 0 Assignment Costs The total cost is the sum of the purchase cost and the transportation cost. Supplier 1 assigned to Division 1 (cost in $1000s): Purchase cost: (40 x $12.60) = $504 Transportation Cost: (40 x $2.75) = $110 Total Cost: $614 BA 452 Lesson B.3 Integer Programming 30 Assignment with Supply and Demand Assignment Costs: Cij = Cost of assigning Supplier i to Division j Cij Div 1 Div 2 Div 3 Div 4 Div 5 Sup 1 614 603 865 532 720 Sup 2 660 639 830 553 648 Sup 3 534 702 775 511 684 Sup 4 680 693 850 581 693 Sup 5 590 693 900 595 657 Sup 6 630 630 930 553 747 BA 452 Lesson B.3 Integer Programming 31 Assignment with Supply and Demand Linear programming formulation (supply inequality, demand equality). Objective (minimize cost): Min S Cij Xij Demand Constraints (since each division’s demand is assigned to exactly one supplier): X11 + X21 + X31 + X41 + X51 + X61 = 1 X12 + X22 + X32 + X42 + X52 + X62 = 1 X13 + X23 + X33 + X43 + X53 + X63 = 1 X14 + X24 + X34 + X44 + X54 + X64 = 1 X15 + X25 + X35 + X45 + X55 + X65 = 1 BA 452 Lesson B.3 Integer Programming 32 Assignment with Supply and Demand Optional: There is no mention of supply constraints, which are common in assignment problems. Here is what those common constraints would be in this problem. Supply Constraints (Each supplier can supply at most 1 Division): X11 + X12 + X13 + X14 + X15 < 1 X21 + X22 + X23 + X24 + X25 < 1 X31 + X32 + X33 + X34 + X35 < 1 X41 + X42 + X43 + X44 + X45 < 1 X51 + X52 + X53 + X54 + X55 < 1 X61 + X62 + X63 + X64 + X65 < 1 BA 452 Lesson B.3 Integer Programming 33 BA 452 Quantitative Analysis End of Lesson B.3 BA 452 Lesson B.3 Integer Programming 34