Table 1 provides the net annual returns from the investment opportunities expressed in millions of dollars. A ninth opportunity, not shown in the table, is available for funds left over from the first eight investments. The return is 5% per year for the amount invested, or equivalently, $0.5 million for each $10 million invested. The manager's goal is to maximize the total annual return without exceeding the budget.
The investment problem has a general mathematical programming formulation.
The notation is the general model is defined below.
The problem as stated is similar in structure to the knapsack problem but the objective function is nonlinear. To formulate it as a mixed-integer linear program it would be necessary to introduce 32 binary variables, one for each nonzero level of investment. Since the budget and investment amounts are integer the slack variable, y, can be treated as integer. Rather than pursuing the MILP formulation we will use the problem as an introduction to dynamic programming.
