Systems Optimization - Models and Computation Assignment 3

1 KKT Conditions (15 points) Consider the following problem: (x1 minimum x 4)2 + (x2 6)2 x21 + x2 s.t. x2  0  4 x 2 <2 : Write a necessary condition for optimality and verify that it is satis ed by the point (2; 4). Is this the optimal point? Why or why not? 2 Questions on Convexity (20 points) (a) Consider the function f (x) = c x + 12 x Qx? Suppose that   8 32 Q= : 8 2 T T Is f (x) a convex function? Why or why not? Now suppose that   5 4 Q= : 4 2 Is f (x) a convex function? Why or why not? (b) For x 2 < consider the function: n f (x) = min   =1;:::;p i { Prove that f (x) is a concave function. 1 a i T  x+b i : { For any x, let I (x) denote the set of binding linear functions of f (x), namely:    I (x) := i j f (x) = a i T  x+b i : Prove that at any given point x, it is true that g is a subgradient of f (x) at x if and only if g can be written as a convex combination of those a for which i 2 I (x). More formally we write this as: X X g=  a ;   0; i 2 I (x) ;  =1: i i i i i 2I (x ) 2I (x ) i i Hint: proving the \if" part is easy. To prove the \only if" part, use linear programming duality. 3 Optimality Conditions (10 points) Consider the following problem: P: minimize f (x1 ; x2 ) = x1 ln(12 x2 ) ln(8 + x1 x2 ) 2 x 7 2 (i) Show that (x1 ; x2 ) = (2; 3) satis es the rst-order necessary conditions for a solution of P . (ii) Show that this point is the global minimum of f (x). 4 Modeling Using Integer Programing (25 p oints) The Powerplant Unit Commitment Problem An energy provider owns three powerplants, each with a capacity of 250 MW (MegaWatts). Each powerplant can be operated at any level p between 0 MW and 250 MW. However, the cost of producing power at level p for one hour, measured in million dollars per MW, is a piecewise linear function of the power level p, shown in Figure 1. Note from Figure 1 that c(0) = $0:00/hour, but c(0+) = $6:00 million/hour. The consumer demand for power varies by the time of day, as shown in Table 1. We would like to meet demand for power throughout the day at minimum cost. Running a single powerplant at 225 MW from 00:00 to 08:00, running two powerplants at 250 MW each from 08:00 to 16:00, and running a single powerplant at 250 MW from 16:00 to 24:00, would be a feasible (but suboptimal) operating plan. This plan would cost: $(8  1  5 + 8  2  6 + 8  1  6) = $184 million: 2 Time of Day Demand for Power (MW) midnight to 08:00 225 MW 08:00 to 16:00 500 MW 250 MW 16:00 to 24:00 Table 1: The demand for power varies by the time of day. 6 5 Millions of Dollars 4 3 2 1 0 0 50 100 150 200 250 MW Hours Figure 1: Cost per MW per hour of operating a powerplant, in $ million. 3 6 5 4 y 3 2 1 0 −1 −1 0 1 2 x 3 4 5 Figure 2: Illustration of the boundaries of the inequality constraints of IP1. Construct a mixed integer program to determine a minimum cost operating plan for the powerplants that satis es the demand for power for each time of day. Solve your model using OPL Studio. (Note that this exercise ignores powerplant start-up times, shutdown times, and shortterm uctuations in demand. We will explore some of these other issues in a later modeling assignment.) 5 Integer Programming Duality (25 p oints) Consider the integer constrained problem IP1 : Z  = minimum 4x x;y s.t. + y + 2y 2x 2x + 2y 7x + 6y 5x + 6y 3x + 12y x; y 0 x; y integer: 4      5 1 60 20 42 Question (a): Relax the constraint 3x + 12y  42 and determine the Lagrangean dual function, L (u). L (u) will be of the form L (u) = min( )2 ( 4x + y + u( 42 + 3x + 12y)). P is the set of integer pairs satisfying the remaining constraints. x;y Question (b): What is the optimal objective value v = max u P  0 L (u) of this dual problem? Note that the next two questions can be answered graphically. Question (c): How does the v compare to Z  , the optimal value of the original problem? Does this make sense? IP Question (d): How does the v compare to Z  , the optimal value of the linear programming relaxation of the problem? Does this make sense? LP Question (e): In practice you would not enumerate all integer points in P . What method could be used to solve the dual problem? Question (f): Solve this problem using the method you selected above. 6 Uncapacitated Facility Location (35 p oints) The uncapacitated facility location problem can be described as follows. We are given a set N = f1; 2; : : : ; ng of potential facility locations and a set I = f1; 2; : : : ; mg of clients. A facility placed at location j costs c to construct, for j 2 N . The total cost of satisfying the demand of client i from a facility at location j is d . The optimization problem is to choose a subset of the locations at which to place facilities and then to assign the clients to these facilities so as to minimize total system cost. There is no restriction on the number of clients that a facility can serve. Each client can only be served by one facility. j i;j It is well known that the uncapacitated facility location problem is NP-hard. In this assignment, we explore various algorithmic approaches related to this problem. Consider the following models: Model UF L1 minimize P j s.t. 2N P cy + j P j 2I ;j 2N d x i;j i;j 8 i 2 I; x  y 8 i 2 I; j 2 N x 2 f0; 1g 8 i 2 I; j 2 N y 2 f0; 1g 8 j 2 N: j 2N (1) i x =1 i;j i;j j i;j j 5 (2) (3) (4) (5) Model UF L2 P minimize j =1 i;j (6) i;j 8 i 2 I; (7) i;j i;j  my 8 j 2 N 2 f0; 1g 8 i 2 I; j 2 N y 2 f0; 1g 8 j 2 N: m i d x 2I ;j 2N x =1 2N P j i P j x j 2N s.t. P cy + x i;j (8) j (9) (10) j Equation (8) in (UF L2) is an aggregation of equation (3) in (UF L1), so model (UF L2) has fewer constraints than model (UF L1). Question (a): Show that the feasible integral solution to the two formulations (UF L1) and (UF L2) are identical. Question (b): Consider the the following Lagrangian relaxation of (UF L2), where we place equation (7) in the objective function: P : u  L (u) := minimum P j 2N P cy + j j 2I ;j 2N d x + i;j i;j i P =1 i x i;j 2I u i 1 i P j 2N ! x i;j  my 8 j 2 N 2 f0; 1g 8 i 2 I; j 2 N y 2 f0; 1g 8 j 2 N: m s.t. P x i;j j j (11) (12) (13) (14) Let L (u) be the optimal value of the problem P . The Lagrangian dual then is: u D : maximum u L (u) u2< s.t. n Note here u is not restricted in sign, since we dualized on equality constraints. Describe how you would solve the problem P to obtain the value of L (u) for any u. (Hint: carefully examine P and see if you can solve it by inspection!) u u 6 Question (c): The uncapacitated facility location problem can also be formulated as the following set partitioning problem: P j s.t. P n minimize P n j =1 S f1;2;:::;mg P f (S )z (S ) j (15) j 8 i 2 I; z (S ) 2 f0; 1g 8 j 2 N; S  I: z (S ) = 1 j =1 S f1;2;:::;mg;i2S j (16) (17) The variable z (S ) denotes the decision to serve the set S of clients using the facility at location j . The objective function coeÆcient of the variable z (S ) is the value f (S ) de ned as: j j f (S ) = c + j X j j d : i;j 2S i Constraint (16) models the fact that each client can only be served by one facility. The les 1c.dat, 2c.dat, 3c.dat, and 4c.dat each are a data set for an instance of the uncapacitated facility location model. Construct a column generation algorithm in OPL script to solve the LP relaxation of the set partitioning model of the uncapacitated facility location problem, for these four problem instances. 7