Tornar a Working Papers

Paper #1303

A tractable consideration set structure for network revenue management
Arne Strauss i Kalyan Talluri
Febrer 2012 (Revisió: Octubre 2012)
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.
Paraules clau:
discrete-choice models, network revenue management, consideration sets
Codis JEL:
C61, L93, L83, M11
Àrea de Recerca:
Gestió de la Producció i de les Operacions

Descarregar el paper en format PDF (176 Kb)

Cercar Working Papers

Per data:
-cal seleccionar un valor a les quatre llistes desplegables-

Consultes Predefinides