Question

A company is considering 5 proposals for investment. The table below displays each proposal's net present value (NPV) in millions of dollars and each proposal's requirements for cash (in millions of dollars) for each of the next three years.

                                                     Cash Requirements

Proposal        NPV           Year 1          Year 2                Year 3

     1                12.8              4.40               3.30                   3.50

     2                10.5              4.30               2.50                   2.10

     3                 9.4              4.10               3.40                   1.50

     4               11.7              4.70               3.90                   3.10

     5               10.2              5.00               3.40             0.75

           

The manager wants to maximize the total NPV while meeting the following restrictions:

(i) The total cash requirement cannot exceed 14.2 million dollars in the first year.

(ii) The total cash requirement cannot exceed 12.8 million dollars in the second year.

(iii) The total cash requirement cannot exceed 10 million dollars in the third year.

(iii) At most three of the proposals can be approved.

(iv) If proposal 1 is approved then proposal 3 must also be approved.

Formulate a capital budgeting integer programming problem for this situation by defining

(a) The decision variables.

(b) The objective function. What does it represent?

(c) All the constraints. What does each constraint represent?

Answer 1

Integer programming model

(a) Decision variables: Xi be a binary variable such that Xi = 1, if proposal i is approved, otherwise Xi = 0 if proposal i is not approved.

(b) Objective function: Max 12.8X1+10.5X2+9.4X3+11.7X4+10.2X5

(c) Constraints are following. The condition, which each constraint represents is written in front of it.  

4.4X1+4.3X2+4.1X3+4.7X4+5.0X5 <= 14.2 (i) The total cash requirement cannot exceed 14.2 million dollars in the first year.

3.3X1+2.5X2+3.4X3+3.9X4+3.4X5 <= 12.8 (ii) The total cash requirement cannot exceed 12.8 million dollars in the second year.

3.5X1+2.1X2+1.5X3+3.1X4+0.75X5 <= 10 (iii) The total cash requirement cannot exceed 10 million dollars in the third year.

X1+X2+X3+X4+X5 <= 3 (iv) At most three of the proposals can be approved.

X3-X1 >= 0 (v) If proposal 1 is approved then proposal 3 must also be approved.

Xi {0,1} binary variable constraint