A fast branch-and-bound algorithm for non-convex quadratic integer optimization subject to linear constraints using ellipsoidal relaxations

DOI10.1016/j.orl.2015.05.001zbMath1408.90219OpenAlexW216476246MaRDI QIDQ1785386

Laura Palagi, Christoph Buchheim, Marianna De Santis

Publication date: 28 September 2018

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

Full work available at URL: http://hdl.handle.net/11573/839791

zbMATH Keywords

global optimizationinteger programmingquadratic programming

Mathematics Subject Classification ID

Integer programming (90C10) Nonconvex programming, global optimization (90C26) Quadratic programming (90C20)

Related Items

A decision space algorithm for multiobjective convex quadratic integer optimization, Cost-optimal constrained correlation clustering via weighted partial maximum satisfiability, Extensions on ellipsoid bounds for quadratic integer programming

Uses Software

• CPLEX

Cites Work

• Semidefinite relaxations for non-convex quadratic mixed-integer programming
• Reduced RLT representations for nonconvex polynomial programming problems
• The generalized trust region subproblem
• A reformulation-linearization technique for solving discrete and continuous nonconvex problems
• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• A branch and bound algorithm for general mixed-integer quadratic programs based on quadratic convex relaxation
• An Exact Algorithm for Nonconvex Quadratic Integer Minimization Using Ellipsoidal Relaxations
• Trust Region Methods