[Question 1] The total marks available for this question is 34. The weighting of each subpart is indicated in %.

CBU International is interested in building new detached houses in three areas of Coventry. To start building new houses the company must first redevelop the area, which incurs significant investments as shown in the table below. After the redevelopment of an area is completed, a number of houses can be built in that area. The construction costs per house and the maximum number of houses in each area are also shown below.

The total budget for area redevelopment and building new houses is £5 million. The company does not have to build houses in all three areas. However, if an area is used, the number of houses built in it must be at least 5.

(a)  Formulate an integer linear programming (ILP) model aiming to maximize the total number of

houses built. Do not solve the model.

[30%]

(b)  Modify the model in part (a) to incorporate the following condition: houses in area 3 cannot be

built if the number of houses built in area 2 is 20 or more.

[20%]

(c)   Ignore  parts  (a)  and  (b). An  integer  linear  program  was  solved  using  the  branch-and-bound algorithm, in which the corresponding linear program (LP) relaxation problems were solved by the simplex-method. The seven printouts on page 5 below show the optimal solutions to all these LPs. Unfortunately, the  printouts  are  in  disorder.  It  is  known that  six variables were  used  in the formulation, of which X1, X2 and X3 were integer, and Y1, Y2 and Y3 binary. The objective function was maximized. It is also known that branching was performed only on binary variables Y1, Y2 and Y3, and not on X1, X2 and X3.

Draw the tree representing the solution process, incorporating the printouts shown and indicating the additional constraints added to the model at different stages.

Is the assumption that the model was completely solved consistent with the solution tree?

What  is  the  maximum  value  of  the  objective  function  in  the  original  ILP  problem?  Provide explanations for each of your answers.

[50%]

[Question 2] The total marks available for this question is 33. The weighting of each subpart is indicated in %.

A  company’s  production  process  depends  on  a  supply  of  a  special  component.  Demand for the component is shown in the table below:

The company can order units at the beginning of each month. Orders are delivered immediately. It costs £60 to place an order, no matter how many units are ordered. However, it costs £30 to store a

unit for one month in a warehouse. Assume the company has no unit in store at the very beginning. (a)  Use dynamic programming (DP) to define an ordering policy with the minimal total cost.

Solve the DP and provide all the details.

How many stages are there in the DP formulation?

What are the state variables at each stage?

What is the total cost?

What is the optimal ordering policy?

[60%]

(b)  Now consider a general case. Suppose that the company knows the demands for T months, which

are d1, d2, … , dT . It costs £a to place an order regardless of order quantity and £b to keep one unit in store for a month.

Formulate dynamic programming recursions to find an optimal ordering strategy for this general case.

[40%]