15.093: Optimization Methods Lecture 9: Large Scale OptimizationX X 1 Outline Slide 1 1. The idea of column generation 2. The cutting sto ck 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 cixi i∈I s.t. Aixi = b i∈I x ≥ 0 2.1 Two Key Ideas Slide 3 • Generate columns Aj only as needed. • Calculate mini ci efficiently 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 1X                                 • Pattern: (a1, . . . , am) integers: m aiwi ≤ 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 = 11, b1 = 40, b2 = 40? • feasible patterns: (2, 2), (3, 0), (0, 6) • Solution 1: (2, 2) : 20 patterns; 20 rolls used • Solution 2: (3, 0) : 12, (0, 6) : 9, (2, 2) : 2 patterns: 23 rolls used Slide 8 • W = 70, w1 = 20, w2 = 11, b1 = 12, b2 = 17 • Feasible patterns: 01 , 02 , 03 , 10 , 11 , 12 , 20 , 21 , 22 , 30 , 31 , 0 1 0 0 4 , ,,4 5 6 • x1, . . . , x15 = # of feasible patterns of the type 01 , . . . , 60 respectively • min x1 + · · · + x15 1 2 0 12 s.t. x1 + x2 + · · · + x15 = 0 0 6 17 x1, . . . , x15 ≥ 0 Slide 9 0 0 312 • Example: 2 + 1 + 4 = 7 rolls used 6 5 017 00 312 4 + + 4 = 9 rolls used 41 017 • Any ideas? 2P P 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 fly? 3.4 Algorithm Slide 12 Idea: Generate feasible patterns as needed.         ⌊W ⌋ 00 0 w1  0   ⌊W ⌋   0   0     w2     1) Start with initial patterns:  0  ,  0  ,  ⌊W ⌋  ,  0  w3 00 0 ⌊W ⌋ w4 Slide 13 2) Solve: min x1 + · · · + xm x1A1 + · · · + xmAm = 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 ar e we going to compute reduced costs cj = 1 − p ′ Aj for all j? (huge number) 3X X 3.4.1 Key Idea Slide 15 4) Solve m ∗ z = max piai i=1 m s.t.wiai ≤ 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 p1a1 + · · · + pmam s.t. w1a1 + · · · + wmam ≤ 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 Slide 19 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) = max(11 + F (0)∗ , 7 + F (2), 5 + F (3), 1 + F (5)) = 11 F (7) = max(11 + F (1)∗ , 7 + F (2), 5 + F (3), 1 + F (4)) = 12 F (8) = max(11 + F (2), 7 + F (4)∗ , 5 + F (5), 1 + F (7)) = 14 F (9) = 11 + F (3) = 16 F (10) = 11 + F (4) = 18 F (u) = 11 + F (u − 6) = 16 u ≥ 11 4⇒ 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) 4.1.1 Random data Wrenches 1.5 1.0 0.3 15,000 $130* Pliers 1.0 1.0 0.5 16,000 $100 Slide 20 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 Slide 22  1   8000 with probability 2 • Assembly capacity is random:  …