Choice network revenue management based on new tractable approximations

Abstract

The choice network revenue management model incorporates customer purchase behavior as probability of purchase as a function of the offered products, and is appropriate for air- line and hotel network revenue management, dynamic sales of bundles, and dynamic assort- ment optimization. The optimization problem is a stochastic dynamic program and is in- tractable. Consequently, a linear programming approximation called choice deterministic linear program ( CDLP ) is usually used to generate controls. Tighter approximations such as affine and piecewise-linear relaxations have been proposed, but it was not known if they can be solved efficiently even for simple models such as the multinomial logit (MNL) model with a single segment. We first show that the affine relaxation (and hence the piecewise-linear relaxation) is NP-hard even for a single-segment MNL choice model. By analyzing the affine relaxation we derive a new linear programming approximation that admits a compact representation, implying tractability, and prove that its value falls between the CDLP valueandtheaffinerelaxation value. This is the first tractable relaxation for the choice network revenue management problem that is provably tighter than CDLP . This approximation in turn leads to new policies that, in our numerical experiments, show very good promise: a 2% increase in revenue on average over CDLP ; and the values typically coming very close to the affine relaxation. We extend our analysis to obtain other tractable approximations that yield even tighter bounds. We also give extensions to the case with multiple customer segments with overlapping consideration sets where choice by each segment is according to the MNL model.