How many constraints and decision variables does the sub

Question

As a follow-up to Exercises 5 and 6, once the sub problems have been solved, the rays generated are added to the restricted master:

a) Describe how the columns of the restricted master are computed.

b) Why are weighting constraints not needed for the restricted master in this particular application?

c) What is the stopping rule for this variation of the decomposition algorithm?

d) Suppose that storage limitations force you to drop some of the non-basic columns from the restricted master at some iteration. Is it possible that the algorithm will be unable to find the overall optimal solution as a result?

Exercise 5

Consider the sub problems generated by the decomposition approach. Formulate the sub problem corresponding to buying a 20-year U.S. Government security at the beginning of the first period of a model consisting of 3 one-year periods. The generic decision variables to use are as follows:

b₁, S₂₁(e₂), S₃₁(e₃), h₃₁(e₃).

(Do not include buying a similar security at the beginning of the second or third periods.)

a) How many constraints and decision variables does the sub problem have?

b) The constraints of the sub problems are homogeneous (i.e., zero right hand sides). Suppose that purchasing 1 unit of this security, b₁ = 1, gives a positive rate of return. What can be said about purchasing λb₁ units of this security?

c) Formulate a dynamic-programmig model to solve this sub problem, assuming that b₁ = 1. Show that this solution determines a ray of the sub problem.

Exercise 6

Suppose that, for the sub problems formulated in Exercise 5, we define a ray-finding sub problem as follows: b₁ is set equal to 1 and moved to the right hand side; the resulting sub problem is solved by linear programming.

a) Formulate the ray-finding problem.
b) Find the dual of the ray-finding problem.
c) Show that a basis for the dual problem is triangular.
d) Write down a recursive method for calculating the optimal solution of the dual of the ray-finding problem. [Hint. Exploit the triangular property of the basis to solve for the dual variables by back-substitution.]
e) How is the solution of the primal ray-finding problem determined from the solution of the dual?