EconPapers    
Economics at your fingertips  
 

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 ().

 
Page updated 2025-05-27
Handle: RePEc:inm:ormoor:v:50:y:2025:i:2:p:871-909