Constrained discounted Markov Decision Processes and Hamiltonian Cycles

This paper establishes new links between stochastic and discrete optimization. We consider the following three problems for discrete time Markov Decision Processes with finite states and action sets: (i) find an optimal deterministic policy for a discounted problem with constraints, (ii) find an optimal stationary policy for a weighted discounted problem with constraints, (iii) find an optimal deterministic policy for a weighted discounted problem with constraints. We formulate mathematical programs for problems (i)-(iii) and show that the Hamiltonian Cycle Problem is a special case of each of these problems. Therefore problems (i)-(iii) are NP-hard. We also provide new mathematical programming formulations for the Hamiltonian Cycle and Traveling Salesman Problems.