Approximate Linear Programming in Network Revenue Management with Multiple Modes

David Sayah ()
Additional contact information
David Sayah: Johannes Gutenberg University Mainz

No 1518, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz

Abstract: Approximate linear programming has been applied to network revenue management problems under the fundamental modeling assumption that products de?ne combinations of one resource bundle and a fare class. We consider products that can have multiple operational modes allowing companies to select the way they want to serve the purchaser of a multi-mode product. We show that the presence of multi-mode products implies a weaker relation between an a?ne approximate linear program (ALP) and a compact reformulation, known as reduction. Consequently, the upper bound on the maximum expected revenue obtained via the reduction is not necessarily as tight as the upper bound produced via the ALP. We further demonstrate that the gap between these two formulations is bounded in general and zero in a particular class of instances, when multi-mode products are ?exible products. For general instances, we exploit a set-packing structure within the reduction in order to improve the upper bound, i.e., we introduce a cutting plane method that strengthens the reduction by separating valid inequalities. Our computational tests indicate that it is possible to halve the gap in not more than 4% of the time needed to solve the ALP via column generation.

Keywords: affine approximation; network revenue management; multiple operational modes; transportation networks (search for similar items in EconPapers)
Pages: 32 pages
Date: 2015-11-08
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1518.pdf First version, 2015 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:jgu:wpaper:1518

Access Statistics for this paper

More papers in Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz Contact information at EDIRC.
Bibliographic data for series maintained by Research Unit IPP ().