Submodular maximization and its generalization through an intersection cut lens.
Saved in:
| Title: | Submodular maximization and its generalization through an intersection cut lens. |
|---|---|
| Authors: | Xu, Liding1 (AUTHOR) liding.xu@polytechnique.edu, Liberti, Leo1 (AUTHOR) liberti@lix.polytechnique.fr |
| Source: | Mathematical Programming. May2025, Vol. 211 Issue 1, p341-377. 37p. |
| Subjects: | Submodular functions, Boolean functions, Set functions, Generalization, Algorithms |
| Abstract: | We study a mixed-integer set S : = { (x , t) ∈ { 0 , 1 } n × R : f (x) ≥ t } arising in the submodular maximization problem, where f is a submodular function defined over { 0 , 1 } n . We use intersection cuts to tighten a polyhedral outer approximation of S . We construct a continuous extension F ¯ f of f, which is convex and defined over the entire space R n . We show that the epigraph epi ( F ¯ f) of F ¯ f is an S -free set, and characterize maximal S -free sets containing epi ( F ¯ f) . We propose a hybrid discrete Newton algorithm to compute an intersection cut efficiently and exactly. Our results are generalized to the hypograph or the superlevel set of a submodular-supermodular function over the Boolean hypercube, which is a model for discrete nonconvexity. A consequence of these results is intersection cuts for Boolean multilinear constraints. We evaluate our techniques on max cut, pseudo Boolean maximization, and Bayesian D-optimal design problems within a MIP solver. [ABSTRACT FROM AUTHOR] |
| Copyright of Mathematical Programming is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| Abstract: | We study a mixed-integer set S : = { (x , t) ∈ { 0 , 1 } n × R : f (x) ≥ t } arising in the submodular maximization problem, where f is a submodular function defined over { 0 , 1 } n . We use intersection cuts to tighten a polyhedral outer approximation of S . We construct a continuous extension F ¯ f of f, which is convex and defined over the entire space R n . We show that the epigraph epi ( F ¯ f) of F ¯ f is an S -free set, and characterize maximal S -free sets containing epi ( F ¯ f) . We propose a hybrid discrete Newton algorithm to compute an intersection cut efficiently and exactly. Our results are generalized to the hypograph or the superlevel set of a submodular-supermodular function over the Boolean hypercube, which is a model for discrete nonconvexity. A consequence of these results is intersection cuts for Boolean multilinear constraints. We evaluate our techniques on max cut, pseudo Boolean maximization, and Bayesian D-optimal design problems within a MIP solver. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 00255610 |
| DOI: | 10.1007/s10107-024-02059-2 |
