Metraipolis › archive › dc_eacdf6786302
On Exact Dual and Mixed-Integer Reformulations for Finite Horizon Markov Decision Processes with Submodular Revenue Maximization — arXiv:2611.01863
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.01863
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T18:45:31.132Z
- SHA-256 of the archived text
7f9e4583c3c922a8ff32ab611a97f82895aaa960e3559b3ee2303ac2784ebe5e- Stable URL of this page
https://metraipolis.com/documento/dc_eacdf6786302
How to cite
On Exact Dual and Mixed-Integer Reformulations for Finite Horizon Markov Decision Processes with Submodular Revenue Maximization — arXiv:2611.01863 — arXiv (en), https://arxiv.org/abs/2611.01863 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_eacdf6786302 (Metraipolis archive dc_eacdf6786302, sha256 7f9e4583c3c922a8ff32ab611a97f82895aaa960e3559b3ee2303ac2784ebe5e)
BibTeX
@misc{dceacdf6786302,
title = {On Exact Dual and Mixed-Integer Reformulations for Finite Horizon Markov Decision Processes with Submodular Revenue Maximization — arXiv:2611.01863},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.01863},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_eacdf6786302; sha256 7f9e4583c3c922a8ff32ab611a97f82895aaa960e3559b3ee2303ac2784ebe5e},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.01863. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 linearization to obtain an equivalent mixed-integer linear formulation. We also use the dual structure to conduct a sensitivity analysis of the MDP optimal value with respect to changes in the local revenue coefficients. Based on local incumbent revenues and upper bounds, this sensitivity analysis evaluates the effect of local optimality gaps on the global MDP optimality gap, without solving every local revenue maximization problem to optimality. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno). Categorie arXiv: Optimization and Control (math.OC). Pagina del lavoro: https://arxiv.org/abs/2611.01863 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-03T18:14:37.769Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).