ºÚÁÏÉçÇøÍø

Zhang, Rui; Samiedaluie, Saied; Zhang, Dan. Technical Note—Product-Based Approximate Linear Programs for Network Revenue Management. Operations Research. Sep/Oct2022, Vol. 70 Issue 5, p2837-2850.ÌýÌýÌýÌý

A Novel and Promising Approximation for Network Revenue Management In "Product-Based Approximate Linear Programs for Network Revenue Management," Zhang, Samiedaluie, and Zhang propose a novel separable piecewise linear (SPL) approximation for the network revenue management problem. The coefficients of the proposed SPL approximation can be interpreted as each product's revenue contribution to the value of each resource in a given period, which provides more granular information compared with the existing resource-based SPL approximation in the literature. The new approximation provides more flexibility for policy construction. Furthermore, the new approximation opens the opportunity to derive a set of valid inequalities to further improve the computational performance and achieve additional gains in the expected revenue. Computational experiments with instances of various network structures and parameters demonstrate its efficacy: the new approximation leads to bid-price policies generating higher expected revenues and demonstrates better performance in terms of both computational efficiency and numerical stability. The approximate linear programming approach has received significant attention in the network revenue management literature. A popular approximation in the existing literature is separable piecewise linear (SPL) approximation, which estimates the value of each unit of each resource over time. SPL approximation can be used to construct resource-based bid-price policies. In this paper, we propose a product-based SPL approximation. The coefficients of the product-based SPL approximation can be interpreted as each product's revenue contribution to the value of each unit of each resource in a given period. We show that the resulting approximate linear program admits compact reformulations, such as its resource-based counterpart. Furthermore, the new approximation allows us to derive a set of valid inequalities to (i) speed up the computation and (ii) select optimal solutions to construct more effective policies. We conduct an extensive numerical study to illustrate our results. In a set of 192 problem instances, bid-price policies based on the new approximation generate higher expected revenues than resource-based bid-price policies with an average revenue lift of 0.72% and a maximum revenue lift of 5.3%. In addition, the new approximation can be solved 1.42 times faster than the resource-based approximation and shows better numerical stability. The valid inequalities derived from the new approximation further improve the computational performance and are critical for achieving additional gains in the expected revenue. The policy performance is competitive compared with the dynamic programming decomposition method, which is the strongest heuristic known in the literature.ÌýÌýÌýÌý

Ìý