A tractable consideration set structure for network revenue management

Arne Strauss and Kalyan Talluri ()

Economics Working Papers from Department of Economics and Business, Universitat Pompeu Fabra

Abstract: Models incorporating more realistic models of customer behavior, as customers choosing from an offer set, have recently become popular in assortment optimization and revenue management. The dynamic program for these models is intractable and approximated by a deterministic linear program called the CDLP which has an exponential number of columns. When there are products that are being considered for purchase by more than one customer segment, CDLP is difficult to solve since column generation is known to be NP-hard. However, recent research indicates that a formulation based on segments with cuts imposing consistency (SDCP+) is tractable and approximates the CDLP value very closely. In this paper we investigate the structure of the consideration sets that make the two formulations exactly equal. We show that if the segment consideration sets follow a tree structure, CDLP = SDCP+. We give a counterexample to show that cycles can induce a gap between the CDLP and the SDCP+ relaxation. We derive two classes of valid inequalities called flow and synchronization inequalities to further improve (SDCP+), based on cycles in the consideration set structure. We give a numeric study showing the performance of these cycle-based cuts.

Keywords: discrete-choice models; network revenue management; consideration sets (search for similar items in EconPapers)
JEL-codes: C61 L83 L93 M11 (search for similar items in EconPapers)
Date: 2012-02, Revised 2012-10
New Economics Papers: this item is included in nep-dcm
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
https://econ-papers.upf.edu/papers/1303.pdf Whole Paper (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:upf:upfgen:1303

Access Statistics for this paper

More papers in Economics Working Papers from Department of Economics and Business, Universitat Pompeu Fabra
Bibliographic data for series maintained by ( this e-mail address is bad, please contact ).