On Constrained Mixed-Integer DR-Submodular Minimization
研究了在盒约束和单调性约束下，最小化连续和整数变量的DR-子模函数问题，提出了有效线性不等式并证明了其多项式时间可解性。
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. Funding: This work was supported by the Office of Naval Research Global [Grant N00014-22-1-2602].