On Constrained Mixed-Integer DR-Submodular Minimization
From MaRDI portal
Abstract: DR-submodular functions encompass a broad class of functions which are generally non-convex and non-concave. 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.
This page was built for publication: On Constrained Mixed-Integer DR-Submodular Minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6417252)
