Construction de facettes pour le polytope du sac-à-dos quadratique en 0-1

DOI10.1051/ro:2004008zbMath1092.90030OpenAlexW2139299787MaRDI QIDQ5479831

Olivier Boyer, Alain Faye

Publication date: 11 July 2006

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=RO_2003__37_4_249_0

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) (n)-dimensional polytopes (52B11) Nonlinear programming (90C30) Boolean programming (90C09)

Related Items

A cut-and-branch algorithm for the quadratic knapsack problem

Cites Work

• Unnamed Item
• Unnamed Item
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Linear programming for the \(0-1\) quadratic knapsack problem
• Lagrangean methods for the 0-1 quadratic knapsack problem
• Min-cut clustering
• Cardinality constrained Boolean quadratic polytope
• A semidefinite programming approach to the quadratic knapsack problem
• A new upper bound for the 0-1 quadratic knapsack problem
• An \(O(n \log n)\) procedure for identifying facets of the knapsack polytope.
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• Lifting the facets of zero–one polytopes
• Computing Lower Bounds for the Quadratic Assignment Problem with an Interior Point Algorithm for Linear Programming
• Decomposition and linearization for 0-1 quadratic programming