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.