Maximizing a class of submodular utility functions with constraints

DOI10.1007/s10107-016-1033-3zbMath1358.90085OpenAlexW2413913460MaRDI QIDQ517299

Jiajin Yu, Shabbir Ahmed

Publication date: 23 March 2017

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-016-1033-3

zbMATH Keywords

liftingsubmodularitycutting planesbranch-and-cutmixed integer nonlinear programming

Mathematics Subject Classification ID

Mixed integer programming (90C11)

Related Items (13)

Sequence Independent Lifting for the Set of Submodular Maximization Problem ⋮ A polyhedral approach to bisubmodular function minimization ⋮ An exact method for constrained maximization of the conditional value-at-risk of a class of stochastic submodular functions ⋮ Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints ⋮ Supermodularity and valid inequalities for quadratic optimization with indicators ⋮ A two-stage stochastic programming approach for influence maximization in social networks ⋮ New solution approaches for the maximum-reliability stochastic network interdiction problem ⋮ Outer approximation and submodular cuts for maximum capture facility location problems with random utilities ⋮ An exact cutting plane method for \(k\)-submodular function maximization ⋮ Special issue: Global solution of integer, stochastic and nonconvex optimization problems ⋮ Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems ⋮ Submodular function minimization and polarity ⋮ Sequence independent lifting for a set of submodular maximization problems

Cites Work

• Unnamed Item
• Unnamed Item
• Maximizing a class of submodular utility functions
• Competitive facility location model with concave demand
• On a discrete nonlinear and nonseparable knapsack problem
• The submodular knapsack polytope
• Maximizing expected utility over a knapsack constraint
• Sequence independent lifting in mixed integer programming
• Combinatorial auctions with decreasing marginal utilities
• Maximizing Non-monotone Submodular Functions
• Approximation algorithms for combinatorial auctions with complement-free bidders
• Resource Allocation to Interrelated Risky Projects Using a Multiattribute Utility Function
• Valid Inequalities and Superadditivity for 0–1 Integer Programs
• Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems
• Benchmarking optimization software with performance profiles.

This page was built for publication: Maximizing a class of submodular utility functions with constraints