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. 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.
    7. Wang, Hong, 2017. "Analysis and design for multi-unit online auctions," European Journal of Operational Research, Elsevier, vol. 258(3), pages 1191-1203.
    8. 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.
    9. 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.
    10. 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.
    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. 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.
    13. 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.
    14. Kim, Ju-Young & Brünner, Tobias & Skiera, Bernd & Natter, Martin, 2014. "A comparison of different pay-per-bid auction formats," International Journal of Research in Marketing, Elsevier, vol. 31(4), pages 368-379.
    15. Gebauer, Judith & Mahoney, Joseph T., 2013. "Joining Supply and Demand Conditions of IT Enabled Change: Toward an Economic Theory of Inter-firm Modulation," Working Papers 13-0100, University of Illinois at Urbana-Champaign, College of Business.
    16. Ahlert, Klaus-Henning & Corsten, Hans & Gössinger, Ralf, 2009. "Capacity management in order-driven production networks--A flexibility-oriented approach to determine the size of a network capacity pool," International Journal of Production Economics, Elsevier, vol. 118(2), pages 430-441, April.
    17. Arthur M. Geoffrion & Ramayya Krishnan, 2003. "E-Business and Management Science: Mutual Impacts (Part 1 of 2)," Management Science, INFORMS, vol. 49(10), pages 1275-1286, October.
    18. Chen, Kong-Pin & Lai, Hung-pin & Yu, Ya-Ting, 2018. "The seller's listing strategy in online auctions: Evidence from eBay," International Journal of Industrial Organization, Elsevier, vol. 56(C), pages 107-144.
    19. Li, Zhen & Kuo, Ching-Chung, 2011. "Revenue-maximizing Dutch auctions with discrete bid levels," European Journal of Operational Research, Elsevier, vol. 215(3), pages 721-729, December.
    20. Jason Kuruzovich & Hila Etzion, 2018. "Online Auctions and Multichannel Retailing," Management Science, INFORMS, vol. 64(6), pages 2734-2753, 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.