New Compact Linear Programming Formulations for Choice Network Revenue Management

We consider the network RM problem with customer choice, which incorporates customer purchase behavior as a function of the offered products. The optimization problem is a stochastic dynamic program and is intractable. A certainty-equivalence relaxation of the dynamic program, called the choice deterministic linear program (CDLP) is usually used to generate dynamic controls. It is known CDLP has a compact formulation for the multinomial-logit (MNL) model of customer choice. Our objective is to obtain a tighter bound than CDLP while retaining the appealing properties of a compact linear programming representation. To this end, it is natural to consider the affine relaxation of the dynamic program. We first show that the affine relaxation is NP-complete even for a single-segment MNL model. Nevertheless, by analyzing the affine relaxation we derive new linear programs that approximate the dynamic programming value function better than CDLP, provably between the CDLP value and the affine relaxation. We give a bound on the gap between these tractable relaxations and the (NP-hard) affine relaxation. This bound pinpoints the range of capacities where improvements are possible. We give extensions to the case with multiple customer segments and nested-logit model of choice. Finally we perform extensive numerical comparisons on the various bounds to evaluate their peformance (joint work with K. Talluri).