Notoriously hard (mixed-)binary QPs: empirical evidence on new completely positive approaches

DOI10.1007/S10287-018-0337-6MaRDI QIDQ2010370zbMATH OpenOpenAlexFDO

Authors Immanuel M. Bomze, Jianqiang Cheng, Peter J. C. Dickinson, Abdel Lisser, Jia Liu

Publication date 27 November 2019

Published in Computational Management Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10287-018-0337-6

zbMATH Keywords

nonconvex optimizationquadratic assignment problemnonlinear optimizationquadratic optimizationpenalization methodcompletely positivereformulationscopositivitymul tidimensional knapsack problem

Mathematics Subject Classification ID

Quadratic programming (90C20) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30) Operations research and management science (90Bxx)

Recommendations

• A fresh CP look at mixed-binary QPs: new formulations and relaxations
• Inner approximations of completely positive reformulations of mixed binary quadratic programs: a unified analysis
• Reformulation of the quadratic multidimensional knapsack problem as copositive/completely positive programs
• A simplified completely positive reformulation for binary quadratic programs
• A note on Burer's copositive representation of mixed-binary QPs

Cites work

• scientific article; zbMATH DE number 3748742 (Why is no real title available?)
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A fresh CP look at mixed-binary QPs: new formulations and relaxations
• A gentle, geometric introduction to copositive optimization
• An aggregate subgradient method for nonsmooth convex minimization
• An improved characterisation of the interior of the completely positive cone
• Graph implementations for nonsmooth convex programs
• New lower bounds and asymptotics for the cp-rank
• New results on the cp-rank and related properties of co(mpletely) positive matrices
• On copositive programming and standard quadratic optimization problems
• On the computational complexity of membership problems for the completely positive cone and its dual
• On the copositive representation of binary and continuous nonconvex quadratic programs
• Optimizing a polyhedral-semidefinite relaxation of completely positive programs
• QAPLIB - a quadratic assignment problem library
• Simplified copositive and Lagrangian relaxations for linearly constrained quadratic optimization problems in continuous and binary variables
• Some NP-complete problems in quadratic and nonlinear programming
• Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones

Cited in

(1)

• Distributionally Robust Chance Constrained Geometric Optimization

Describes a project that uses

Uses Software

• QAPLIB
• SeDuMi
• OR-Library
• CVX

This page was built for publication: Notoriously hard (mixed-)binary QPs: empirical evidence on new completely positive approaches

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2010370)