Decision-Stage Method: Convergence Proof, Special Application, and Computation Experience

This paper presents a new method for obtaining exact optimal solutions for a class of discrete-variable non-linear resource-allocation problems. The new method is called the decision-state method because, unlike the conventional dynamic programming method which works only in the state space, the new method works in the state space and the decision space. It generates and retains only a fraction of the points in the state space at which the state functions are discontinuous; and thus overcomes to some extent the curse of dimensionality. It carries the cumulative decision-strongs associated with these points, and thus avoids the backtracking entailed by the conventional dynamic programming method for recovering the optimal decisions. A concise and complete statement of the method is given in Algorithm 2 and it is proved that the algorithm finds all exact optimal solutions. In addition the method is adapted for solving some problems with special structures such as block-angular or split-block-angular constraints and the resultant substantial advantages are demonstrated. The performance of Algorithm 2 on many resource-allocations problems is reported, along with investigations on many tactical decisions which have substantial impact on the performance. The performance of the computer implementation of Algorithm 2 is compared with that of the MMDP algorithm and it showed that for the class of problems at which the two are aimed, the decision-state Algorithm 2 performed better than MMDP algorithm both in terms of storage requirement and solution time. In fact, it achieved an order of magnitude saving in storage requirement.