The Capital Budgeting Problem (CapBud)

of Section 11.2 over a set of n proposed projects j using decision variables xj = 1 if project j is chosen and = 0 otherwise can be formulated as follows:

max a n

j = 1rjxj ( maximize total return)

s.t. a n

j = 1at, j xj … bt for all t ( budget limits in times t)

xj … xk for all j, k  P (project pairs subject to precedence)

xj + xk … 1 for all j, k  M (mutually exclusive project pairs)

xj binary j = 1,

c, n

(a) Develop and justify an expression for the length of a binary encoding for an instance in terms of the dimensions and parameters of the model.

(b) State the threshold version 1CapBudÚ2 of the problem for given threshold v, and establish that it belongs to complexity class NP.

(c) The threshold version 1BKPÚ2 of the Binary Knapsack Problem discussed in Exercise 14-2 above is known to be NPComplete.

Use that fact along with part

(b) to establish that 1CapBudÚ2 is also NP-Complete. Be sure to fully detail the required reduction among instances of the two problems.

(d) Explain what the result of

(c) implies for the prospects of finding a polynomial time (binary encoding) algorithm for either 1CapBudÚ2 or the full optimization version (CapBud), and why.