MATP6640/DSES6770 Linear Programming, Homework 5.
Due: 11.59pm on Friday, April 1, 2022 on LMS.
10% penalty for each day late.
Prove that ρ(x) is a convex function of x.
Let x(1) and x(2) be feasible first stage decisions. Since the problem has complete recourse, there are optimal second stage solutions (ys(i).η(i),v s(i)) ∀s for the first stage decisions x(i), i = 1, 2. Let λ ∈ [0, 1] and define x = λx(1) + (1 - λ)x(2). Define ys = λys(1) + (1 - λ)ys(2) ∀s, η = λη(1) + (1 - λ)η(2), and v s = λvs(1) + (1 - λ)v s(2) ∀s. Then (ys,η,v s) ∀s is a feasible second stage decision for the first stage decision x. Thus,
so ρ(x) is convex.
Here, we’ve weighted the CVaR by μ to trade it off with the expected return. We saw the L-shaped method for solving stochastic programming problems in class. At iteration K, a disaggregated Master Problem for problem (1) has the form
where Q(xk,ξs) is the optimal value of the second stage problem with first stage decision xk and scenario ξs, and the subgradient vector ζ sk has the form
Hence, we can use the constraint
These S constraints can replace the constraints
It is clear from the construction that any optimal solution to (2) must satisfy (3).
Conversely, given x and t, if η and v satisfy (3) then
so the solution is feasible in (2).
To find an upper bound, we need to find a feasible solution to (1). We take x = x and then we choose η and v to solve the linear program
This is feasible in (1).
Note that the LP can be solved very easily. For example, we can set up the dual problem and exploit complementary slackness, and all that is required is to order the values of Q(x,ξs).
You will need to load in both data files.
Model and run files for minimizing the expectation using ampl are available:
You will need to modify these files to handle the formulation in Question 2
The same problem is solved in both parts, so they give the same solution with value 156 with xrt = 2, xru = xrv = 12, xtu = xtv = 0. In the notation of Question 2, the optimal solution has η = 156, with unmet demand in scenarios 2 and 30.
Here is the output for part (a).
Here is the modified model file for part (b).
Here is the modified run file for part (b).
Here is the output for part (b).
Show that x = (3, 1, 2) is on the central path for this problem.
The point y = (0, 0), s = (2, 6, 3) is dual feasible, and then xisi = 6 =: μ for i = 1, 2, 3.
(Most of the problems are also available in AMPL format and MATLAB format and uncompressed MPS format at http://clas.ufl.edu/users/hager/coap/format.html with an AMPL model file available both at http://clas.ufl.edu/users/hager/coap/m2a and at http://www.netlib.org/ampl/models/mps.mod
Alternatively, you can run cplex directly, without using ampl, in which case you would read in the MPS file. Useful commands in cplex include read, optimize, and display. You can choose the solver in cplex by issuing the command set lpmethod at the prompt. You can change options in the barrier solver (including the use of crossover) with the command set barrier. You can use these options in ampl with the syntax option cplex_options ’...’;)
Hand in the primal solution for each problem, and discuss whether the three solutions differ for each of the models you chose. If the solutions have too many variables it is fine to select a few variables to display.
The problem boeing1 should give three different solutions. For example, you can look at the variable PLAXSEA8 in these solutions.