A Shadow Simplex Method for Infinite Linear Programs

Archis Ghate (), Dushyant Sharma () and Robert L. Smith ()
Additional contact information
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

Operations Research, 2010, vol. 58, issue 4-part-1, 865-877

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.

Keywords: programming; infinite dimensional; dynamic programming/optimal control; Markov; infinite state; network/graphs; theory (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1090.0755 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:58:y:2010:i:4-part-1:p:865-877

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().