Technical Note—Product-Based Approximate Linear Programs for Network Revenue Management

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.