On Exact Dual and Mixed-Integer Reformulations for Finite Horizon Markov Decision Processes with Submodular Revenue Maximization

Jia-Yu Chen, Hsin-Yuan Huang, Tzu-Yang Teng, Yun-Jen Tsai, Hao-Hsiang Wu

arXivarxiv/2611.01863Nov 1, 2026math.OCscore 0

We study exact mixed-integer reformulations of a finite horizon Markov decision process (MDP) with transition revenues defined by local submodular revenue maximization problems. We start with the dual linear programming formulation of the MDP, where local optimal revenues appear in the objective function and the constraints describe the state probabilities from the initial state. We combine the dual formulation with the binary variables of the local problems and obtain an exact mixed-integer nonlinear formulation with bilinear terms. We use the submodular inequalities and an exact McCormick…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2611.01863
curl -X POST /api/v1/records/arxiv/2611.01863/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.01863/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'