A column generation algorithm for choice-based network revenue management

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 assum...

Descripción completa

Detalles Bibliográficos
Autores principales: Méndez Díaz, Isabel, Vulcano, Gustavo José
Publicado: 2009
Materias:
Analysis of algorithms: computational complexity
Linear applications
Marketing: choice models
Programming: fractional
Columbia University
Column generation
Computational challenges
Computational results
Customer choice
Exact algorithms
Flexible products
General version
Greedy heuristics
High quality
Linear programming models
Manufacturing service
Multinomials
New York
NP-hard
Phillips
Practical solutions
Real-size networks
Revenue management
Algorithms
Computational complexity
Customer satisfaction
Dynamic programming
Heuristic algorithms
Heuristic methods
Linearization
Management
Sales
Systems engineering
Wireless telecommunication systems
Network management
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0030364X_v57_n3_p769_Bront
http://hdl.handle.net/20.500.12110/paper_0030364X_v57_n3_p769_Bront
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_0030364X_v57_n3_p769_Bront
record_format dspace
spelling paper:paper_0030364X_v57_n3_p769_Bront2023-06-08T14:55:43Z A column generation algorithm for choice-based network revenue management Méndez Díaz, Isabel Vulcano, Gustavo José Analysis of algorithms: computational complexity Linear applications Marketing: choice models Programming: fractional Analysis of algorithms: computational complexity Columbia University Column generation Computational challenges Computational results Customer choice Exact algorithms Flexible products General version Greedy heuristics High quality Linear applications Linear programming models Manufacturing service Multinomials New York NP-hard Phillips Practical solutions Programming: fractional Real-size networks Revenue management Algorithms Computational complexity Customer satisfaction Dynamic programming Heuristic algorithms Heuristic methods Linearization Management Sales Systems engineering Wireless telecommunication systems Network management 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. ©2009 INFORMS. Fil:Méndez-Díaz, I. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Vulcano, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2009 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0030364X_v57_n3_p769_Bront http://hdl.handle.net/20.500.12110/paper_0030364X_v57_n3_p769_Bront
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Analysis of algorithms: computational complexity
Linear applications
Marketing: choice models
Programming: fractional
Analysis of algorithms: computational complexity
Columbia University
Column generation
Computational challenges
Computational results
Customer choice
Exact algorithms
Flexible products
General version
Greedy heuristics
High quality
Linear applications
Linear programming models
Manufacturing service
Multinomials
New York
NP-hard
Phillips
Practical solutions
Programming: fractional
Real-size networks
Revenue management
Algorithms
Computational complexity
Customer satisfaction
Dynamic programming
Heuristic algorithms
Heuristic methods
Linearization
Management
Sales
Systems engineering
Wireless telecommunication systems
Network management
spellingShingle Analysis of algorithms: computational complexity
Linear applications
Marketing: choice models
Programming: fractional
Analysis of algorithms: computational complexity
Columbia University
Column generation
Computational challenges
Computational results
Customer choice
Exact algorithms
Flexible products
General version
Greedy heuristics
High quality
Linear applications
Linear programming models
Manufacturing service
Multinomials
New York
NP-hard
Phillips
Practical solutions
Programming: fractional
Real-size networks
Revenue management
Algorithms
Computational complexity
Customer satisfaction
Dynamic programming
Heuristic algorithms
Heuristic methods
Linearization
Management
Sales
Systems engineering
Wireless telecommunication systems
Network management
Méndez Díaz, Isabel
Vulcano, Gustavo José
A column generation algorithm for choice-based network revenue management
topic_facet Analysis of algorithms: computational complexity
Linear applications
Marketing: choice models
Programming: fractional
Analysis of algorithms: computational complexity
Columbia University
Column generation
Computational challenges
Computational results
Customer choice
Exact algorithms
Flexible products
General version
Greedy heuristics
High quality
Linear applications
Linear programming models
Manufacturing service
Multinomials
New York
NP-hard
Phillips
Practical solutions
Programming: fractional
Real-size networks
Revenue management
Algorithms
Computational complexity
Customer satisfaction
Dynamic programming
Heuristic algorithms
Heuristic methods
Linearization
Management
Sales
Systems engineering
Wireless telecommunication systems
Network management
description 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. ©2009 INFORMS.
author Méndez Díaz, Isabel
Vulcano, Gustavo José
author_facet Méndez Díaz, Isabel
Vulcano, Gustavo José
author_sort Méndez Díaz, Isabel
title A column generation algorithm for choice-based network revenue management
title_short A column generation algorithm for choice-based network revenue management
title_full A column generation algorithm for choice-based network revenue management
title_fullStr A column generation algorithm for choice-based network revenue management
title_full_unstemmed A column generation algorithm for choice-based network revenue management
title_sort column generation algorithm for choice-based network revenue management
publishDate 2009
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0030364X_v57_n3_p769_Bront
http://hdl.handle.net/20.500.12110/paper_0030364X_v57_n3_p769_Bront
work_keys_str_mv AT mendezdiazisabel acolumngenerationalgorithmforchoicebasednetworkrevenuemanagement
AT vulcanogustavojose acolumngenerationalgorithmforchoicebasednetworkrevenuemanagement
AT mendezdiazisabel columngenerationalgorithmforchoicebasednetworkrevenuemanagement
AT vulcanogustavojose columngenerationalgorithmforchoicebasednetworkrevenuemanagement
_version_ 1768543645119545344

Ejemplares similares