Not logged in.

Contribution Details

Type Journal Article
Scope Discipline-based scholarship
Title Reductions of non-separable approximate linear programs for network revenue management
Organization Unit
  • Simon Laumer
  • Christiane Barz
Item Subtype Original Work
Refereed Yes
Status Published in final form
  • English
Journal Title European Journal of Operational Research
Publisher Elsevier
Geographical Reach international
ISSN 0377-2217
Volume 309
Number 1
Page Range 252 - 270
Date 2023
Abstract Text We suggest a novel choice of non-separable basis functions for an approximate linear programming approach to the well-known network revenue management problem. Considering non-separability is particularly important when interdependencies between resources are large. Such a situation can be illustrated for example by a bus line, where different origin-destination pairs have many overlapping segments. Traditional separable approximation approaches tend to ignore the resulting interactions. We suggest to group resources into non-separable subnetworks. For each chosen subnetwork, basis functions either span the whole function space or consist of linear functions. Given this more general choice of basis functions, we extend existing reductions of approximate linear programs. If there is only one subnetwork, for which the basis functions span the whole function space, we prove the equivalence to a compact linear program of polynomial size. For the general case, we suggest an approximate reduction. Numerical examples illustrate our novel upper bounds for the maximum expected revenue and the corresponding competitive policies. In particular, we find that the added benefit of non-separability heavily depends on the network structure and the capacity. Our work helps to better understand the impact of assuming separability in network revenue management. The polynomial sized reductions make it possible to estimate the added average revenue resulting from incorporating interactions between resources. The theory we develop demonstrates how the interpretation of dual variables as state-action probabilities can be applied to reduce exponentially large approximate linear programs via variable aggregation.
Free access at DOI
Digital Object Identifier 10.1016/j.ejor.2023.01.006
Other Identification Number merlin-id:23349
PDF File Download from ZORA
Export BibTeX
Keywords Revenue management, Approximate dynamic programming, Network revenue management, Reductions, Non-separability