Decision-Stage Method: Convergence Proof, Special Application, and Computation Experience / Vinay Dharmadhikari.

By:

Dharmadhikari, Vinay

Contributor(s):

National Bureau of Economic Research

Material type: Text

TextSeries: Working Paper Series (National Bureau of Economic Research) ; no. w0094.Publication details: Cambridge, Mass. National Bureau of Economic Research 1975.Description: 1 online resource: illustrations (black and white)Online resources:

Available additional physical forms:

Hardcopy version available to institutional subscribers

Abstract: 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.

Tags from this library: No tags from this library for this title. Log in to add tags.

Average rating: 0.0 (0 votes)

Holdings
Item type	Home library	Collection	Call number	Status	Date due	Barcode	Item holds
Working Paper	Biblioteca Digital	Colección NBER	nber w0094 (Browse shelf(Opens below))	Not For Loan

Total holds: 0

Collection: Colección NBER Close shelf browser (Hides shelf browser)

Previous	No cover image available	No cover image available	No cover image available	No cover image available	No cover image available	No cover image available	No cover image available	Next
Previous	nber w0091 Autoregressive Spectrum Estimation Technique Allied to Quarterly Consumer Durables Expenditure Data /	nber w0092 Schooling as a Wage Depressant /	nber w0093 Rational Expectations and the Dynamic Structure of Macroeconomic Models: A Critical Review /	nber w0094 Decision-Stage Method: Convergence Proof, Special Application, and Computation Experience /	nber w0095 Qualitative Information, Reputation, and Monopolistic Competition /	nber w0096 Specification Errors in Limited Dependent Variable Models /	nber w0097 Human Wealth and Human Capital /	Next

July 1975.

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.