On Constrained Mixed-Integer DR-Submodular Minimization

• 成果类型: Article
• 署名作者: Yu, Qimeng; Kucukyavuz, Simge
• 署名单位: Universite de Montreal; Northwestern University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.0320
• 发表日期: 2025
• 关键词: polynomial-time algorithm; set function subject; linear inequalities; 2 variables; PROGRAMS; RISK; maximization

摘要

Diminishing returns (DR)-submodular functions encompass a broad class of functions that are generally nonconvex and nonconcave. We study the problem of minimizing any DR-submodular function with continuous and general integer variables under box constraints and, possibly, additional monotonicity constraints. We propose valid linear inequalities for the epigraph of any DR-submodular function under the constraints. We further provide the complete convex hull of such an epigraph, which, surprisingly, turns out to be polyhedral. We propose a polynomial -time exact separation algorithm for our proposed valid inequalities with which we first establish the polynomial -time solvability of this class of mixed -integer nonlinear optimization problems.