H. Edwin Romeijn

Simplex Algorithm for Countable-state Discounted Markov Decision Processes

  • Marina A. Epelman
  • H. Edwin Romeijn
  • Ilbin Lee
  • Robert L. Smith
    • Categories Dynamic Programming, Infinite Dimensional Optimization, Linear Programming Tags , ,

    We consider discounted Markov Decision Processes (MDPs) with countably-infinite state spaces, finite action spaces, and unbounded rewards. Typical examples of such MDPs are inventory management and queueing control problems in which there is no specific limit on the size of inventory or queue. Existing solution methods obtain a sequence of policies that converges to optimality … Read more

    Extreme Point Solutions for Infinite Network Flow Problems

  • H. Edwin Romeijn
  • Dushyant Sharma
  • Robert L. Smith
    • Categories Infinite Dimensional Optimization, Network Optimization Tags ,

    We study capacitated network flow problems with supplies and demands defined on a countably infinite collection of nodes having finite degree. This class of network flow models includes, for example, all infinite horizon deterministic dynamic programs with finite action sets since these are equivalent to the problem of finding a shortest infinite path in an … Read more