Spectral relaxations and branching strategies for global optimization of mixed-integer quadratic programs
From MaRDI portal
Publication:5148407
Abstract: We consider the global optimization of nonconvex quadratic programs and mixed-integer quadratic programs. We present a family of convex quadratic relaxations which are derived by convexifying nonconvex quadratic functions through perturbations of the quadratic matrix. We investigate the theoretical properties of these quadratic relaxations and show that they are equivalent to some particular semidefinite programs. We also introduce novel branching variable selection strategies which can be used in conjunction with the quadratic relaxations investigated in this paper. We integrate the proposed relaxation and branching techniques into the global optimization solver BARON, and test our implementation by conducting numerical experiments on a large collection of problems. Results demonstrate that the proposed implementation leads to very significant reductions in BARON's computational times to solve the test problems.
Recommendations
- SDP-quality bounds via convex quadratic relaxations for global optimization of mixed-integer quadratic programs
- A branch and bound algorithm for general mixed-integer quadratic programs based on quadratic convex relaxation
- Semidefinite relaxations for non-convex quadratic mixed-integer programming
- A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations
- A hybrid LP/NLP paradigm for global optimization relaxations
Cites work
- \(\alpha BB\): A global optimization method for general constrained nonconvex problems
- A hybrid LP/NLP paradigm for global optimization relaxations
- A quadratic assignment formulation of the molecular conformation problem
- A reformulation-linearization technique for solving discrete and continuous nonconvex problems
- A survey for the quadratic assignment problem
- An efficient compact quadratic convex reformulation for general integer quadratic programs
- BARON: A general purpose global optimization software package
- Branching rules revisited
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
- Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2
- Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems with BARON
- Global minimization of indefinite quadratic problems
- Global optimization of general non-convex problems with intermediate bilinear substructures
- Global optimization of mixed-integer nonlinear programs: a theoretical and computational study
- Global optimization of nonconvex problems with multilinear intermediates
- Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods
- scientific article; zbMATH DE number 4070633 (Why is no real title available?)
- scientific article; zbMATH DE number 757676 (Why is no real title available?)
- scientific article; zbMATH DE number 3335677 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
- LAPACK Users' Guide
- Partial Lagrangian relaxation for general quadratic programming
- Semidefinite relaxations for non-convex quadratic mixed-integer programming
- Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons
- Undominated d.c. decompositions of quadratic functions and applications to branch-and-bound approaches
Cited in
(10)- A hybrid LP/NLP paradigm for global optimization relaxations
- SDP-quality bounds via convex quadratic relaxations for global optimization of mixed-integer quadratic programs
- A computational study on QP problems with general linear constraints
- New bounds for nonconvex quadratically constrained quadratic programming
- Improved convex and concave relaxations of composite bilinear forms
- Spatial algorithm for mixed integer generalized affine multiplicative problems
- Solving continuous and discrete nonlinear programs with BARON
- Globally solving concave quadratic programs via doubly nonnegative relaxation
- Fix and bound: an efficient approach for solving large-scale quadratic programming problems with box constraints
- Simultaneous convexification for the planar obnoxious facility location problem
This page was built for publication: Spectral relaxations and branching strategies for global optimization of mixed-integer quadratic programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5148407)
