OPUS 4 Latest Documents RSS FeedLatest documents
http://opus4.kobv.de/opus4-ubbayreuth/index/index/
Sat, 11 May 2013 10:04:42 +0100Sat, 11 May 2013 10:04:42 +0100Computational Bounds for Elevator Control Policies by Large Scale Linear Programming
http://opus4.kobv.de/opus4-ubbayreuth/frontdoor/index/index/docId/1378
We computationally assess policies for the elevator control problem by a new column-generation approach for the linear programming method for discounted infinite-horizon Markov decision problems. By analyzing the optimality of given actions in given states, we were able to provably improve the well-known nearest-neighbor policy. Moreover, with the method we could identify an optimal parking policy. This approach can be used to detect and resolve weaknesses in particular policies for Markov decision problems.Stefan Heinz; Jörg Rambau; Andreas Tuchschererpreprinthttp://opus4.kobv.de/opus4-ubbayreuth/frontdoor/index/index/docId/1378Tue, 05 Nov 2013 10:04:42 +0100Local Approximation of Discounted Markov Decision Problems by Mathematical Programming Methods
http://opus4.kobv.de/opus4-ubbayreuth/frontdoor/index/index/docId/678
We develop a method to approximate the value vector of discounted Markov decision problems (MDP) with guaranteed error bounds. It is based on the linear programming characterization of the optimal expected cost. The new idea is to use column generation to dynamically generate only such states that are most relevant for the bounds by incorporating the reduced cost information. The number of states that is sufficient in general and necessary in the worst case to prove such bounds is independent of the cardinality of the state space. Still, in many instances, the column generation algorithm can prove bounds using much fewer states. In this paper, we explain the foundations of the method. Moreover, the method is used to improve the well-known nearest-neighbor policy for the elevator control problem.Stefan Heinz; Jörg Rambau; Andreas Tuchschererpreprinthttp://opus4.kobv.de/opus4-ubbayreuth/frontdoor/index/index/docId/678Tue, 24 May 2011 11:15:59 +0200