A Tractable Consideration Set Structure for Network Revenue Management

• Authors: Arne Strauss and Kalyan Talluri.
• BSE Working Paper: 606 | September 15
• Keywords: network revenue management , discrete-choice models , consideration sets
• JEL codes: C61, L93, L83, M11

The dynamic program for choice network RM is intractable and approximated by a deterministic linear program called the CDLP. When the segment consideration sets overlap, the CDLP is difficult to solve. A weaker formulation (SDCP+) is tractable and approximates the CDLP value very closely. We show that if the segment consideration sets follow a tree structure, the two problems are equivalent, and give a counterexample to show that cycles can induce a gap between CDLP and the relaxation.