Industrial and Operations Engineering, Department of (IOE)
http://hdl.handle.net/2027.42/78369
2016-07-26T18:03:28ZA linear programming approach to constrained nonstationary infinite-horizon Markov decision processes
http://hdl.handle.net/2027.42/109729
A linear programming approach to constrained nonstationary infinite-horizon Markov decision processes
Lee, Ilbin; Epelman, Marina A; Romeijn, H. Edwin; Smith, Robert L
Constrained Markov decision processes (MDPs) are MDPs optimizing an objective function while satisfying additional constraints. We study a class of infinite-horizon constrained MDPs with nonstationary problem data, finite state space, and discounted cost criterion. This problem can equivalently be formulated as a countably infinite linear program (CILP), i.e., a linear program (LP) with a countably infinite number of variables and constraints. Unlike finite LPs, CILPs can fail to satisfy useful theoretical properties such as duality, and to date there does not exist a general solution method for such problems. Specifically, the characterization of extreme points as basic feasible solutions in finite LPs does not extend to general CILPs. In this paper, we provide duality results and a complete characterization of extreme points of the CILP formulation of constrained nonstationary MDPs with finite state space, and illustrate the characterization for special cases. As a corollary, we obtain the existence of a K-randomized optimal policy, where K is the number of constraints.
2013-03-06T00:00:00ZSimplex 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:00Z