{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:38:58Z","timestamp":1740145138781,"version":"3.37.3"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,10,22]],"date-time":"2022-10-22T00:00:00Z","timestamp":1666396800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,10,22]],"date-time":"2022-10-22T00:00:00Z","timestamp":1666396800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006447","name":"University of Zurich","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006447","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2023,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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.<\/jats:p>","DOI":"10.1007\/s11590-022-01945-y","type":"journal-article","created":{"date-parts":[[2022,10,22]],"date-time":"2022-10-22T02:02:57Z","timestamp":1666404177000},"page":"437-451","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient compact linear programs for network revenue management"],"prefix":"10.1007","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8859-459X","authenticated-orcid":false,"given":"Simon","family":"Laumer","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,22]]},"reference":[{"issue":"4","key":"1945_CR1","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1287\/opre.1060.0368","volume":"55","author":"D Adelman","year":"2007","unstructured":"Adelman, D.: Dynamic bid prices in revenue management. Oper. Res. 55(4), 647\u2013661 (2007)","journal-title":"Oper. Res."},{"issue":"3","key":"1945_CR2","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1287\/moor.1040.0094","volume":"29","author":"DP de Farias","year":"2004","unstructured":"de Farias, D.P., Van Roy, B.: On constraint sampling in the linear programming approach to approximate dynamic programming. Math. Oper. Res. 29(3), 462\u2013478 (2004)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"1945_CR3","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1057\/rpm.2009.53","volume":"10","author":"A Erdelyi","year":"2011","unstructured":"Erdelyi, A., Topaloglu, H.: Using decomposition methods to solve pricing problems in network revenue management. J. Revenue Pricing Manag. 10(4), 325\u2013343 (2011)","journal-title":"J. Revenue Pricing Manag."},{"issue":"11","key":"1945_CR4","doi-asserted-by":"publisher","first-page":"2719","DOI":"10.1111\/poms.13075","volume":"28","author":"J Ke","year":"2019","unstructured":"Ke, J., Zhang, D., Zheng, H.: An approximate dynamic programming approach to dynamic pricing for network revenue management. Prod. Oper. Manag. 28(11), 2719\u20132737 (2019)","journal-title":"Prod. Oper. Manag."},{"issue":"1","key":"1945_CR5","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1287\/opre.2015.1453","volume":"64","author":"S Kunnumkal","year":"2016","unstructured":"Kunnumkal, S., Talluri, K.: A note on relaxations of choice network revenue management dynamic program. Oper. Res. 64(1), 158\u2013166 (2016)","journal-title":"Oper. Res."},{"issue":"1","key":"1945_CR6","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1287\/moor.2015.0716","volume":"41","author":"S Kunnumkal","year":"2016","unstructured":"Kunnumkal, S., Talluri, K.: On a piecewise-linear approximation for network revenue management. Math. Oper. Res. 41(1), 72\u201391 (2016)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"1945_CR7","doi-asserted-by":"publisher","first-page":"1544","DOI":"10.1287\/mnsc.2019.3289","volume":"66","author":"Q Lin","year":"2019","unstructured":"Lin, Q., Nadarajah, S., Soheili, N.: Revisiting approximate linear programming: Constraint-violation learning with applicatins to inventory control and energy storage. Manag. Sci. 66(4), 1544\u20131562 (2019)","journal-title":"Manag. Sci."},{"issue":"2","key":"1945_CR8","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1016\/j.ejor.2011.06.033","volume":"216","author":"J Meissner","year":"2012","unstructured":"Meissner, J., Strauss, A.K.: Network revenue management with inventory-sensitive bid prices and customer choice. Eur. J. Oper. Res. 216(2), 459\u2013468 (2012)","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"1945_CR9","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1016\/0022-247X(85)90317-8","volume":"110","author":"PJ Schweitzer","year":"1985","unstructured":"Schweitzer, P.J., Seidmann, A.: Generalized polynomial approximations in Markovian decision processes. J. Math. Anal. Appl. 110(2), 568\u2013582 (1985)","journal-title":"J. Math. Anal. Appl."},{"issue":"1","key":"1945_CR10","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1287\/mnsc.1030.0147","volume":"50","author":"K Talluri","year":"2004","unstructured":"Talluri, K., van Ryzin, G.J.: Revenue management under a general discrete choice model of consumer behavior. Manag. Sci. 50(1), 15\u201333 (2004)","journal-title":"Manag. Sci."},{"key":"1945_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/b139000","volume-title":"The Theory and Practice of Revenue Management","author":"K Talluri","year":"2004","unstructured":"Talluri, K., van Ryzin, G.J.: The Theory and Practice of Revenue Management. Kluwer Academic Publishers, Norwell, MA (2004)"},{"issue":"1","key":"1945_CR12","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1287\/ijoc.2013.0551","volume":"26","author":"C Tong","year":"2014","unstructured":"Tong, C., Topaloglu, H.: On the approximate linear programming approach for network revenue management problems. INFORMS J. Comput. 26(1), 121\u2013134 (2014)","journal-title":"INFORMS J. Comput."},{"issue":"3","key":"1945_CR13","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1287\/opre.1080.0597","volume":"57","author":"H Topaloglu","year":"2009","unstructured":"Topaloglu, H.: Using Lagrangian relaxation to compute capacity-dependent bid prices in network revenue management. Oper. Res. 57(3), 637\u2013649 (2009)","journal-title":"Oper. Res."},{"issue":"6","key":"1945_CR14","doi-asserted-by":"publisher","first-page":"1352","DOI":"10.1287\/opre.2015.1442","volume":"63","author":"TWM Vossen","year":"2015","unstructured":"Vossen, T.W.M., Zhang, D.: Reductions of approximate linear programs for network revenue management. Oper. Res. 63(6), 1352\u20131371 (2015)","journal-title":"Oper. Res."},{"issue":"3","key":"1945_CR15","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1111\/poms.12239","volume":"24","author":"TWM Vossen","year":"2015","unstructured":"Vossen, T.W.M., Zhang, D.: A dynamic disaggregation approach to approximate linear programs for network revenue management. Prod. Oper. Manag. 24(3), 469\u2013487 (2015)","journal-title":"Prod. Oper. Manag."},{"key":"1945_CR16","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1057\/rpm.2009.38","volume":"9","author":"D Walczak","year":"2010","unstructured":"Walczak, D., Mardan, S., Kallesen, R.: Customer choice, fare adjustments and the marginal expected revenue data transformation: A note on using old yield management techniques in the brave new world of pricing. J. Revenue Pricing Manag. 9, 94\u2013109 (2010)","journal-title":"J. Revenue Pricing Manag."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01945-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-022-01945-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01945-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,9]],"date-time":"2023-02-09T23:07:26Z","timestamp":1675984046000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-022-01945-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,22]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["1945"],"URL":"https:\/\/doi.org\/10.1007\/s11590-022-01945-y","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2022,10,22]]},"assertion":[{"value":"17 June 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 October 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author declares that he has no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}