The scalability of algorithms for solving Markov Decision Processes (MDPs) has been a limiting factor for MDPs as a modeling tool. This dissertation develops theoretical and empirical techniques for solving larger MDPs than was possible before, and aims to demonstrate the achieved progress by applying these new algorithms to a real-world problem.