Not logged in.

Quick Search - Contribution

Contribution Details

Type Journal Article
Scope Discipline-based scholarship
Title Efficient compact linear programs for network revenue management
Organization Unit
Authors
  • Simon Laumer
Item Subtype Original Work
Refereed Yes
Status Published in final form
Language
  • English
Journal Title Optimization Letters
Publisher Springer
Geographical Reach international
ISSN 1862-4472
Volume 17
Number 2
Page Range 437 - 451
Date 2023
Abstract Text We are concerned with computing bid prices in network revenue management using approximate linear programming. It is well-known that affine value function approximations yield bid prices which are not sensitive to remaining capacity. The analytic reduction to compact linear programs allows the efficient computation of such bid prices. On the other hand, capacity-dependent bid prices can be obtained using separable piecewise linear value function approximations. Even though compact linear programs have been derived for this case also, they are still computationally much more expensive compared to using affine functions. We propose compact linear programs requiring substantially smaller computing times while, simultaneously, significantly improving the performance of capacity-independent bid prices. This simplification is achieved by taking into account remaining capacity only if it becomes scarce. Although our proposed linear programs are relaxations of the unreduced approximate linear programs, we conjecture equivalence and provide according numerical support. We measure the quality of an approximation by the difference between the expected performance of an induced policy and the corresponding theoretical upper bound. Using this paradigm in numerical experiments, we demonstrate the competitiveness of our proposed linear programs.
Free access at DOI
Digital Object Identifier 10.1007/s11590-022-01945-y
Other Identification Number merlin-id:22856
PDF File Download from ZORA
Export BibTeX
EP3 XML (ZORA)