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.
|
|
| FullText | Links: – Type: pdflink Text: Availability: 1 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 184787732 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Submodular maximization and its generalization through an intersection cut lens. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Xu%2C+Liding%22">Xu, Liding</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> liding.xu@polytechnique.edu</i><br /><searchLink fieldCode="AR" term="%22Liberti%2C+Leo%22">Liberti, Leo</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> liberti@lix.polytechnique.fr</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Mathematical+Programming%22">Mathematical Programming</searchLink>. May2025, Vol. 211 Issue 1, p341-377. 37p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Submodular+functions%22">Submodular functions</searchLink><br /><searchLink fieldCode="DE" term="%22Boolean+functions%22">Boolean functions</searchLink><br /><searchLink fieldCode="DE" term="%22Set+functions%22">Set functions</searchLink><br /><searchLink fieldCode="DE" term="%22Generalization%22">Generalization</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=184787732 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s10107-024-02059-2 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 37 StartPage: 341 Subjects: – SubjectFull: Submodular functions Type: general – SubjectFull: Boolean functions Type: general – SubjectFull: Set functions Type: general – SubjectFull: Generalization Type: general – SubjectFull: Algorithms Type: general Titles: – TitleFull: Submodular maximization and its generalization through an intersection cut lens. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Xu, Liding – PersonEntity: Name: NameFull: Liberti, Leo IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 05 Text: May2025 Type: published Y: 2025 Identifiers: – Type: issn-print Value: 00255610 Numbering: – Type: volume Value: 211 – Type: issue Value: 1 Titles: – TitleFull: Mathematical Programming Type: main |
| ResultId | 1 |
