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.