MATP6640/DSES6770 Linear Programming, Homework 5.

Due: 11.59pm on Friday, April 1, 2022 on LMS.
10% penalty for each day late.

  1. Let a stochastic program have a finite set S of scenarios ξs, each with probability p s. Let the first stage decision variables be x +n and assume the problem has complete recourse for any first stage decision. Let 0 < α < 1. For any feasible first stage decision x, the Conditional Value at Risk ρ(x) can be calculated by solving the problem
                                   1∑
ρ(x) :=   miny,η,v        η  +   α   s∈S psvs
         subject to W  ys  =  hs - T sx  ∀s ∈ S
                    qT ys  ≤  η + v      ∀s ∈ S
                        s          s
                       y   ≥  0          ∀s ∈ S

    Prove that ρ(x) is a convex function of x.

  2. Assume we have a stochastic program with finite number of scenarios and complete recourse. A weighted combination of the standard stochastic program expectation objective with CVaR can be written
                             ∑                 (      ∑      )
minx,v,η         cTx  +     s psQ(x, ξs) + μ η + 1α-  spsvs
subject to       Ax          =   b
            Q (x, ξs) -    η  ≤   v   ∀s
                                  s
                         vs  ≥   0  ∀s
                  x          ≥   0
    (1)

    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

    min           cT x  +   ∑S   p t +  μ(η +  1∑   p v )
    x,t,μ,v                 s=1 s s          α   s s s
subjectktoT     Axk              =   b   k  s
     (ζs) (x - x )  +       ts ≥   Q (x ,ξ )  for s = 1,...,S, k = 1,2,...,K  - 1
     (ζks)T(x - xk)  +   η + vs ≥   Q (xk,ξs)  for s = 1,...,S, k = 1,2,...,K  - 1
                 x             ≥   0
                           v   ≥   0          for s = 1,...,S
                             s
    (2)

    where Q(xks) 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

    ζks = T (ξs)Tπsk

    1. Exploit the relationships between η + vs, Q(x,ξs), and t s to derive an equivalent formulation with fewer constraints. (Hint: formulation (2) has 2S(K - 1) subgradient inequalities. Can you construct an equivalent formulation with approximately SK constraints to represent the subgradient information?)
    2. Assume (x,t,μ,v) is optimal in (2). How would you find upper and lower bounds on the optimal value of (1)?
  3. Consider the capacity expansion problem considered in class, but with 30 scenarios. The ampl data file is here: http://www.rpi.edu/~mitchj/matp6640/hw5html/cap_exp.dat
    1. Solve the formulation (1) using a direct formulation using ampl, with α = μ = 0.1. Hand in the optimal value and the optimal first stage decisions. A model file and a data file with the data specific to the CVaR formulation are available:
      1. model file: http://www.rpi.edu/~mitchj/matp6640/hw5html/cap_expCVaR.mod
      2. data file: http://www.rpi.edu/~mitchj/matp6640/hw5html/cap_expCVaR.dat

      You will need to load in both data files.

    2. Solve the formulation (1) using the L-shaped formulation you derived in Question 2(b). Hand in the optimal value and the optimal first stage decisions. Also hand in something to convince me you did solve the problem using an L-shaped method! For example, highlight the changes you made to the model and run files, and show some of the output reflecting the progress of the algorithm.

      Model and run files for minimizing the expectation using ampl are available:

      1. run file: http://www.rpi.edu/~mitchj/matp6640/hw5html/cap_expLshaped.run
      2. model file: http://www.rpi.edu/~mitchj/matp6640/hw5html/cap_expLshaped.mod

      You will need to modify these files to handle the formulation in Question 2

  4. Consider the LP:
    min   2x1  +   6x2  +  3x3

s.t.    x1  +    x2  +    x3  =  6
       x1  -   2x2  +  4x3   =  9
                         xi  ≥  0  i = 1,...,3

    Show that x = (3, 1, 2) is on the central path for this problem.

  5. Pick three problems from the netlib LP test suite, at http://www.netlib.org/lp including the problem boeing1. Solve each problem using both a simplex algorithm and an interior point algorithm. Do you get the same primal solution with each algorithm? What if you don’t crossover to get a BFS? (Differences less than 10-8 can be ignored.)

    (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.

  6. Hand in a progress report of your work to date on the course project.
    John Mitchell
    Amos Eaton 325
    x6915.
    mitchj at rpi dot edu
    Office hours: Thursday 11am–1pm., on webex https://rensselaer.webex.com/meet/mitchj