Name: |
TakeHome Midterm Exam, Thursday, March 26, 2020.
Due: Noon, Monday, March 30, 2020.
Scan in a pdf version of your solutions and upload to LMS.
Solutions
Please do all four problems. Show all work. You may use any result from class, the homeworks, or the texts, except where stated.
Scan in a pdf version of your solutions and upload to LMS. You can alternatively write your solutions in LaTeX. Include your name in the name of any file you submit.
I will have WebEx office hours on Thursday from 1-2pm and on Friday from 11am-1pm.
Q1 | /20 | |
Q2 | /20 | |
Q3 | /20 | |
Q4 | /40 | |
Total | /100 |
| (1) |
Solution:
Assume x^{*} is optimal. Let
where e is the vector of ones in ℝ^{n}. Then x(λ) is feasible in the modified LP for any λ ≥ 0, and c^{T }x(λ) = c^{T }x^{*}. So the modified problem has an unbounded set of optimal solutions.
The dual constraints imply H^{T }y = g, so NO, no dual feasible solution satisfying the given condition exists.
| (2) |
has second stage cost
| (3) |
Assume all matrices and vectors are dimensioned appropriately. In class, we discussed solving (2) using the L-shaped decomposition method. In class, we only considered the case where the problem has complete recourse, so the second stage problem (3) is feasible for any x feasible in (2).
How can the method be modified if the assumption of complete recourse does not hold? (Assume the dual LP to the subproblem (3) is feasible.)
Solution:
In the L-shaped method, we choose a first stage decision then solve the dual of the second stage problem in each scenario to find ^{s}, and then add the constraint
If the first stage decision is infeasible then there exists a scenario ξ^{s} where the dual is unbounded. The dual is
Hence there exists a dual ray W^{T } ≤ 0 and ^{T } > 0. This is always a ray, and the dual subproblem will be unbounded for any x satisfying ^{T } > 0. In other words, any x satisfying ^{T } > 0 will be infeasible in scenario ξ^{s}. Thus, if we determine that is infeasible in some scenario ξ^{s} with dual ray , we add the constraint
withto the Master Problem. Equivalently,
| (4) |
with m = 10 and n = 30. The seed is contained in the data file, so choose a random seed and generate an LP. Note that c_{j} = 1 for all j, and b_{i} = ∑ _{j=1}^{n}(A_{ ij} - 1) for all i. We consider the robust LP model
| (5) |
where â_{ij} = 1 for all i, j, and Γ_{i} = 15 for all i = 1,…, 10. Solve (5). In addition to your optimal x and optimal value, submit your seed, and also submit a data file containing A.
Note: You don’t need to use AMPL to solve the robust problem, you’re welcome to use a different LP solver. You will need to run AMPL to generate the data file using the command
This command will display the A matrix, which you could copy and paste into another solver. The run command also generates a data file containing A, which you can email to me: please put your name in the title of the file.
(If you don’t even want to use AMPL to generate the data, ensure you generate an instance in the same way, and submit your A matrix using exactly the formatting indicated in the run file.)
Solution:
Solve the LP
where each â_{ij} = 1. The optimal value is probably in the mid-20s. The non-robust version probably has an optimal value in the high teens. The ampl model and run files can be found on LMS and the course webpage.
| (6) |
where A ∈ ℝ^{m×n} and rank(A) = m, and b and c are dimensioned appropriately and c has at least one nonzero component. For any nonnegative scalar parameters μ and ν, we can set up a relaxation of (6):
| (7) |
| (8) |
where
Any minimizer of f(x) must satisfy ∇f(x) = 0. Show that if is a minimizer of f(x) then is infeasible in (6).
for a generic μ > 0, ν > 0. What is the dual solution you obtain using the construction of part 4d? (Hint: the optimal solution has x_{1} < 0, x_{2} > 0.)
Solution:
We need to show this is a strict inequality. We assume it is an equality and derive a contradiction.
Note that we have equality in the first inequality only if A = b and ≥ 0. Pick a component j with c_{j}≠0. Let e_{j} denote the jth unit vector and let a_{j} denote the jth column of A. Define
for ϵ ≥ 0. Note that
Hence does not minimize (7), a contradiction.
from the definition of t. Hence, the constructed y is dual feasible. We get a lower bound of
| (9) |
From the second line, we have
| (10) |
and so from the first line we have
| (11) |
It follows from (10) that
| (12) |
It follows from (10) that
| (13) |
Note that the dual problem is
which has optimal solution y = .