A Dynamic Disaggregation Approach to Approximate Linear Programs for Network Revenue Management

• 成果类型: Article
• 署名作者: Vossen, Thomas W. M.; Zhang, Dan
• 署名单位: University of Colorado System; University of Colorado Boulder
• 刊物名称: PRODUCTION AND OPERATIONS MANAGEMENT
• ISSN/ISSBN: 1059-1478
• DOI: 10.1111/poms.12239
• 发表日期: 2015
• 页码: 469-487
• 关键词: customer-choice behavior; bid prices; iterative aggregation; MODEL

摘要

The linear programming approach to approximate dynamic programming has received considerable attention in the recent network revenue management (RM) literature. A major challenge of the approach lies in solving the resulting approximate linear programs (ALPs), which often have a huge number of constraints and/or variables. Starting from a recently developed compact affine ALP for network RM, we develop a novel dynamic disaggregation algorithm to solve the problem, which combines column and constraint generation and exploits the structure of the underlying problem. We show that the formulation can be further tightened by considering structural properties satisfied by an optimal solution. We prove that the sum of dynamic bid-prices across resources is concave over time. We also give a counterexample to demonstrate that the dynamic bid-prices of individual resources are not concave in general. Numerical experiments demonstrate that dynamic disaggregation is often orders of magnitude faster than existing algorithms in the literature for problem instances with and without choice. In addition, adding the concavity constraints can further speed up the algorithm, often by an order of magnitude, for problem instances with choice.