Dynamic Basis Function Generation for Network Revenue Management

This paper introduces the heuristic two-phase incremental algorithm (H-2PIAlg), an approximate dynamic programming algorithm for network revenue management (NRM). Unlike existing NRM techniques that rely on a fixed set of basis functions to approximate the value function, H-2PIAlg iteratively refines this set by dynamically generating and adding basis functions. These functions are optimized by extending to the NRM context the flow imbalance ideas developed for a deterministic setting. H-2PIAlg integrates this approach with known row generation techniques and monotonicity properties. To make H-2PIAlg practical, we take the known affine approximation as a starting point and use exponential ridge basis functions to refine it. Our computational study on two sets of benchmark instances from the literature demonstrates that H-2PIAlg with these specifications produces significantly better upper bounds and policies than the affine approximation. H-2PIAlg also achieves superior upper bounds and policies compared with other NRM benchmark methods in instances with scarce capacity. These improvements come at a substantial computational cost. However, H-2PIAlg can solve large instances that cause some NRM benchmarks to run out of memory. History: Accepted by Nicola Secomandi, Area Editor for Stochastic Models & Reinforcement Learning. Funding: D. Adelman is grateful for financial support from the Booth School of Business, University of Chicago. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0418 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0418 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .