A Strong Lagrangian Relaxation for General Discrete Choice Network Revenue Management

Published Papers
Kunnumkal, Sumit M., Talluri, Kalyan. (Forthcoming) "A Strong Lagrangian Relaxation for General Discrete Choice Network Revenue Management", Computational Optimization and Applications
The choice network revenue management (RM) model incorporates customer purchase behavior as customers purchasing products with certain probabilities that are a function of the offered assortment of products, and is the appropriate model for airline and hotel network revenue management, dynamic sales of bundles, and dynamic assortment optimization. The underlying stochastic dynamic program is intractable and even its certainty-equivalence approximation, in the form of a linear program called Choice Deterministic Linear Program ($CDLP$) is difficult to solve in most cases. The separation problem for $CDLP$ is NP-complete for MNL with just two segments when their consideration sets overlap. The affine approximation of the dynamic program is NP-complete for even a single-segment MNL. This is in contrast to the independent-class or perfect-segmentation case where even the piecewise-linear approximation has been shown to be tractable. In this paper we investigate the piecewise-linear approximation for network RM under a general discrete-choice model of demand. Furthermore, we show that the piecewise-linear approximation is polynomially-time solvable for a fixed consideration set size, solvable in fact as a linear program. Small consideration sets are a reasonable modeling tradeoff in many practical applications. Our solution relies on showing that for any discrete-choice model the separation problem for the linear program of the piecewise-linear approximation can be solved exactly by a Lagrangian relaxation. We give modeling extensions and show by numerical experiments the improvements from using piecewise-linear approximation functions.