An Analysis of the Control-Algorithm Re-solving Issue in Inventory and Revenue Management

摘要

While inventory- and revenue-management problems can be represented as Markov decision process (MDP) models, in some cases the well-known dynamic-programming curse of dimensionality makes it computationally prohibitive to solve them exactly. An alternative solution, called here the control-algorithm approach, is to use a math program (MP) to approximately represent the MDP and use its optimal solution to heuristically instantiate the parameters of the decision rules of a given set of control policies. As new information is observed over time, the control algorithm can incorporate it by re-solving the MP and revising the parameters of the decision rules with the newly obtained solution. The re-solving issue arises when one reflects on the consequences of this revision: Does the performance of the control algorithm really improve by revising its decision-rule instantiation with the solution of the re-solved MP, or should an appropriate modification of the prior solution be used? This paper analyzes the control-algorithm re-solving issue for a class of finite-horizon inventory- and revenue-management problems. It establishes sufficient conditions under which re-solving does not deteriorate the performance of a control algorithm, and it applies these results to control algorithms for network revenue management and multiproduct make-to-order production with lost sales and positive lead time.