Faculty Digital Archive

Archive@NYU >
Stern School of Business >
IOMS: Operations Management Working Papers >

Please use this identifier to cite or link to this item: http://hdl.handle.net/2451/27726

Title: A Column Generation Algorithm for Choice-Based Network Revenue Management
Authors: Bront, Juan Jose Miranda
Keywords: choice behavior
multinomial logit
capacity control
hyperbolic programming
integer programming
Issue Date: 13-Oct-2008
Series/Report no.: OM-2007-06
Abstract: In the last few years, there has been a trend to enrich traditional revenue management models built upon the independent demand paradigm by accounting for customer choice behavior. This extension involves both modeling and computational challenges. One way to describe choice behavior is to assume that each customer belongs to a segment, which is characterized by a consideration set, i.e., a subset of the products provided by the firm that a customer views as options. Customers choose a particular product according to a multinomial-logit criterion, a model widely used in the marketing literature. In this paper, we consider the choice-based, deterministic, linear programming model (CDLP) of Gallego et al. [6], and the follow-up dynamic programming (DP) decomposition heuristic of van Ryzin and Liu [16], and focus on the more general version of these models, where customers belong to overlapping segments. To solve the CDLP for real-size networks, we need to develop a column generation algorithm. We prove that the associated column generation subproblem is indeed NP-Complete, and propose a simple, greedy heuristic to overcome the complexity of an exact algorithm. Our computational results show that the heuristic is quite effective, and that the overall approach has good practical potential and leads to high quality solutions.
URI: http://hdl.handle.net/2451/27726
Appears in Collections:IOMS: Operations Management Working Papers

Files in This Item:

File Description SizeFormat
OM-2007-6.pdf363.46 kBAdobe PDFView/Open

Items in Faculty Digital Archive are protected by copyright, with all rights reserved, unless otherwise indicated.


The contents of the FDA may be subject to copyright, be offered under a Creative Commons license, or be in the public domain.
Please check items for rights statements. For information about NYU’s copyright policy, see http://www.nyu.edu/footer/copyright-and-fair-use.html 
Valid XHTML 1.0 | CSS