15 081J 6 251J Introduction to Mathematical Programming Lecture 14 Large Scale Optimization I 1 Outline Slide 1 1 The idea of column generation 2 The cutting stock problem 3 Stochastic programming 2 Column Generation Slide 2 For x n and n large consider the LOP min c x s t Ax b x 0 Restricted problem min ci xi Ai xi b i I s t i I x 0 2 1 Two Key Ideas Slide 3 Generate columns Aj only as needed Calculate mini ci e ciently without enumerating all columns 3 The Cutting Stock Problem Slide 4 Company has a supply of large rolls of paper of width W bi rolls of width wi i 1 m need to be produced Example w 70 inches can be cut in 3 rolls of width w1 17 and 1 roll of width w2 15 waste 70 3 17 1 15 4 Slide 5 Given w1 wm and W there are many cutting patterns 3 1 and 2 2 for example 3 17 1 15 70 2 17 2 15 70 1 Pattern a1 am integers m ai wi W i 1 3 1 Problem Slide 6 Given wi bi i 1 m bi number of rolls of width wi demanded and W width of large rolls Find how to cut the large rolls in order to minimize the number of rolls used 3 2 Concrete Example Slide 7 What is the solution for W 70 w1 21 w2 9 b1 20 b2 21 feasible patterns 2 3 3 0 0 7 2 0 Solution 1 2 3 7 rolls 3 0 2 rolls 9 rolls total Solution 2 0 7 3 3 0 6 2 0 1 10 rolls total Slide 8 W 70 w1 20 w2 11 b1 12 b2 17 Feasible patterns 10 20 30 01 11 21 02 12 22 03 13 0 1 0 0 4 4 5 6 x1 x15 of feasible patterns of the type 10 06 respectively min s t x15 x1 1 2 0 12 x2 x15 x1 0 0 6 17 x1 x15 0 Slide 9 0 0 3 12 Example 2 1 4 6 5 0 17 4 0 0 3 12 4 4 1 0 17 Any ideas 2 7 rolls used 9 rolls used 3 3 Formulation Slide 10 Decision variables xj number of rolls cut by pattern j characterized by vector Aj n min xj j 1 b1 n Aj xj j 1 bm xj 0 integer Slide 11 Huge number of variables Can we apply column generation that is generate the patterns Aj on the y 3 4 Algorithm Slide 12 Idea Generate feasible patterns as needed W 0 w1 0 W w2 1 Start with initial patterns 0 0 0 0 0 0 0 0 0 W w3 W w 0 4 Slide 13 2 Solve min x1 xm x1 A1 xm Am b xi 0 Slide 14 3 Compute reduced costs cj 1 p Aj for all patterns j If cj 0 current set of patterns optimal If cs 0 xs needs to enter basis How are we going to compute reduced costs cj 1 p Aj for all j huge number 3 3 4 1 Key Idea Slide 15 4 Solve m z max i 1 m s t p i ai wi ai W i 1 ai 0 integer This is the integer knapsack problem Slide 16 If z 1 1 p Aj 0 j current solution optimal If z 1 s 1 p As 0 Variable xs becomes basic i e a new pattern As will enter the basis Perform min ratio test and update the basis 3 5 Dynamic Programming Slide 17 F u max p1 a1 pm am s t w1 a1 wm am u ai 0 integer For u wmin F u 0 For u wmin F u max pi F u wi i 1 m Why 3 6 Example Slide 18 max 11x1 7x2 5x3 x4 s t 6x1 4x2 3x3 x4 25 xi 0 xi integer F 0 0 F 1 1 F 2 1 F 1 2 F 3 max 5 F 0 1 F 2 5 F 4 max 7 F 0 5 F 1 1 F 3 7 F 5 max 7 F 1 5 F 2 1 F 4 8 F 6 F 7 F 8 F 9 F 10 F u max 11 F 0 7 F 2 5 F 3 1 F 5 11 max 11 F 1 7 F 2 5 F 3 1 F 4 12 max 11 F 2 7 F 4 5 F 5 1 F 7 14 11 F 3 16 11 F 4 18 11 F u 6 16 u 11 4 Slide 19 F 25 11 F 19 11 11 F 13 11 11 11 F 7 33 12 45 x 4 0 0 1 4 Stochastic Programming 4 1 Example Steel lbs Molding machine hrs Assembly machine hrs Demand limit tools day Contribution to earnings 1000 units Slide 20 Wrenches 1 5 1 0 0 3 15 000 130 Pliers 1 0 1 0 0 5 16 000 100 Cap 27 000 21 000 9 000 Slide 21 max 130W 100P s t W 15 P 16 1 5W P 27 W P 21 0 3W 0 5P 9 W P 0 4 1 1 Random data Assembly capacity is random 8000 with probability 10 000 with probability Contribution from wrenches 160 with probability 90 4 1 2 with probability 1 2 1 2 Slide 22 1 2 1 2 Decisions Slide 23 Need to decide steel capacity in the current quarter Cost 58 1000lbs Soon after uncertainty will be resolved Next quarter company will decide production quantities 4 1 3 Formulation Slide 24 5 State 1 2 3 4 Cap 8 000 10 000 8 000 10 000 W contr 160 160 90 90 Decision Variables S steel capacity Pi Wi i 1 4 production plan under state i max s t Ass 1 Mol 1 Ste 1 W d 1 P d 1 Obj 1 4 1 4 Slide 25 58S 0 25Z1 0 25Z2 0 25Z3 0 25Z4 0 3W1 0 5P1 8 W1 P1 21 S 1 5W1 P1 0 W1 15 P1 16 Z1 160W1 100P1 0 Slide 26 Ass Mol Ste W d P d Obj 2 2 2 2 2 2 0 3W2 0 5P2 8 W2 P2 21 S 1 5W2 P2 0 W2 15 P2 16 Z2 160W2 100P2 0 Ass Mol Ste W d P d Obj 3 3 3 3 3 3 0 3W3 0 5P3 8 W3 P3 21 S 1 5W3 P3 0 W3 15 P3 16 Z3 160W3 100P3 0 Ass Mol Ste W d P d Obj 4 4 4 4 4 4 0 3W4 0 5P4 8 W4 P4 21 S 1 5W4 P4 0 W4 15 P4 16 Z4 160W4 100P4 0 S Wi Pi 0 Solution Slide 27 Slide 28 Slide 29 Solution S 27 250lb 1 2 3 4 Prob 0 25 0 25 0 25 0 25 Wi 15 000 15 …