A Column Generation Algorithm for Choice-Based Network Revenue Management
The DOI matches its Crossref record; 30 of the 30 references it cites were found in a registry or an index.
Abstract
During the past 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. (2004) [Gallego, G., G. Iyengar, R. Phillips, A. Dubey. 2004. Managing flexible products on a network. Technical Report CORC TR-2004-01, Department of Industrial Engineering and Operations Research, Columbia University, New York], and the follow-up dynamic programming decomposition heuristic of van Ryzin and Liu (2008) [van Ryzin, G. J., Q. Liu. 2008. On the choice-based linear programming model for network revenue management. Manufacturing Service Oper. Management 10(2) 288–310]. We 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-hard 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 leads to high-quality, practical solutions.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
Discrete Choice Methods with Simulation
Train, K. E. (2001) · doi:10.1017/cbo9780511805271 · Cited by 7,784
Mixed MNL models for discrete response
McFadden, D., & Train, K. (2000) · Journal of Applied Econometrics · doi:10.1002/1099-1255(200009/10)15:5<447::aid-jae570>3.0.co;2-1 · Cited by 4,322
Discrete Choice Methods with Simulation
Train, K. E. (2003) · Cambridge University Press eBooks · doi:10.1017/cbo9780511753930 · Cited by 3,890
The Theory and Practice of Revenue Management
Talluri, K. T., & Van Ryzin, G. J. (2004) · International Series in Operations Research & Management Science · doi:10.1007/b139000 · Cited by 2,243
Approximate Dynamic Programming: Solving the Curses of Dimensionality
Powell, W. B. (2007) · Wiley Series in Probability and Statistics · doi:10.1002/9780470182963 · Cited by 1,566
Revenue Management Under a General Discrete Choice Model of Consumer Behavior
Talluri, K., & van Ryzin, G. (2004) · Management Science · doi:10.1287/mnsc.1030.0147 · Cited by 1,108
Boolean Methods in Operations Research and Related Areas
Hammer, P. L., & Rudeanu, S. (1968) · Ökonometrie und Unternehmensforschung / Econometrics and Operations Research · doi:10.1007/978-3-642-85823-9 · Cited by 529
Assortment Planning: Review of Literature and Industry Practice
Kök, A. G., Fisher, M. L., & Vaidyanathan, R. (2008) · International Series in Operations Research & Management Science · doi:10.1007/978-0-387-78902-6_6 · Cited by 413
On the Choice-Based Linear Programming Model for Network Revenue Management
Liu, Q., & van Ryzin, G. (2008) · Manufacturing & Service Operations Management · doi:10.1287/msom.1070.0169 · Cited by 366
Models and Heuristics for Product Line Selection
Green, P. E., & Krieger, A. Μ. (1985) · Marketing Science · doi:10.1287/mksc.4.1.1 · Cited by 328
Positioning and Pricing a Product Line
Dobson, G., & Kalish, S. (1988) · Marketing Science · doi:10.1287/mksc.7.2.107 · Cited by 274
An Approximate Dynamic Programming Approach to Network Revenue Management with Customer Choice
Zhang, D., & Adelman, D. (2009) · Transportation Science · doi:10.1287/trsc.1090.0262 · Cited by 226
Measuring the societal impacts of automobile downsizing
Cardell, N. S., & Dunbar, F. C. (1980) · Transportation Research Part A: General · doi:10.1016/0191-2607(80)90060-6 · Cited by 224
Revenue Management for Parallel Flights with Customer-Choice Behavior
Zhang, D., & Cooper, W. L. (2005) · Operations Research · doi:10.1287/opre.1050.0194 · Cited by 205
Managing Flexible Products on a Network
Gallego, G., Iyengar, G., Phillips, R., & Dubey, A. (2004) · SSRN Electronic Journal · doi:10.2139/ssrn.3567371 · Cited by 200
Models of the Spiral-Down Effect in Revenue Management
Cooper, W. L., Homem-de-Mello, T., & Kleywegt, A. J. (2006) · Operations Research · doi:10.1287/opre.1060.0304 · Cited by 191
OM Practice—Choice-Based Revenue Management: An Empirical Study of Estimation and Optimization
Vulcano, G., van Ryzin, G., & Chaar, W. (2010) · Manufacturing & Service Operations Management · doi:10.1287/msom.1090.0275 · Cited by 185
Self-citationAn Integer Programming Approach to the Optimal Product Line Selection Problem
McBride, R. D., & Zufryden, F. S. (1988) · Marketing Science · doi:10.1287/mksc.7.2.126 · Cited by 179
Optimizing Multinomial Logit Profit Functions
Hanson, W., & Martin, K. (1996) · Management Science · doi:10.1287/mnsc.42.7.992 · Cited by 177
Airline network seat inventory control : methodologies and revenue impacts
Williamson, E. L. (1992) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 171
Asymptotic Behavior of an Allocation Policy for Revenue Management
Cooper, W. L. (2002) · Operations Research · doi:10.1287/opre.50.4.720.2855 · Cited by 168
Chen, K. D., & Hausman, W. H. (2000) · Management Science · doi:10.1287/mnsc.46.2.327.11931 · Cited by 165
A note on a global approach for general 0–1 fractional programming
Wu, T. (1997) · European Journal of Operational Research · doi:10.1016/s0377-2217(96)00258-5 · Cited by 120
Computing Virtual Nesting Controls for Network Revenue Management Under Customer Choice Behavior
Ryzin, G. J. V., & Vulcano, G. J. (2008) · Manufacturing & Service Operations Management · doi:10.1287/msom.1070.0210 · Cited by 109
Self-citationBoyd, E. A., & Kallesen, R. (2004) · Journal of Revenue and Pricing Management · doi:10.1057/palgrave.rpm.5170104 · Cited by 91
Future of Revenue Management: Models of demand
Ryzin, G. J. V. (2005) · Journal of Revenue and Pricing Management · doi:10.1057/palgrave.rpm.5170140 · Cited by 75
Passenger Choice Analysis for Seat Capacity Control: A Pilot Project in Scandinavian Airlines
Andersson, S. E. (1998) · International Transactions in Operational Research · doi:10.1111/j.1475-3995.1998.tb00130.x · Cited by 70
An Analysis of the Control-Algorithm Re-solving Issue in Inventory and Revenue Management
Secomandi, N. (2008) · Manufacturing & Service Operations Management · doi:10.1287/msom.1070.0184 · Cited by 50
On complexity of unconstrained hyperbolic 0–1 programming problems
Prokopyev, O. A., Huang, H.-X., & Pardalos, P. M. (2004) · Operations Research Letters · doi:10.1016/j.orl.2004.05.011 · Cited by 42
Cited by
Assortment Planning: Review of Literature and Industry Practice
Kök, A. G., Fisher, M. L., & Vaidyanathan, R. (2008) · International Series in Operations Research & Management Science · doi:10.1007/978-0-387-78902-6_6 · Cited by 413
Assortment Optimization Under Variants of the Nested Logit Model
Davis, J. M., Gallego, G., & Topaloglu, H. (2014) · Operations Research · doi:10.1287/opre.2014.1256 · Cited by 295
Assortment Optimization under the Multinomial Logit Model with Random Choice Parameters
Rusmevichientong, P., Shmoys, D., Tong, C., & Topaloglu, H. (2014) · Production and Operations Management · doi:10.1111/poms.12191 · Cited by 279
Mapping the Ethicality of Algorithmic Pricing: A Review of Dynamic and Personalized Pricing
Seele, P., Dierksmeier, C., Hofstetter, R., & Schultz, M. D. (2021) · Journal of Business Ethics · doi:10.1007/s10551-019-04371-w · Cited by 196
Unconstraining methods in revenue management systems: research overview and prospects
Guo, P., Xiao, B., & Li, J. (2012) · Advances in Operations Research · doi:10.1155/2012/270910 · Cited by 40
Metadata
- Authors
- Bront, J. J. M., Méndez-Díaz, I., & Vulcano, G.
- Venue
- Operations Research
- Published
- 2009-06
- Volume
- 57
- Issue
- 3
- Pages
- 769-784
- ISSN
- 0030-364X (ISSN-L)
- 1526-5463
- OpenAlex
- W2067581912
- Cited by
- 310
- References
- 30
- FWCI
- 23.21
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.