IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v58y2010i4-part-1p865-877.html
   My bibliography  Save this article

A Shadow Simplex Method for Infinite Linear Programs

Author

Listed:
  • Archis Ghate

    (Industrial and Systems Engineering Department, University of Washington, Seattle, Washington 98195)

  • Dushyant Sharma

    (Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109)

  • Robert L. Smith

    (Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109)

Abstract

We present a simplex-type algorithm---that is, an algorithm that moves from one extreme point of the infinite-dimensional feasible region to another, not necessarily adjacent, extreme point---for solving a class of linear programs with countably infinite variables and constraints. Each iteration of this method can be implemented in finite time, whereas the solution values converge to the optimal value as the number of iterations increases. This simplex-type algorithm moves to an adjacent extreme point and hence reduces to a true infinite-dimensional simplex method for the important special cases of nonstationary infinite-horizon deterministic and stochastic dynamic programs.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:oropre:v:58:y:2010:i:4-part-1:p:865-877
    DOI: 10.1287/opre.1090.0755
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1090.0755
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1090.0755?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. Richard C. Grinold, 1971. "Infinite Horizon Programs," Management Science, INFORMS, vol. 18(3), pages 157-170, November.
    2. 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.
    3. Eugene A. Feinberg & Adam Shwartz, 1996. "Constrained Discounted Dynamic Programming," Mathematics of Operations Research, INFORMS, vol. 21(4), pages 922-945, November.
    4. Wallace J. Hopp & James C. Bean & Robert L. Smith, 1987. "A New Optimality Criterion for Nonhomogeneous Markov Decision Processes," Operations Research, INFORMS, vol. 35(6), pages 875-883, December.
    5. Torpong Cheevaprawatdomrong & Irwin E. Schochetman & Robert L. Smith & Alfredo Garcia, 2007. "Solution and Forecast Horizons for Infinite-Horizon Nonhomogeneous Markov Decision Processes," Mathematics of Operations Research, INFORMS, vol. 32(1), pages 51-72, February.
    6. 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.
    7. E. J. Anderson & P. Nash & A. B. Philpott, 1982. "A Class of Continuous Network Flow Problems," Mathematics of Operations Research, INFORMS, vol. 7(4), pages 501-514, November.
    8. Goberna, M. A. & Lopez, M. A., 2002. "Linear semi-infinite programming theory: An updated survey," European Journal of Operational Research, Elsevier, vol. 143(2), pages 390-405, December.
    9. Edward J. Anderson & Miguel A. Goberna & Marco A. López, 2001. "Simplex-Like Trajectories on Quasi-Polyhedral Sets," Mathematics of Operations Research, INFORMS, vol. 26(1), pages 147-162, February.
    10. Arthur F. Veinott, 1969. "Minimum Concave-Cost Solution of Leontief Substitution Models of Multi-Facility Inventory Systems," Operations Research, INFORMS, vol. 17(2), pages 262-291, April.
    11. Diego Klabjan & Daniel Adelman, 2007. "An Infinite-Dimensional Linear Programming Algorithm for Deterministic Semi-Markov Decision Processes on Borel Spaces," Mathematics of Operations Research, INFORMS, vol. 32(3), pages 528-550, August.
    12. W. D. Cook & C. A. Field & M. J. L. Kirby, 1975. "Infinite Linear Programming in Games with Partial Information," Operations Research, INFORMS, vol. 23(5), pages 996-1010, October.
    13. D. J. White, 1996. "Decision Roll and Horizon Roll Processes in Infinite Horizon Discounted Markov Decision Processes," Management Science, INFORMS, vol. 42(1), pages 37-50, January.
    14. Irwin E. Schochetman & Robert L. Smith, 1989. "Infinite Horizon Optimization," Mathematics of Operations Research, INFORMS, vol. 14(3), pages 559-574, August.
    15. 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. Ghate, Archis, 2015. "Circumventing the Slater conundrum in countably infinite linear programs," European Journal of Operational Research, Elsevier, vol. 246(3), pages 708-720.
    3. M. A. Goberna & M. A. López, 2017. "Recent contributions to linear semi-infinite optimization," 4OR, Springer, vol. 15(3), pages 221-264, September.
    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. M. A. Goberna & M. A. López, 2018. "Recent contributions to linear semi-infinite optimization: an update," Annals of Operations Research, Springer, vol. 271(1), pages 237-278, December.

    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. Ghate, Archis, 2015. "Circumventing the Slater conundrum in countably infinite linear programs," European Journal of Operational Research, Elsevier, vol. 246(3), pages 708-720.
    2. 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.
    3. 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.
    4. 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.
    5. Suresh Chand & Vernon Ning Hsu & Suresh Sethi, 2002. "Forecast, Solution, and Rolling Horizons in Operations Management Problems: A Classified Bibliography," Manufacturing & Service Operations Management, INFORMS, vol. 4(1), pages 25-43, September.
    6. Sampath Rajagopalan & Medini R. Singh & Thomas E. Morton, 1998. "Capacity Expansion and Replacement in Growing Markets with Uncertain Technological Breakthroughs," Management Science, INFORMS, vol. 44(1), pages 12-30, January.
    7. M. A. Goberna & M. A. López, 2018. "Recent contributions to linear semi-infinite optimization: an update," Annals of Operations Research, Springer, vol. 271(1), pages 237-278, December.
    8. Huang, Kai & Ahmed, Shabbir, 2010. "A stochastic programming approach for planning horizons of infinite horizon capacity planning problems," European Journal of Operational Research, Elsevier, vol. 200(1), pages 74-84, January.
    9. M. A. Goberna & M. A. López, 2017. "Recent contributions to linear semi-infinite optimization," 4OR, Springer, vol. 15(3), pages 221-264, September.
    10. 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.
    11. Krishnamurthy Iyer & Nandyala Hemachandra, 2010. "Sensitivity analysis and optimal ultimately stationary deterministic policies in some constrained discounted cost models," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 71(3), pages 401-425, June.
    12. Allise O. Wachs & Irwin E. Schochetman & Robert L. Smith, 2011. "Average Optimality in Nonhomogeneous Infinite Horizon Markov Decision Processes," Mathematics of Operations Research, INFORMS, vol. 36(1), pages 147-164, February.
    13. S. Mishra & M. Jaiswal & H. Le Thi, 2012. "Nonsmooth semi-infinite programming problem using Limiting subdifferentials," Journal of Global Optimization, Springer, vol. 53(2), pages 285-296, June.
    14. 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.
    15. S. Hashemi & Ebrahim Nasrabadi, 2012. "On solving continuous-time dynamic network flows," Journal of Global Optimization, Springer, vol. 53(3), pages 497-524, July.
    16. S Opasanon & E Miller-Hooks, 2009. "The Safest Escape problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(12), pages 1749-1758, December.
    17. 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.
    18. Jonathan Patrick & Martin L. Puterman & Maurice Queyranne, 2008. "Dynamic Multipriority Patient Scheduling for a Diagnostic Resource," Operations Research, INFORMS, vol. 56(6), pages 1507-1525, December.
    19. Chia‐Shin Chung & Sin‐Hoon Hum & Omer Kirca, 2000. "An optimal procedure for the coordinated replenishment dynamic lot‐sizing problem with quantity discounts," Naval Research Logistics (NRL), John Wiley & Sons, vol. 47(8), pages 686-695, December.
    20. Khanh T.P. Nguyen & Thomas Yeung & Bruno Castanier, 2017. "Acquisition of new technology information for maintenance and replacement policies," International Journal of Production Research, Taylor & Francis Journals, vol. 55(8), pages 2212-2231, April.

    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:58:y:2010:i:4-part-1:p:865-877. 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.