The submodular knapsack polytope
From MaRDI portal
Publication:1040079
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
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
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
