A Shadow Simplex Method for Infinite Linear Programs

References

• Aliprantis C. D., Border K. C.Infinite Dimensional Analysis: A Hitchhiker's Guide (1994) (Springer-Verlag, Berlin) Crossref, Google Scholar
• Anderson E. J., Lewis A. S. An extension of Simplex algorithm for semi-infinite linear programming. Math. Programming (1988) 44:247–269Crossref, Google Scholar
• Anderson E. J., Nash P.Linear Programming in Infinite-Dimensional Spaces: Theory and Applications (1987) (John Wiley & Sons, Chichester, UK) Google Scholar
• Anderson E. J., Nash P. A continuous-time network Simplex algorithm. Networks (1989) 19(4):395–425Crossref, Google Scholar
• Anderson E. J., Goberna M. A., Lopez M. A. Locally polyhedral linear inequality systems. Linear Algebra Appl. (1998) 270:231–253Crossref, Google Scholar
• Anderson E. J., Goberna M. A., Lopez M. A. Simplex-like trajectories on quasi-polyhedral sets. Math. Oper. Res. (2001) 26(1):147–162Link, Google Scholar
• Anderson E. J., Nash P., Philpott A. B. A class of continuous network flow problems. Math. Oper. Res. (1982) 7(4):501–514Link, Google Scholar
• Apostol T. M.Mathematical Analysis (1974) 2nd ed.(Addison Wesley, Reading, MA) Google Scholar
• Bean J. C., Lohmann J. R., Smith R. L. A dynamic infinite horizon replacement economy decision model. Engrg. Economist (1985) 30:99–120Crossref, Google Scholar
• Bertsimas D., Tsitsiklis J. N.Introduction to Linear Optimization (1997) (Athena Scientific, Belmont, MA) Google Scholar
• Cheevaprawatdomrong T., Schochetman I. E., Smith R. L., Garcia A. Solution and forecast horizons for infinite-horizon non-homogeneous Markov decision processes. Math. Oper. Res. (2007) 32(1):51–72Link, Google Scholar
• Cook W. D., Field C. A., Kirby M. J. L. Infinite linear programs in games with partial information. Oper. Res. (1975) 23(5):996–1010Link, Google Scholar
• Cross W. P., Romeijn H. E., Smith R. L. Approximating extreme points of infinite dimensional convex sets. Math. Oper. Res. (1998) 23(2):433–442Link, Google Scholar
• Demaine E. D., Fekete S. P., Gal S. Online searching with turn cost. Theoret. Comput. Sci. (2006) 361(2):342–355Crossref, Google Scholar
• Feinberg E., Shwartz A. Constrained discounted dynamic programming. Math. Oper. Res. (1996) 21:922–945Link, Google Scholar
• Feinberg E., Shwartz A.Handbook of Markov Decision Processes: Methods and Algorithms (2002) (Kluwer, Boston) Crossref, Google Scholar
• Garcia A., Smith R. L. Solving nonstationary infinite horizon dynamic optimization problems. J. Math. Anal. Appl. (2000) 244:304–317Crossref, Google Scholar
• Ghate A. V. Markov chains, game theory, and infinite programming: Three paradigms for optimization of complex systems. (2006) . Ph.D. thesis, Industrial and Operations Engineering, The University of Michigan, Ann ArborGoogle Scholar
• Ghate A. V., Smith R. L. Characterizing extreme points as basic feasible solutions in infinite linear programs. Oper. Res. Lett. (2009a) 37(1):7–10Crossref, Google Scholar
• Ghate A. V., Smith R. L. Duality theory for countably infinite linear programs. (2009b) . Working paper, University of Washington, SeattleGoogle Scholar
• Ghate A. V., Smith R. L. A short note on extendability in truncations of infinite-horizon production planning problems. (2009c) . Working paper, University of Washington, SeattleGoogle Scholar
• Goberna M. A., Lopez M. A.Linear Semi-Infinite Optimization (1998) (Wiley, New York) Google Scholar
• Goberna M. A., Lopez M. A. Linear semi-infinite programming theory: An updated survey. Eur. J. Oper. Res. (2002) 143:390–405Crossref, Google Scholar
• Grinold R. C. Infinite horizon programs. Management Sci. (1971) 18(3):157–170Link, Google Scholar
• Grinold R. C. Finite horizon approximations of infinite horizon linear programs. Math. Programming (1977) 12:1–17Crossref, Google Scholar
• Grinold R. C. Convex infinite horizon programs. Math. Programming (1983) 25(1):64–82Crossref, Google Scholar
• Grinold R. C. Infinite horizon stochastic programs. SIAM J. Control Optim. (1986) 24(6):1246–1260Crossref, Google Scholar
• Hernandez-Lerma O., Lasserre J. B. Approximation schemes for infinite linear programs. SIAM J. Optim. (1998) 8(4):973–988Crossref, Google Scholar
• Hernandez-Lerma O., Lasserre J. B., Feinberg E., Shwartz A. The linear programming approach. Handbook of Markov Decision Processes: Methods and Algorithms (2002) (Kluwer, Boston) Crossref, Google Scholar
• Hopp W. J., Bean J. C., Smith R. L. A new optimality criterion for non-homogeneous Markov decision processes. Oper. Res. (1987) 35:875–883Link, Google Scholar
• Huang K. Multi-stage stochastic programming models in production planning. (2005) . Ph.D. thesis, School of Industrial and Systems Engineering, Georgia Institute of Technology, AtlantaGoogle Scholar
• Klabjan D., Adelman D. Existence of optimal policies for semi-Markov decision processes using duality for infinite linear programming. Math. Oper. Res. (2005) 30(1):28–50Link, Google Scholar
• Klabjan D., Adelman D. A convergent infinite dimensional linear programming algorithm for deterministic semi-Markov decision processes on Borel spaces. Math. Oper. Res. (2007) 32(3):528–550Link, Google Scholar
• Luenberger D. G.Optimization by Vector Space Methods (1969) (John Wiley & Sons, New York) Google Scholar
• Philpott A. B., Craddock M. An adaptive discretization algorithm for a class of continuous network programs. Networks (1995) 26:1–11Crossref, Google Scholar
• Pullan M. C. An algorithm for a class of continuous linear programs. SIAM J. Control Optim. (1993) 31:1558–1577Crossref, Google Scholar
• Pullan M. C. Convergence of a general class of algorithms for separated continuous linear programs. SIAM J. Optim. (2000) 10:722–731Crossref, Google Scholar
• Puterman M. L. Markov decision processes: Discrete stochastic dynamic programming. (1994) (John Wiley & Sons, New York) Crossref, Google Scholar
• Romeijn H. E., Smith R. L. Shadow prices in infinite-dimensional linear programming. Math. Oper. Res. (1998) 23(1):239–256Link, Google Scholar
• Romeijn H. E., Sharma D., Smith R. L. Extreme point solutions for infinite network flow problems. Networks (2006) 48(4):209–222Crossref, Google Scholar
• Romeijn H. E., Smith R. L., Bean J. C. Duality in infinite dimensional linear programming. Math. Programming (1992) 53:79–97Crossref, Google Scholar
• Ross S. M.Introduction to Stochastic Dynamic Programming (1983) (Academic Press, New York) Google Scholar
• Schochetman I. E., Smith R. L. Infinite horizon optimization. Math. Oper. Res. (1989) 14:559–574Link, Google Scholar
• Sharkey T. C., Romeijn H. E. A Simplex algorithm for minimum cost network flow problems in infinite networks. Networks (2008) 52(1):14–31Crossref, Google Scholar
• Veinott A. F. Extreme points of Leontief substitution systems. Linear Algebra Appl. (1968) 1:181–194Crossref, Google Scholar
• Veinott A. F. Minimum concave cost solution of Leontief substitution models of multi-facility inventory systems. Oper. Res. (1969) 17(2):262–291Link, Google Scholar
• Weiss G. A simplex based algorithm to solve separated continuous linear programs. Math. Programming (2008) 115(1):151–198Crossref, Google Scholar
• White D. J. Decision roll and horizon roll in infinite horizon discounted Markov decision processes. Management Sci. (1996) 42(1):37–50Link, Google Scholar