G.2.1 Combinatorics (F.2.2)
Refine
Document Type
- ZIB-Report (2) (remove)
Language
- English (2)
Has Fulltext
- yes (2)
Is part of the Bibliography
- no (2)
Keywords
- MST-heuristic (1)
- Markov decision problem (1)
- NP-hardness (1)
- Steiner trees (1)
- average case analysis (1)
- column generation (1)
- dial-a-ride-problem (1)
- linear programming (1)
Institute
- ZIB Allgemein (2)
The standard computational methods for computing the optimal value functions of Markov Decision Problems (MDP) require the exploration of the entire state space. This is practically infeasible for applications with huge numbers of states as they arise, e.\,g., from modeling the decisions in online optimization problems by MDPs. Exploiting column generation techniques, we propose and apply an LP-based method to determine an $\varepsilon$-approximation of the optimal value function at a given state by inspecting only states in a small neighborhood. In the context of online optimization problems, we use these methods in order to evaluate the quality of concrete policies with respect to given initial states. Moreover, the tools can also be used to obtain evidence of the impact of single decisions. This way, they can be utilized in the design of policies.
In the dial-a-ride-problem (DARP) objects have to be moved between given sources and destinations in a transportation network by means of a server. The goal is to find a shortest transportation for the server. We study the DARP when the underlying transportation network forms a caterpillar. This special case is strongly NP-hard in the worst case. We prove that in a probabilistic setting there exists a polynomial time algorithm which almost surely finds an optimal solution. Moreover, with high probability the optimality of the solution found can be certified efficiently. We also examine the complexity of the DARP in a semi-random setting and in the unweighted case.