15.094- Homework 3 Solved

1           Sparsity
In this exercise we examine what happens to sparsity properties of an LO under robustification. This is important as our ability to solve large scale LO problems within within an acceptable time horizon depends on the sparsity of the problems.

Consider the constraint aTx ≤ b, ∀a ∈U, where U = {a : ka−ak∞ ≤ Γ} (here a ∈Rn and Γ > 0 are given. Formulate the RC as a finite number of linear inequality constraints.
Comment on the sparsity of the new representation in Part (a). If a has mostly zero entries (in which case we would call the constraint aTx ≤ b “sparse”), are the constraints in the new representation of the uncertain constraint still sparse? Please be as specific as possible.
Repeat Parts (a) and (b) with a different uncertainty set:
U = {a : ka − ak1 ≤ Γ}.

What differences, if any, did you observe between Parts (b) and (c)? Offer an explanation for why there are (or are not) differences. Does this say anything about how to choose uncertainty sets?
(Extra Credit) You can test the time performance of the two different uncertain formulations on the robust counterpart of Problem 2.5 (the robust unlimited cash case), by varying the uncertainty type between the box uncertainty and 1-norm uncertainty, for a choice of Γ = 1. Please report the solution time of the two problems. Are the results what you expect? (Note: Make sure to only time the solve step, since the model creation time can be significant. Furthermore, make sure that you solve another problem before you do your time comparison, because of the compile time of JuMP/JuMPeR/Gurobi.)
2           World Food Programme, Syria Case Study
For this problem, we will be considering a simplified example of the multicommodity flow problem that was posed in Lecture 6 on the World Food Programme. The nominal problem is provided in HW3 WFP.jl, with the required data in the Homework3 folder (and we will be covering it in Recitation 5). The principles of the problem are as follows:

The objective of initial problem is to minimize total cost while supplying enough food for all people for the given day.
We have a set of demand nodes (ND).
We have data pc, which designates the prices of goods available at potential supply nodes. The supply nodes are separated into a set of local nodes NL, regional nodes NR and international nodes NI.
We have data hc which designates the edges along which commodities can flow, with the costs in the units of USD per metric ton.
We design rations over all available commodities, to satisfy nutritional constraints. For simplicity, we assume that the rations are the same for all demand nodes, and that all people receive the same rations.
Please note that there are some important unit changes in the constraints. Procurement and transportation costs are in USD/ton. Nutritional requirements per person are in their own values. Nutrient contents of commodities are per 100g of the commodities. The rations are in kgs per person.

We have defined a baseline model and the following variables for your convenience:

Fsource, sink, commodity: how many tons of a commodity travel from source node to sink node.
procurementnode, commodity: how many tons of a commodity are procured in the node.
deliverynode, commodity: how many tons of commodity are delivered to a node.
transportationsource, sink: how many tons of all commodities travel from source node to sink node.
ration ppcommodity: how many kg of a commodity are in one person’s rations.
nutrients ppnutrient: how much of a nutrient is in one person’s rations.
transportation cost: sum of all transportation costs in USD.
procurement cost: sum of all procurement costs in USD.
In this section, you will be consider a series of case studies over the WFP problem, with and without uncertainty, to improve our hypothetical implementation of the program.

Performance Assessment
To be able to assess the performance of our allocation under different constraints and levels of robustness, we will consider the performance metrics below. • Probabilistic guarantee of our resource allocation (0.5 if zero uncertainty, ≥ 0.5 with robustness).

Total cost in USD.
Ratio of procurement cost to total cost.
Ratio of transportation cost to total cost.
Ratio of international procurement cost as a fraction of total procurement cost.
A slack variable on the constraint for nutrients per person. At 1, the nutrient constraint should be satisfied exactly, while values between 0 and 1 the nutritional constraints should be satisfied by the fraction. Total cost per person fed in USD. If we satisfy demand fractionally with a nutrient slack, please count each person by that fraction.
Number of individual purchases (i.e. nonzero procurement variables).
Number of active transport edges (i.e. nonzero transportation variables).
Some of these have not been included yet, so we expect you to formulate the variables/post-processing as needed. We advise you to design an efficient method to report the results of these objectives, since we will rely on these repeatedly.

2.1
Please solve the nominal cost-minimizing problem that satisfies nutritional needs fully, and report the results with respect to variables defined in Performance Assessment. Furthermore, comment on the food mix, as well as nutrients per person. (Optional: try turning off the diet constraints and see how the rations change.)

2.2
Unfortunately, in reality we only have $6000 dollars for the day, to be able to satisfy as much demand as possible. Come up with a way to change the problem so that you can satisfy the budget constraints and feed as many people as possible. (Hint: use your slack variable.) Explain your method and and the changes to your model. Report your results with respect to variables in Performance Assessment. How does our strategy with limited resources change relatively to our strategy with unlimited resources?

2.3
We would like to protect against uncertainty in commodity costs. The international commodity prices (i.e. cost of goods bought in international nodes ∈ ND) are independent, normally distributed with a standard deviation equal to 5% of the nominal price. The price of a commodity in a regional or local node is also normally distributed around the nominal price, but is positively correlated to the prices of other commodities in that node. The cost perturbation is as follows, for commodity c in local/regional node n:

∆(Costn,c) = 0.35Costn,czn,c + 0.05 X Costn,kzn,k

k∈commodities in n\c

where z is the uncertain variable in the ellipsoidal uncertainty set. Please come up with your P matrix (hint: it’s square), model this with a joint ellipsoidal uncertainty set, and report your formulation here. Provide a method to compute the safety factor of your uncertainty set for a given probabilistic guarantee between 1 and 0.5. Provide intuition about why the uncertainty may be correlated.

2.4
Solve the robust problem above over a range of safety factors that protect against [50, 75, 85, 90, 92, 95, 96, 97, 98, 99]% of uncertain outcomes. We encourage you to formulate this RO problem in JuMP using the robust counterpart instead of using JuMPeR, to aid your understanding. But either method is sufficient.

Tabulate the metrics from Performance Assessment for all safety factors and evaluate the results. How does our procurement and transportation strategy evolve as we protect against more uncertainty? How might practical considerations affect your choice of uncertainty protection?

(Note: Please relax the required equality constraints to be able to use the robust counterpart, and watch out for numerical precision of your solution.)

2.5
Let’s assume again that we have unlimited cash. Solve the robust cost-minimizing robust problem, and generate the Performance Assessment matrix. What do the results imply about how we should apply our procurement and transportation policies when the uncertainty is realized (i.e. when prices do not match what we expect)? A qualitative answer is sufficient, but please provide reasoning using the above data and the optimization formulation.

2.6
Please include your robust optimization code. (No need to include data processing and solver printouts.)