IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v62y2014i4p876-890.html
   My bibliography  Save this article

A Dynamic Near-Optimal Algorithm for Online Linear Programming

Author

Listed:
  • Shipra Agrawal

    (Microsoft Research India, Bangalore, India)

  • Zizhuo Wang

    (Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, Minnesota 55455)

  • Yinyu Ye

    (Department of Management Science and Engineering, Stanford University, Stanford, California 94305)

Abstract

A natural optimization model that formulates many online resource allocation problems is the online linear programming (LP) problem in which the constraint matrix is revealed column by column along with the corresponding objective coefficient. In such a model, a decision variable has to be set each time a column is revealed without observing the future inputs, and the goal is to maximize the overall objective function. In this paper, we propose a near-optimal algorithm for this general class of online problems under the assumptions of random order of arrival and some mild conditions on the size of the LP right-hand-side input. Specifically, our learning-based algorithm works by dynamically updating a threshold price vector at geometric time intervals, where the dual prices learned from the revealed columns in the previous period are used to determine the sequential decisions in the current period. Through dynamic learning, the competitiveness of our algorithm improves over the past study of the same problem. We also present a worst case example showing that the performance of our algorithm is near optimal.

Suggested Citation

  • Shipra Agrawal & Zizhuo Wang & Yinyu Ye, 2014. "A Dynamic Near-Optimal Algorithm for Online Linear Programming," Operations Research, INFORMS, vol. 62(4), pages 876-890, August.
    • Handle: RePEc:inm:oropre:v:62:y:2014:i:4:p:876-890
    DOI: 10.1287/opre.2014.1289
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2014.1289
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2014.1289?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. William L. Cooper, 2002. "Asymptotic Behavior of an Allocation Policy for Revenue Management," Operations Research, INFORMS, vol. 50(4), pages 720-727, August.
    2. Guillermo Gallego & Garrett van Ryzin, 1994. "Optimal Dynamic Pricing of Inventories with Stochastic Demand over Finite Horizons," Management Science, INFORMS, vol. 40(8), pages 999-1020, August.
    3. Kalyan Talluri & Garrett van Ryzin, 1998. "An Analysis of Bid-Price Controls for Network Revenue Management," Management Science, INFORMS, vol. 44(11-Part-1), pages 1577-1593, November.
    4. Marco Molinaro & R. Ravi, 2014. "The Geometry of Online Packing Linear Programs," Mathematics of Operations Research, INFORMS, vol. 39(1), pages 46-59, February.
    5. Wedad Elmaghraby & P{i}nar Keskinocak, 2003. "Dynamic Pricing in the Presence of Inventory Considerations: Research Overview, Current Practices, and Future Directions," Management Science, INFORMS, vol. 49(10), pages 1287-1309, October.
    6. Guillermo Gallego & Garrett van Ryzin, 1997. "A Multiproduct Dynamic Pricing Problem and Its Applications to Network Yield Management," Operations Research, INFORMS, vol. 45(1), pages 24-41, February.
    7. Gabriel Bitran & René Caldentey, 2003. "An Overview of Pricing Models for Revenue Management," Manufacturing & Service Operations Management, INFORMS, vol. 5(3), pages 203-229, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Dan Zhang & Larry Weatherford, 2017. "Dynamic Pricing for Network Revenue Management: A New Approach and Application in the Hotel Industry," INFORMS Journal on Computing, INFORMS, vol. 29(1), pages 18-35, February.
    2. Dan Zhang & Zhaosong Lu, 2013. "Assessing the Value of Dynamic Pricing in Network Revenue Management," INFORMS Journal on Computing, INFORMS, vol. 25(1), pages 102-115, February.
    3. Omar Besbes & Assaf Zeevi, 2012. "Blind Network Revenue Management," Operations Research, INFORMS, vol. 60(6), pages 1537-1550, December.
    4. Stefanus Jasin, 2014. "Reoptimization and Self-Adjusting Price Control for Network Revenue Management," Operations Research, INFORMS, vol. 62(5), pages 1168-1178, October.
    5. Yongbo Xiao, 2018. "Dynamic pricing and replenishment: Optimality, bounds, and asymptotics," Naval Research Logistics (NRL), John Wiley & Sons, vol. 65(1), pages 3-25, February.
    6. Muzaffer Buyruk & Ertan Güner, 2022. "Personalization in airline revenue management: an overview and future outlook," Journal of Revenue and Pricing Management, Palgrave Macmillan, vol. 21(2), pages 129-139, April.
    7. Constantinos Maglaras & Joern Meissner, 2003. "Dynamic Pricing Strategies for Multi-Product Revenue Management Problems," Working Papers MRG/0002, Department of Management Science, Lancaster University, revised Nov 2005.
    8. William L. Cooper & Tito Homem-de-Mello, 2007. "Some Decomposition Methods for Revenue Management," Transportation Science, INFORMS, vol. 41(3), pages 332-353, August.
    9. Dasci, A. & Karakul, M., 2009. "Two-period dynamic versus fixed-ratio pricing in a capacity constrained duopoly," European Journal of Operational Research, Elsevier, vol. 197(3), pages 945-968, September.
    10. Lingxiu Dong & Panos Kouvelis & Zhongjun Tian, 2009. "Dynamic Pricing and Inventory Control of Substitute Products," Manufacturing & Service Operations Management, INFORMS, vol. 11(2), pages 317-339, December.
    11. Alex Gershkov & Benny Moldovanu, 2009. "Dynamic Revenue Maximization with Heterogeneous Objects: A Mechanism Design Approach," American Economic Journal: Microeconomics, American Economic Association, vol. 1(2), pages 168-198, August.
    12. Huseyin Topaloglu & S. Ilker Birbil & J. B. G. Frenk & Nilay Noyan, 2012. "Tractable Open Loop Policies for Joint Overbooking and Capacity Control Over a Single Flight Leg with Multiple Fare Classes," Transportation Science, INFORMS, vol. 46(4), pages 460-481, November.
    13. moldovanu, benny & Gershkov, Alex, 2007. "The Dynamic Assignment of Heterogenous Objects: A Mechanism Design Approach," CEPR Discussion Papers 6439, C.E.P.R. Discussion Papers.
    14. Constantinos Maglaras & Joern Meissner, 2006. "Dynamic Pricing Strategies for Multiproduct Revenue Management Problems," Manufacturing & Service Operations Management, INFORMS, vol. 8(2), pages 136-148, July.
    15. Ningyuan Chen & Guillermo Gallego, 2019. "Welfare Analysis of Dynamic Pricing," Management Science, INFORMS, vol. 65(1), pages 139-151, January.
    16. Martin I. Reiman & Qiong Wang, 2008. "An Asymptotically Optimal Policy for a Quantity-Based Network Revenue Management Problem," Mathematics of Operations Research, INFORMS, vol. 33(2), pages 257-282, May.
    17. Syed Asif Raza & Rafi Ashrafi & Ali Akgunduz, 2020. "A bibliometric analysis of revenue management in airline industry," Journal of Revenue and Pricing Management, Palgrave Macmillan, vol. 19(6), pages 436-465, December.
    18. Zizhuo Wang & Yinyu Ye, 2016. "Hidden-City Ticketing: The Cause and Impact," Transportation Science, INFORMS, vol. 50(1), pages 288-305, February.
    19. Sentao Miao & Xi Chen & Xiuli Chao & Jiaxi Liu & Yidong Zhang, 2022. "Context‐based dynamic pricing with online clustering," Production and Operations Management, Production and Operations Management Society, vol. 31(9), pages 3559-3575, September.
    20. Pornpawee Bumpensanti & He Wang, 2020. "A Re-Solving Heuristic with Uniformly Bounded Loss for Network Revenue Management," Management Science, INFORMS, vol. 66(7), pages 2993-3009, July.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:62:y:2014:i:4:p:876-890. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.