Sequence independent lifting for a set of submodular maximization problems

DOI10.1007/s10107-022-01801-yzbMath1506.90174OpenAlexW4224259771MaRDI QIDQ2097631

Bo Zeng, Xueyu Shi, Oleg A. Prokopyev

Publication date: 14 November 2022

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

Full work available at URL: https://doi.org/10.1007/s10107-022-01801-y

zbMATH Keywords

polyhedrasequence-independent liftingsubmodular function maximizationmixed 0-1 knapsackmultidimentional lifting

Mathematics Subject Classification ID

Mixed integer programming (90C11) Combinatorial optimization (90C27)

Uses Software

• Gurobi

Cites Work

• Unnamed Item
• Unnamed Item
• A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: strong valid inequalities by sequence-independent lifting
• Maximizing a class of submodular utility functions with constraints
• Maximizing a class of submodular utility functions
• Sequence independent lifting for mixed knapsack problems with GUB constraints
• Polymatroids and mean-risk minimization in discrete optimization
• The submodular knapsack polytope
• Submodularity and valid inequalities in capacitated fixed charge networks
• The 0-1 knapsack problem with a single continuous variable
• A two-stage stochastic programming approach for influence maximization in social networks
• Polyhedral results for a class of cardinality constrained submodular minimization problems
• Maximizing expected utility over a knapsack constraint
• Sequence independent lifting in mixed integer programming
• Joint chance-constrained programs and the intersection of mixing sets through a submodularity lens
• An exact method for constrained maximization of the conditional value-at-risk of a class of stochastic submodular functions
• Submodular functions and optimization.
• Dynamic Assortment Optimization with a Multinomial Logit Choice Model and Capacity Constraint
• Integer Programming
• Sequence Independent Lifting for Mixed-Integer Programming
• An analysis of approximations for maximizing submodular set functions—I
• Valid Inequalities and Superadditivity for 0–1 Integer Programs
• Sequence Independent Lifting for the Set of Submodular Maximization Problem
• Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems
• Maximizing a Class of Utility Functions Over the Vertices of a Polytope
• Path Cover and Path Pack Inequalities for the Capacitated Fixed-Charge Network Flow Problem
• A Framework to Derive Multidimensional Superadditive Lifting Functions and Its Applications
• Computational Geometric Approach to Submodular Function Minimization for Multiclass Queueing Systems

This page was built for publication: Sequence independent lifting for a set of submodular maximization problems