Allocating railroad maintenance funds by solving binary knapsack problems with precedence constraints

The United States is faced with allocating funds from a limited budget to the repair or replacement of railroad track segments on military bases. The problem can be modeled as a very large binary knapsack problem having a single budget constraint and multiple precedence constraints. A procedure has been developed to convert this original problem into an equivalent knapsack problem with a single constraint and significantly fewer variables. The new knapsack problem, still too large to be solved optimally, is then solved efficiently by a heuristic which provides answers within a few percent of optimality. Furthermore, the quality of the solution improves with the size of the problem.