IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v246y2015i3p708-720.html
   My bibliography  Save this article

Circumventing the Slater conundrum in countably infinite linear programs

Author

Listed:
  • Ghate, Archis

Abstract

Duality results on countably infinite linear programs are scarce. Subspaces that admit an interior point, which is a sufficient condition for a zero duality gap, yield a dual where the constraints cannot be expressed using the ordinary transpose of the primal constraint matrix. Subspaces that permit a dual with this transpose do not admit an interior point. This difficulty has stumped researchers for a few decades; it has recently been called the Slater conundrum. We find a way around this hurdle.

Suggested Citation

  • Ghate, Archis, 2015. "Circumventing the Slater conundrum in countably infinite linear programs," European Journal of Operational Research, Elsevier, vol. 246(3), pages 708-720.
    • Handle: RePEc:eee:ejores:v:246:y:2015:i:3:p:708-720
    DOI: 10.1016/j.ejor.2015.04.026
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221715003197
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2015.04.026?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Eitan Altman, 1994. "Denumerable Constrained Markov Decision Processes and Finite Approximations," Mathematics of Operations Research, INFORMS, vol. 19(1), pages 169-191, February.
    2. H. Edwin Romeijn & Robert L. Smith, 1998. "Shadow Prices in Infinite-Dimensional Linear Programming," Mathematics of Operations Research, INFORMS, vol. 23(1), pages 239-256, February.
    3. Chen, Xi & Ghate, Archis & Tripathi, Arvind, 2011. "Dynamic lot-sizing in sequential online retail auctions," European Journal of Operational Research, Elsevier, vol. 215(1), pages 257-267, November.
    4. Richard C. Grinold & David S. P. Hopkins, 1973. "Computing Optimal Solutions for Infinite-Horizon Mathematical Programs with a Transient Stage," Operations Research, INFORMS, vol. 21(1), pages 179-187, February.
    5. Archis Ghate & Robert L. Smith, 2013. "A Linear Programming Approach to Nonstationary Infinite-Horizon Markov Decision Processes," Operations Research, INFORMS, vol. 61(2), pages 413-425, April.
    6. Richard C. Grinold, 1971. "Infinite Horizon Programs," Management Science, INFORMS, vol. 18(3), pages 157-170, November.
    7. Archis Ghate & Dushyant Sharma & Robert L. Smith, 2010. "A Shadow Simplex Method for Infinite Linear Programs," Operations Research, INFORMS, vol. 58(4-part-1), pages 865-877, August.
    8. Edieal J. Pinker & Abraham Seidmann & Yaniv Vakrat, 2003. "Managing Online Auctions: Current Business and Research Issues," Management Science, INFORMS, vol. 49(11), pages 1457-1484, November.
    9. John P. Evans, 1969. "Duality in Markov Decision Problems with Countable Action and State Spaces," Management Science, INFORMS, vol. 15(11), pages 626-638, July.
    10. Irwin E. Schochetman & Robert L. Smith, 1989. "Infinite Horizon Optimization," Mathematics of Operations Research, INFORMS, vol. 14(3), pages 559-574, August.
    11. GRINOLD, Richard C., 1977. "Finite horizon approximations of infinite horizon linear programs," LIDAM Reprints CORE 294, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Ilbin Lee & Marina A. Epelman & H. Edwin Romeijn & Robert L. Smith, 2017. "Simplex Algorithm for Countable-State Discounted Markov Decision Processes," Operations Research, INFORMS, vol. 65(4), pages 1029-1042, August.
    2. Lidia Huerga & Baasansuren Jadamba & Miguel Sama, 2019. "An Extension of the Kaliszewski Cone to Non-polyhedral Pointed Cones in Infinite-Dimensional Spaces," Journal of Optimization Theory and Applications, Springer, vol. 181(2), pages 437-455, May.

    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. Archis Ghate & Dushyant Sharma & Robert L. Smith, 2010. "A Shadow Simplex Method for Infinite Linear Programs," Operations Research, INFORMS, vol. 58(4-part-1), pages 865-877, August.
    2. Ilbin Lee & Marina A. Epelman & H. Edwin Romeijn & Robert L. Smith, 2017. "Simplex Algorithm for Countable-State Discounted Markov Decision Processes," Operations Research, INFORMS, vol. 65(4), pages 1029-1042, August.
    3. H. Edwin Romeijn & Robert L. Smith, 1998. "Shadow Prices in Infinite-Dimensional Linear Programming," Mathematics of Operations Research, INFORMS, vol. 23(1), pages 239-256, February.
    4. Archis Ghate & Robert L. Smith, 2013. "A Linear Programming Approach to Nonstationary Infinite-Horizon Markov Decision Processes," Operations Research, INFORMS, vol. 61(2), pages 413-425, April.
    5. O. Zeynep Akşin, 2007. "On valuing appreciating human assets in services," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(2), pages 221-235, March.
    6. Jiang, Zhong-Zhong & Fang, Shu-Cherng & Fan, Zhi-Ping & Wang, Dingwei, 2013. "Selecting optimal selling format of a product in B2C online auctions with boundedly rational customers," European Journal of Operational Research, Elsevier, vol. 226(1), pages 139-153.
    7. Ghate, Archis, 2015. "Optimal minimum bids and inventory scrapping in sequential, single-unit, Vickrey auctions with demand learning," European Journal of Operational Research, Elsevier, vol. 245(2), pages 555-570.
    8. Wang, Hong, 2017. "Analysis and design for multi-unit online auctions," European Journal of Operational Research, Elsevier, vol. 258(3), pages 1191-1203.
    9. William P. Cross & H. Edwin Romeijn & Robert L. Smith, 1998. "Approximating Extreme Points of Infinite Dimensional Convex Sets," Mathematics of Operations Research, INFORMS, vol. 23(2), pages 433-442, May.
    10. Katehakis, Michael N. & Puranam, Kartikeya S., 2012. "On bidding for a fixed number of items in a sequence of auctions," European Journal of Operational Research, Elsevier, vol. 222(1), pages 76-84.
    11. Thomas W.M. Vossen & Fan You & Dan Zhang, 2022. "Finite‐horizon approximate linear programs for capacity allocation over a rolling horizon," Production and Operations Management, Production and Operations Management Society, vol. 31(5), pages 2127-2142, May.
    12. Seksan Kiatsupaibul & Robert L. Smith & Zelda B. Zabinsky, 2016. "Solving infinite horizon optimization problems through analysis of a one-dimensional global optimization problem," Journal of Global Optimization, Springer, vol. 66(4), pages 711-727, December.
    13. Radkevitch, U.L. & van Heck, H.W.G.M. & Koppius, O.R., 2008. "Coping with Costly Bid Evaluation in Online Reverse Auctions for IT Services," ERIM Report Series Research in Management ERS-2008-039-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    14. Meents, S. & Verhagen, T. & Vlaar, P.W.L., 2011. "How sellers can stimulate purchasing in electronic marketplaces: Using information as a risk reduction signal," Serie Research Memoranda 0014, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    15. René Caldentey & Gustavo Vulcano, 2007. "Online Auction and List Price Revenue Management," Management Science, INFORMS, vol. 53(5), pages 795-813, May.
    16. Liu, Xiaotian & Popkowski Leszczyc, Peter T.L., 2023. "The reference price effect of historical price lists in online auctions," Journal of Retailing and Consumer Services, Elsevier, vol. 71(C).
    17. Dixit, Ashutosh & Whipple, Thomas W. & Zinkhan, George M. & Gailey, Edward, 2008. "A taxonomy of information technology-enhanced pricing strategies," Journal of Business Research, Elsevier, vol. 61(4), pages 275-283, April.
    18. Ying-Ju Chen & Gustavo Vulcano, 2009. "Effects of Information Disclosure Under First- and Second-Price Auctions in a Supply Chain Setting," Manufacturing & Service Operations Management, INFORMS, vol. 11(2), pages 299-316, September.
    19. Verhagen, Tibert & Meents, Selmar, 2007. "A Framework for Developing Semantic Differentials in IS research: Assessing the Meaning of Electronic Marketplace Quality (EMQ)," Serie Research Memoranda 0016, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    20. Kartikeya Puranam & Michael Katehakis, 2014. "On optimal bidding and inventory control in sequential procurement auctions: the multi period case," Annals of Operations Research, Springer, vol. 217(1), pages 447-462, June.

    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:eee:ejores:v:246:y:2015:i:3:p:708-720. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.