Industrial and Operations Engineering, Department of (IOE)
http://hdl.handle.net/2027.42/78369
2014-11-26T10:01:04ZSimplex Algorithm for Countable-state Discounted Markov Decision Processes
http://hdl.handle.net/2027.42/109413
Simplex Algorithm for Countable-state Discounted Markov Decision Processes
Lee, Ilbin; Epelman, Marina A.; Romeijn, H. Edwin; Smith, Robert L.
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 in value but may not improve monotonically, i.e., a policy in the sequence may be worse than preceding policies. Our proposed approach considers countably-infinite linear programming (CILP) formulations of the MDPs (a CILP is defined as a linear program (LP) with countably-infinite numbers of variables and constraints). Under standard assumptions for analyzing MDPs with countably-infinite state spaces and unbounded rewards, we extend the major theoretical extreme point and duality results to the resulting CILPs. Under an additional technical assumption which is satisfied by several applications of interest, we present a simplex-type algorithm that is implementable in the sense that each of its iterations requires only a finite amount of data and computation. We show that the algorithm finds a sequence of policies which improves monotonically and converges to optimality in value. Unlike existing simplex-type algorithms for CILPs, our proposed algorithm solves a class of CILPs in which each constraint may contain an infinite number of variables and each variable may appear in an infinite number of constraints. A numerical illustration for inventory management problems is also presented.
Submitted to Operations Research; preliminary version.
2014-11-18T00:00:00ZManaging White-Collar Work: An Operations-Oriented Survey
http://hdl.handle.net/2027.42/73896
Managing White-Collar Work: An Operations-Oriented Survey
Hopp, Wallace J.; Iravani, Seyed M. R.; Liu, Fang
2009-01-01T00:00:00ZNetwork delay tomography using flexicast experiments
http://hdl.handle.net/2027.42/73739
Network delay tomography using flexicast experiments
Lawrence, Earl; Michailidis, George; Nair, Vijayan N.
2006-11-01T00:00:00ZModelling three-dimensional trajectories by using BÉzier curves with application to hand motion
http://hdl.handle.net/2027.42/72561
Modelling three-dimensional trajectories by using BÉzier curves with application to hand motion
Faraway, Julian J.; Reed, Matthew P.; Wang, Jing
2007-11-01T00:00:00Z