The submodular knapsack polytope

DOI10.1016/j.disopt.2009.03.002zbMath1179.90270OpenAlexW2037187765MaRDI QIDQ1040079

Vishnu Narayanan, Atamtürk, Alper

Publication date: 23 November 2009

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2009.03.002

zbMATH Keywords

branch-and-cut algorithmssubmodular functionsconic integer programmingprobabilistic knapsacks

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items

Recursive central rounding for mixed integer programs, Chance-Constrained Binary Packing Problems, A note on the implications of approximate submodularity in discrete optimization, Lifting for conic mixed-integer programming, Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints, Submodularity in Conic Quadratic Mixed 0–1 Optimization, Lifting of probabilistic cover inequalities, Maximizing a class of submodular utility functions with constraints, Supermodular covering knapsack polytope, Polyhedral results for a class of cardinality constrained submodular minimization problems, Ambiguous Chance-Constrained Binary Programs under Mean-Covariance Information, Simplex QP-based methods for minimizing a conic quadratic objective over polyhedra, Optimization algorithms for the disjunctively constrained knapsack problem, Robustness Concepts for Knapsack and Network Design Problems Under Data Uncertainty, Robust optimization-based heuristic algorithm for the chance-constrained knapsack problem using submodularity, Successive Quadratic Upper-Bounding for Discrete Mean-Risk Minimization and Network Interdiction, Minimizing ratio of monotone non-submodular functions, Sequence independent lifting for a set of submodular maximization problems, A combinatorial cut-and-lift procedure with an application to 0-1 second-order conic programming

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cover and pack inequalities for (mixed) integer programming
• Polymatroids and mean-risk minimization in discrete optimization
• Stochastic spanning tree problem
• The ellipsoid method and its consequences in combinatorial optimization
• Some simplified NP-complete graph problems
• Linear programming for the \(0-1\) quadratic knapsack problem
• Robust solutions of uncertain linear programs
• On the facets of the mixed-integer knapsack polyhedron
• A note on maximizing a submodular set function subject to a knapsack constraint
• A semidefinite programming approach to the quadratic knapsack problem
• The nonlinear knapsack problem - algorithms and applications
• On the supermodular knapsack problem
• Robust optimization-methodology and applications
• A nonlinear knapsack problem
• Cuts for mixed 0-1 conic programming
• Chance-Constrained Programming
• Worst-Case Value-At-Risk and Robust Portfolio Optimization: A Conic Programming Approach
• Maximizing Classes of Two-Parameter Objectives Over Matroids
• (1,k)-configurations and facets for packing problems
• Faces for a linear inequality in 0–1 variables
• Facet of regular 0–1 polytopes
• Facets of the knapsack polytope
• An Algorithm for Nonlinear Knapsack Problems
• An analysis of approximations for maximizing submodular set functions—I
• Facets of the Knapsack Polytope From Minimal Covers
• Introduction to Stochastic Programming
• Exact Solution of the Quadratic Knapsack Problem
• An Efficient Method for a Class of Continuous Nonlinear Knapsack Problems
• Optimal Inequalities in Probability Theory: A Convex Optimization Approach