Handling Other Constraints

Sometimes project-selection models have other constraints. For example, suppose that if we select Project 3, we must also select Project 4. Because our current optimal solution selects Project 3 but not Project 4, we know that our current solution can’t remain optimal. To solve this problem, simply add the constraint that the binary changing cell for Project 3 is less than or equal to the binary changing cell for Project 4.

You can find this example on the If 3 then 4 worksheet in the file Capbudget.xlsx, which is shown in Figure 30-4. Cell L9 refers to the binary value related to Project 3, and cell L12 to the binary value related to Project 4. By adding the constraint L9<=L12, if we choose Project 3, L9 equals 1 and our constraint forces L12 (the Project 4 binary) to equal 1. Our constraint must also leave the binary value in the changing cell of Project 4 unrestricted if we do not select Project 3. If we do not select Project 3, L9 equals 0 and our constraint allows the Project 4 binary to equal 0 or 1, which is what we want. The new optimal solution is shown in Figure 30-4.

Figure 30-4: New optimal solution for if not Project 3 then Project 4

A new optimal solution is calculated if selecting Project 3 means we must also select Project 4. Now suppose that we can do only four projects from among Projects 1 through 10. (See the At Most 4 Of P1–P10 worksheet, shown in Figure 30-5.) In cell L8, we compute the sum of the binary values associated with Projects 1 through 10 with the formula SUM(A6:A15). Then we add the constraint L8<=L10, which ensures that, at most, 4 of the first 10 projects are selected. The new optimal solution is shown in Figure 30-5. The NPV has dropped to $9.014 billion.

Figure 30-5: Optimal solution when we can select only 4 of 10 projects

Solving Binary and Integer Programming Problems

Linear Solver models in which some or all changing cells are required to be binary or integer are usually harder to solve than linear models in which all changing cells are allowed to be fractions. For this reason, we often are satisfied with a near-optimal solution to a binary or integer programming problem. If your Solver model runs for a long time, you may want to consider adjusting the Tolerance setting in the Solver Options dialog box. (See Figure 30-6.) For example, a Tolerance setting of 0.5% means that Solver will stop the first time it finds a feasible solution that is within 0.5 percent of the theoretical optimal target cell value (the theoretical optimal target cell value is the optimal target value found when the binary and integer constraints are omitted). Often we are faced with a choice between finding an answer within 10 percent of optimal in 10 minutes or finding an optimal solution in two weeks of computer time! The default Tolerance value is 0.05%, which means that Solver stops when it finds a Target cell value within 0.05 percent of the theoretical optimal target cell value.

Figure 30-6: Adjusting the Tolerance option