Systems Optimization: Assignment 2

1 Lagrangian Dual (10 points) Consider the problem: P: min x f (x) = 21 x x + c x T T Ax = b s.t. x0 x2< : n Create dual variables u for the constraints \Ax = b" and v for the constraints \x  0", and formulate the Lagrangian. What is the Lagrange dual of this problem? 2 The Frank-Wolfe Algorithm (25 points) Consider the following instance of P : P : minimize f (x) x2C ; s.t. where f (x) = 24x1 + 0:5x14 10x2 + x22 and C = f(x1 ; x2 ) j x1 x2  1; 6x1 + x2  13; x2  7; x1  0; x2  0g : Download the support les fw.zip which contains skeletal code for the Frank-Wolfe algorithm designed to be run using OPLStudio. You may choose to base your code on this skeletal code or not. 1 3  Construct a version of the Frank-Wolfe method and solve this problem starting from the point (x1 ; x2 ) = (0:5; 3:0).   Plot the iterates (x1 ; x2 ). k k Hand in a hard copy of your code, coded in OPLStudio. What stopping criteria did you use? Subgradient Algorithm for Lagrange Dual (20 points) Consider the primal problem: c x OP : minimum T x Ax b  0 s.t. x 2 f0; 1g : n Here g(x) = Ax b and P = f0; 1g = fx j x = 0 or 1; j = 1; : : : ; ng. n j We create the Lagrangian: L(x; u) := c x + u (Ax b) T T and the dual function: L (u) := minimum 2f0 1gn c x + u (Ax b) x T ; T The dual problem then is: L (u) D : maximum u u0 s.t. Now let us choose u  0. Notice that an optimal solution x of L (u) is: x = ( j 0 if (c 1 if (c A u) A u) T T for j = 1; : : : ; n. Also, L (u) = c x + u (Ax T T b) = u b T j j 0 0 Xh n j 2 =1 (c i A u) T j : Also g := g(x) = Ax b is a subgradient of L (u). Now consider the following data instance of this problem: 0 B B B A=B B @ and 1 0 1 6 8 12 C B C 2 3C 1C B C B C 7 5 C C ; b=B B 45 C C @ 20 A 4 6 A 3 14 42 c =( 5 T 4) : Construct a subgradient algorithm for solving Lagrange dual problems, coded in OPLStudio. You may use the skeletal code sg.zip as a starting point. Use your algorithm to solve problem D for the data instance (A; b; c) above, starting at u1 = (1; 1; 1; 1; 1) , with the following step-size choices: T      1 for k = 1; : : :. k = k = p1 for k = 1; : : :. k k k k = 1  (0:99) for k = 1; : : :. k = :9  (0:9775) for k = 1; : : :. k a stepsize rule of your own. Which step-size rules work best for this problem? 4 Solution Strategies for the Cutting Stock Problem (30 points) This question asks you to compare di erent formulations and solution strategies for solving the cutting stock problem. The goal of this question is to demonstrate the power of alternative formulations of an optimization problem, as well as to demonstrate the power of column generation as a solution strategy. We rst revisit the Kantorovich formulation of the cutting stock problem discussed in lecture. We will use the following notation, which is di erent from the notation used in the lecture.  w ; i = 1; : : : ; m: the width of item i. (data)  b ; i = 1; : : : ; m: the demand for stock of width w . (data) i i i 3     W : the width of the large rolls. (data) K : the number of available rolls. (data) y : 1 if roll k is cut, 0 otherwise, k = 1; : : : ; K . (decision variable) k x : number of times that an item of width w is cut on roll k. (decision variable) k i i The objective is to minimize the number of rolls used in order to satisfy demand. X K min x;y k =1 y k We must satisfy demand for each item i = 1; : : : ; m: X K k =1 x k i b i We cannot exceed the width of each roll k = 1; : : : ; K : X m wx i =1 k i  Wy k i The decision variables must also satisfy their bounds and integrality: x 0y k i k 0 1 x; y are integer Note that this formulation solves for the number of rolls that must be cut as well as the pattern (x1 ; : : : ; x ) that is used for each roll k = 1; : : : ; K . k Question (a): k m Solution using the Kantorovich formulation. Use the les kant.mod and kant.osc as a starting point. Finish constructing the OPL model for this formulation and then solve the problem using the data le cs1.dat. Next modify the data le to gain some more experience with the ease and/or diÆculty of solving the cutting stock problem using the Kantorovich formulation. Try varying K , the number of rolls available. Also try varying the number m of items, as well as the widths w ; i = 1; : : : ; m. Next try varying the width W of the large rolls. What do you observe? What is a possible explanation for your observation? Finally, relax the integrality constraints. What happens? i As a common basis of comparison for a sections of this problem use the data les and chv4.dat. cs1.dat,cs2.dat,cs3.dat, chv1.dat,chv2.dat,chv3.dat, 4 You should have found some diÆculty when trying to solve the Kantorivich formulation for some data con gurations. Let us also think about an alternative formulation of the problem. The concept is simple. For a given set of widths, w ; i = 1; : : : ; m, it is \easy" to determine all feasible patterns into which a large roll of width W could be cut. This enumeration could take some time to compute, but it is a straightforward exercise. Once we enumerate all of the feasible cutting patterns, we can then determine the fewest number of rolls to cut in order to satisfy demand. i First, we introduce some more notation:  n: number of possible patterns, j = 1; : : : ; n. (data)  a : The number of items of width w which are cut in pattern j , for i = 1; : : : ; m ij  i and j = 1; : : : ; n. (data) z : The number of rolls that we will cut using pattern j . (decision variable) j Using the above notation, there are n di erent patterns. Each pattern j is represented using (a1 ; a2 ; : : : ; a ) for the j pattern, and satis es the requirement: j j mj th X m a w ij =1 i W i Now, as before, we want to minimize the total number of rolls cut. But now we minimize the sum (over all possible patterns) of the number of rolls cut using each pattern. (A deeper connection between the two formulations was discussed in lecture.) The objective function is: min z X n z j j =1 We must satisfy demand for each item i = 1; : : : ; m: X n a z ij j =1 i b i The decision variables must satisfy their bounds and integrality: z j 0 z is integer j Note that the x from the Kantorovich formulation are not the same as the a of this formulation. k i ij 5 Question (b): Solution using the pattern formulation. Use the le fullmastercs.osc, fullmaster.mod, patterns.osc and as a starting p oint. Finish constructing the OPL model for the pattern formulation of the cutting stock problem and then solve the problem using the data les cs1-3.dat, and chv1-4.dat. Next modify the data le to gain some more experience with the ease and/or diÆculty of solving the cutting stock problem using the pattern formulation. Try varying the width W of the large roll. Also try varying the number m of items. What do you observe? What is a possible explanation for your observation? Finally, relax the integrality constraints. What happens? You should have found some diÆculty when running the OPL model of the pattern formulation. Even when the number of rolls is small, the number of feasible patterns can be huge. Forming the coeÆcient matrix that corresponds to all possible patterns is clearly impractical. However, as was discussed in lecture, this problem is a perfect candidate for column generation. Instead of pre-generating all possible patterns, we generate feasible patterns as necessary. Question (c): Use the les CS.osc, generatecol.mod, selectcol.mod, as a starting point, and nish constructing a column generation algorithm in OPL script to solve the cutting stock problem. Then solve the problem using the data les cs1-3.dat, and chv14.dat. Next modify the data le to gain some more experience with the ease and/or diÆculty of solving the cutting stock problem using column generation. Try varying the width W of the large rolls. Also try varying the number m of items, as well as the widths w ; i = 1; : : : ; m. What do you observe? What is a possible explanation for your observation? What do you observe when comparing this formulation and implementation to the previous formulations and implementations? i 6