A Constrained Capital Budgeting Problem with Applications to Repair Kit Selection

We consider a capital budgeting problem in which each potential project requires the performance of a known set of activities. In general, these sets of activities are not mutually exclusive. However, when a particular activity is common to the requirements of multiple projects, a single performance of the activity simultaneously satisfies the requirements of the multiple projects. Associated with the performance of each activity are two quantities: a known fixed cost and a consumption of a known amount of a scarce resource. Because the sets of activities required by the projects are not mutually exclusive, we cannot apportion an activity's fixed cost or resource consumption to a single project. In this paper, we formulate this capital budgeting problem (and a slight variant) as a maximal network flow problem with a side constraint, and we report computational experience using Lagrangian relaxation to find an optimal solution. We also discuss an application to the selection of parts and tools to include in a field repair kit used to fix a variety of types of breakdowns.