A tractable consideration set structure for network revenue management

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.