Problem 3 (Multi-Period Knapsack problem) (a) Consider the following multi-period capital budgeting problem. An investor is considering 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 subset of projects to invest in, so as to maximize the total expected net returns. For simplicity, assume that: - Unutilized funds are not carried forward to the next period and are not available for investments. - Cash flows are not discounted for the time value of money (we could consider discounting of cash flows, but the problem becomes considerably more difficult to formulate). Table 1: All figures in $10,000 's of dollars Formulate the problem as an integer programming problem, and use either MATLAB or Excel to solve it. Hint: Introduce 8 binary variables and consider 3 constraints (knapsacks). (b) Consider the same setting as in Problem 2(a), but relax the first assumption, i.e., unused funds can be carried forward to the next period and are available for cash outflows. Formulate the problem as an integer programming problem, and use either MATLAB or Excel to solve it. Compare your solution to the one from Problem 2(a). Hint: Introduce additionally 3 auxiliary variables y1,y2,y3, corresponding to unutilized funds in years 1,2,3 respectively. Then the available funds for period 1 are $1,000,000. The available funds for period 2 are $1,000,000+y1. The available funds for period 3 are $1,000,000+y2. Apply ideas from the multi-period models to capture the cash-flow dynamics