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 show that the Hamiltonian Cycle Problem is a special case of each of these problems. Therefore problems (i-iii) are NP-hard in spite of the fact that a minor modification of problem (i) is polynomially solvable. We construct mathematical programs for each of these problems and formulate algorithms for the Hamiltonian Cycle and Traveling Salesman Problems that follow from the algorithms for problems (i-iii).