Asymptotically optimal heuristics for network Revenue Management

We consider a network Revenue Management (RM) problem with multiple products and resources. Prices are assumed to be fixed. The objective is to design a dynamic resource allocation control in order to maximize expected revenue. As it is, the problem is computationally intractable and so the literature documents many attempts to develop near-optimal heuristics. Recently there has been some interests in studying the performance of heuristics constructed using the solutions of the so-called Deterministic Linear Program (DLP) formulation of the original RM problem. The appeal is obvious - an LP is easy to solve, and the formulation also lends itself to many intuitive interpretations. The drawback, however, is also obvious - the LP formulation only takes into account first-order information (i.e. expected value of future demand) and ignores the rest. A way to partly overcome this issue is by re-optimizing the control several times throughout the selling horizon. But how good is such approach?;We show that the benefit of re-optimization depends largely on the specific of heuristics being used. That is, different LP-based heuristics may have very different performance under frequent re-optimization. Our main result: there exists an LP-based heuristic that has O(1) expected loss under sufficiently frequent re-optimization. That is, the loss of this heuristic is independent of the size of the problem. We also extend the result to a more general case with customer choice.