On Constrained Mixed-Integer DR-Submodular Minimization

Qimeng Yu () and Simge Küçükyavuz ()
Additional contact information
Qimeng Yu: Département d’Informatique et de Recherche Opérationnelle, Université de Montréal, Montréal, Quebec H3T 1J4, Canada
Simge Küçükyavuz: Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, Illinois 60208

Mathematics of Operations Research, 2025, vol. 50, issue 2, 871-909

Abstract: 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.

Keywords: Primary: 90C11; 90C57 (Polyhedral combinatorics; branch-and-bound; branch-and-cut); DR-submodular minimization; mixed-integer variables; polyhedral study; convex hull (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.0320 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:50:y:2025:i:2:p:871-909

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().