Implicit Enumeration Algorithm with Binary-Valued Constraints

摘要

In many capital budgeting problems, the basic decisions simply are whether to approve or reject various capital investment proposals. This naturally gives rise to binary decision variables and an integer programming formulation of the problem. In fact, this type of problem is one of the most important areas of application of integer programming. General-purpose algorithms for binary integer programming frequently are applied to capital budgeting problems. However, such problems generally have a great deal of special structure, including contraints for mutually exclusive alternatives, contingent alternatives, and other interdependencies. (A project which can be undertaken at different discrete levels is a good example for mutually exclusive alternatives and a simple kind of contingent alternative concerns two-stage projects, where the second stage can be undertaken only if its first stage couterpart has been undertaken already. A similar relationship also can exist between two groups of mutually exclusive alternatives.) Many group contingent constraints, which are common in capital budgeting problems and scheduling problems, are binary valued. A capital budgeting model is presented. Keywords: Linear programming.