Problem $3($Multi$-$Period Knapsack problem$)$

$($a$)$ Consider the following multi$-$period capital budgeting problem. An investor is consid$-$

ering $8$ independent investment projects. Each project requires full participation, no partial

participation is allowed. If selected, a project may require cash contributions yearly over

the next $3$ years, as in the following table. There is an external fixed amount of $$1,000,000$

available for these investments in each of the following $3$ years. Each investment project is

expected to have a net return as shown in Table $1.$ The investor needs to determine the sub$-$

set of projects to invest in$,$ so as to maximize the total expected net returns. For simplicity,

assume that:

Table $1$: All figures in $$10,000\text{'}$s of dollars

$($a$)$ Assume that unutilized funds are not carried forward to the next period and are not

available for investments. Model the problem as a binary program and use either Python or

Excel to solve it$.$

Hint: Introduce $8$ binary variables and consider $3$ constraints $($knapsacks$).$

$($b$)$Assume that unutilized funds can be carried forward to the next period and are

available for cash out$-$flows. Formulate the problem as an integer program, and use either

Python or Excel to solve it$.$ Compare your solution to the one from $3($a$).$

Hint: Introduce additionally $3$ auxiliary variables $y_1,y_2,y_3,$ corresponding to unutilized funds

in years $1,2,3$ respectively. Then the available funds for period $1$ are $$1,000,000.$ The avail$-$

able funds for period $2$ are $$1,000,000+y_1.$ The available funds for period $3$ are $$1,000,000$

$+y_2.$ Apply ideas from multi$-$period models to capture the cash$-$flow dynamics.