P6.

A corporation is considering four projects that are expected to improve the long-term profitability of the company. Each project can be accepted for funding next year or rejected (Partial funding is not possible.) A total of $2.1 million is available for the funding of these projects. The table below provides the funding needing for each proposal and the scores that represent the estimated NPV (in $100M) for each project.

a) Formulate a zero-one linear optimization model to decide what projects to accept to maximize the total score within the available budget.

b) Solve the linear programming relaxation to this problem. Provide both the solution vector and the solution value and, by simple rounding, find a feasible integer solution to this problem. Indicate the difference between the upper and lower bounds.

c) Find the optimal solution by performing branch-and-bound for this knapsack problem and justify that it is the global optimum.

PROJECT	A	B	C	D
Value	3	3	1	2
Cost (in $K)	600	800	600	600