A cut-and-branch algorithm for the quadratic knapsack problem
From MaRDI portal
Publication:2673234
DOI10.1016/j.disopt.2020.100579OpenAlexW1464660497MaRDI QIDQ2673234
Adam N. Letchford, Franklin Djeumou Fomeni, Konstantinos Kaparis
Publication date: 9 June 2022
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://eprints.lancs.ac.uk/id/eprint/141820/1/qkp2.pdf
Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Quadratic programming (90C20) Combinatorial optimization (90C27) Boolean programming (90C09)
Related Items
The Boolean Quadric Polytope, Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems, A lifted-space dynamic programming algorithm for the quadratic knapsack problem, A general purpose exact solution method for mixed integer concave minimization problems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Asymptotic behavior of the quadratic knapsack problem
- An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem
- The quadratic knapsack problem -- a survey
- The Boolean quadratic polytope: Some characteristics, facets and relatives
- Linear programming for the \(0-1\) quadratic knapsack problem
- Min-cut clustering
- On the \(0/1\) knapsack polytope
- A semidefinite programming approach to the quadratic knapsack problem
- Sequence independent lifting in mixed integer programming
- On lifted cover inequalities: a new lifting procedure with unusual properties
- Cutting planes for RLT relaxations of mixed 0-1 polynomial programs
- A new family of facet defining inequalities for the maximum edge-weighted clique problem
- Separation algorithms for 0-1 knapsack polytopes
- Using a Mixed Integer Programming Tool for Solving the 0–1 Quadratic Knapsack Problem
- Solution of Large Quadratic Knapsack Problems Through Aggressive Reduction
- A Dynamic Programming Heuristic for the Quadratic Knapsack Problem
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Solving Large-Scale Zero-One Linear Programming Problems
- Quadratic knapsack problems
- Faces for a linear inequality in 0–1 variables
- Facets of the knapsack polytope
- Exact Solution of the Quadratic Knapsack Problem
- Technical Note—Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program
- Construction de facettes pour le polytope du sac-à-dos quadratique en 0-1
- Geometry of cuts and metrics