Write down a dual formulation of this linear program -

Question

PROBLEM 1

Consider Example 1 with a second-stage program defined as:

min 2y₁ + y₂

s.t. y₁ + 2y₂ ≥ ξ₁ - x₁,

y₁ + 2y₂ ≥ ξ₂ - x₁ - x₂, 0 ≤ y₁ ≤ 1, 0 ≤ y₂ ≤ 1

Example 1 is on pages 105-106 and states:

"Using the upper bounds on y, the first constraint implies ξ₁ - x₁ ≤ 3 and the second one implies ξ₂ - x₁ - x₂ ≤ 2. Thus K₂(ξ) = { x|x₁ ≥ ξ₁ - 3, x₁ + x₂ ≥ ξ₂ - 2}. As ξ is discrete, we may easily define the second-stage feasibility set

K2 = ?ξ∈K₂(ξ)

In Example 1, if ξ₁ takes the value 2, 3, 4 and ξ₂ the values 1, 4, 7 with some nonspecified probabilities, independently of each other or not, K₂ = {x|x₁ ≥ 1, x₁ + x₂ ≥ 5}. In fact, it suffices here to know the componentwise maximum of ξ to obtain K₂. This set is a polyhedron.
Define posW = {t|W_y = t, y ≥ 0}. It is called the positive hull of W. It represents the set of right- hand sides that can be obtained by a non-negative combination of the columns of W. The positive hull is easily seen to be a convex cone."

PROBLEM 2

Consider Example 2 where the second-stage program is defined as:

min 2y₁ + y₂

s.t. y₁ + y₂ ≥ 1 - x₁,

y₁ ≥ ξ - x₁ - x₂,

y₁, y₂ ≥ 0

where Ξ ⊂R+

So, we have seen that K₂(ξ) = { x|x₁ ≥ ξ₁ - 3, x₁ + x₂ ≥ ξ₂ - 2}

Let ξ₁ and ξ₂ be two independent continuous random variables. Assume they both have uniform density over [2,4].

(a) What is K₂^P?

(b) What is K₂?

(c) Let u_i* be defined as in (1.7). What are u_i* and u_i* in this example?

Here is the Example 2 found on pages 107-108 in the Birge textbook and states:

" Consider the following second-stage program:

min 2y₁ + y₂
s.t. y₁ + y₂ ≥ 1 - x₁,

y₁ ≥ ξ - x₁ - x₂,
y₁ , y₂ ≥ 0

To reduce the calculations, assume 0 ≤ x1 ≤ 1, 0 ≤ x₂ ≤ 1. The optimal second-stage solutions are as follows:

i. If ξ ≤ x₁ + x₂ ---> y₁ = 0, y₂ = 1 - x₁ ;

ii. If ξ > x₁ + x₂ ---> y₁ = ξ - x₁ - x₂ and y₂ = (1 - ξ + x₂)⁺ where a+ = max(a,0).

This results in three situations (as 1 - ξ + x₂ may be positive or negative). Setting the second-stage decisions into the second-stage objective, one obtains the following three pieces for Q(x, ξ):

 Thus Q(x, ξ) is clearly piecewise linear in x. "

PROBLEM 3:

Consider Example 4 in Section 3.2b. Instead of putting a limit on the total purchase of wheat and corn, the farmer does not want either purchase to be over 10 T. Thus, (2.17) is replaced by:

P(y1(ω) ≤ 10, y2(ω) ≤ 10) ≥ 0.80.

Show how to reformulated the recourse problem with K scenarios and this extra probabilistic constraint as a MILP with K extra binary variables and 2K + 1 extra constraints.

Here is the Example 4 in Section 3.2 found on pages 132-133 in Birge textbook:

"Consider the farmer in Section 1.1. The example was built assuming a discrete random variable with only three scenarios: good, fair and bad. This number can easily be extended either in a similar manner or by taking past observations of the yields. We now assume K scenarios, each consisting of a vector of three yields.

The farmer finds it inappropriate to purchase large quantities of wheat and/or corn. He considers it excessive to purchase more than a total of 20T. Owing the uncertainty of mother nature, he allows for a 20% probability of excessive purchases. Thus, his probabilistic constraint is:

P(y₁(ω) ≤ 10, y₂(ω) ≤ 10) ≥ 0.80

where y₁(ω) and y₂(ω) are the purchases of wheat and corn, respectively.

Here is a case where the probabilistic constraint depends on the recourse actions under the general form g(x,y(ω), ξ(ω)) = h(ω) - T(ω)x - W(ω)y(ω).

To obtain (constraint 2.14 on pg 131) g(x, y_k, ξ_k) ≤ uk wk , we start from the representation of the constraint under scenario k as -20 + y₁^k + y₂^k ≤ 0 where y₁^k + y₂^k  represent the purchase of wheat and corn under scenario k. From Table 1 in Section 1.1, the total requirement of wheat and corn is 440. The upperbound to form g(x, y_k, ξ_k) ≤ u_k wk is the value 420, so that a single constraint of the form:

y₁^k + y₂^k ≤ 20 + 420 Wk is created.

The recourse problem with K scenarios and the extra probabilistic constraint

P(y₁(ω) ≤ 10, y₂(ω) ≤ 10) ≥ 0.80

Is reformulated as an MILP with K extra binary variables and K + 1 extra constraints."

PROBLEM 4:

Consider the standard two-stage linear stochastic formulation

min c^Tx + E[Q(x, ξ)]              (1)

s.t. Ax = b,x ≥ 0                   (2)

where Q(x, ξ is the optimal value of the second stage

min q^Ty                               (3)

s.t. T_x +W_y = h,y> 0             (4)

Show that the following conditions are equivalent:

(a) problem (1-4) has complete recourse

(b) the feasible set of the dual problem Π(q) = {W^TΠ ≤ q} is bounded for every cost function vector q.

(c) the system W^TΠ ≤ 0 has only one solution Π = 0.

Problem 5 - Using the L Shaped Method:

Consider a Belgian company Volsay, which specializes in producing ammoniac gas (NH₃), which requires 1 unit of nitrogen and 3 units of hydrogen, and ammonium chloride (NH₄Cl), which requires 1 unit of nitrogen, 4 units of hydrogen and 1 unit of chlorine. The company makes a profit of 40 Euros for each sale of an ammoniac gas unit and 50 Euros for each sale of an ammonium chloride unit. Volsay would like to order materials (nitrogen, hydrogen and chlorine) to guarantee the best average production costs (profit from manufacturing and material salvage minus the costs of materials). Furthermore, assume that the demand for ammoiac gas is distributed as gamma random variable with shape=10 and scale=2, and the demand for ammonium chloride is distributed as gamma random variable with shape=20 and scale=3.

Assume that a unit of nitrogen costs 10 euros, a unit of hydrogen costs 1 euro, and a unit of chlorine also costs 1 euro. The salvage cost of a unit of nitrogen is 0, the salvage cost of hydrogen 0.1, and the salvage cost of chlorine is 0.1.

Consider a scenario based formulation of this problem. Let pk denote a probability of scenario k, the amount of material m required for production of a unit of product p is A(p,m), K is a total number of scenarios, zk[p] is a production level of product p in scenario k, dk[p] is a demand for product p in scenario k, yk[m] is a remaining material m in scenario k, q[p] is a profit from product p, s[m] is a salvage cost for material m, c[m] is a cost of ordering a unit of material m, x[m] is an amount of material m ordered (first stage variables).

min c^Tx + _k=1Σ^k Pk[-q^Tz^k -S^Ty^k]

S.t. y^k = x - A^T z^k, k = 1, . . . , K

0 ≤ Z^k ≤ d^k , y^k ≥ 0, x ≥ 0

1. Write down a dual formulation of this linear program.

2. Describe how the dual formulation can be used to obtain a feasibility cut in the L-shaped method.

3. Describe how the dual formulation can be used to obtain an optimality cut in the L-shaped method.

4. Implement a single-cut version of the L-shaped method for this problem using a template available on the black board. Solve the problem for 100,1000 and 10000 scenarios and summarize the computational results.

5. Implement a multi-cut version of the L-shaped method. Solve the problem for 100, 1000 and 10000 scenarios and compare the computational results to the single cut L-shaped algorithm.

6. Compute the Jensen Lower Bound for E[Q(x, ξ )], where x[nitrogen] = 86, x[hydrogen] = 325 and x[chlorine] = 71:5. How can you improve this bound?