Given the computational difficulties associated with solving the model presented in Exercise 11,…

 Given the computational difficulties associated with solving the model presented in Exercise 11, A. S. Manne conceived of a way to approximate the mixed-integer programming model as a linear program. This transformation is based on defining for each item j a series of production sequences over the planning horizon T . Each sequence is a set of T nonnegative integers that identify the amount to be produced of item j at each time period t during the planning horizon, in such a way that demand requirements for the item are met. It is enough to consider production sequences such that, at a given time period, the production is either zero or the sum of consecutive demands for some number of periods into the future. This limits the number of production sequences to a total of 2T−1 for each item. Let

                x jkt = amount to be produced of item j in period t by means of production sequence k.

To illustrate how the production sequences are constructed, assume that T = 3. Then the total number of production sequences for item j is 23−1 = 4. The corresponding sequences are given in Table.

The total cost associated with sequence k for the production of item j is given by

and the corresponding man-hours required for this sequence in period t is

verify that, if the model presented in Exercise 11 is restricted to producing each item in production sequences, then it can be formulated as follows:

b) Study the structure of the resulting model. How could you define the structure? For T = 12 and J = 10,000, how many rows and columns does the model have?

c) Under what conditions can we eliminate the integrality constraints imposed on variables θ jk without significantly affecting the validity of the model? [Hint. Read the comment made on the multi-term scheduling problem in Section 12.1 of the text.]

 d) Propose a decomposition approach to solve the resulting large-scale linear-programming model. What advantages and disadvantages are offered by this approach? (Assume that at this point the resulting subproblems are easy to solve. See Exercise 13 for details.)