Gap inequalities for non-convex mixed-integer quadratic programs

DOI10.1016/j.orl.2011.07.002zbMath1235.90102OpenAlexW2152686051WikidataQ57702176 ScholiaQ57702176MaRDI QIDQ408381

Adam N. Letchford, Laura Galli, Konstantinos Kaparis

Publication date: 5 April 2012

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2011.07.002

zbMATH Keywords

max-cut problempolyhedral combinatoricsmixed-integer nonlinear programming

Mathematics Subject Classification ID

Mixed integer programming (90C11) Nonconvex programming, global optimization (90C26) Quadratic programming (90C20)

Related Items

Linear transformation based solution methods for non-convex mixed integer quadratic programs, The Boolean Quadric Polytope, Unbounded convex sets for non-convex mixed-integer quadratic programming, Complexity results for the gap inequalities for the max-cut problem, A note on representations of linear inequalities in non-convex mixed-integer quadratic programs, Valid inequalities for quadratic optimisation with domain constraints, A note on convex reformulation schemes for mixed integer quadratic programs, Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Enhancing RLT relaxations via a new class of semidefinite cuts
• Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Experiments in quadratic 0-1 programming
• Stronger linear programming relaxations of max-cut
• The cut polytope and the Boolean quadric polytope
• On a positive semidefinite relaxation of the cut polytope
• Exploring the relationship between max-cut and stable set relaxations
• Binary Positive Semidefinite Matrices and Associated Integer Polytopes
• Polyhedral Approaches to Mixed Integer Linear Programming
• Fifty-Plus Years of Combinatorial Integer Programming
• Integer Quadratic Quasi-polyhedra
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
• On the cut polytope
• Nonpolyhedral Relaxations of Graph-Bisection Problems
• On the Facial Structure of the Set of Correlation Matrices
• Geometry of cuts and metrics