A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming

DOI10.1007/BF01100205zbMath0843.90088OpenAlexW2912475851MaRDI QIDQ1905964

Franz Rendl, Svatopluk Poljak, Henry Wolkowicz

Publication date: 19 August 1996

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01100205

zbMATH Keywords

theta functionquadratic assignmentgraph partitioningsemidefinite programsLagrangian dualityconcave quadratic maximizationmax-clique problemminmax eigenvalue problemsparametric trust region problemsrelaxations of \((0,1)\)-quadratic programming problems

Mathematics Subject Classification ID

Quadratic programming (90C20) Boolean programming (90C09)

Related Items (74)

A strong conic quadratic reformulation for machine-job assignment with controllable processing times ⋮ The Boolean Quadric Polytope ⋮ The Random QUBO ⋮ Using the eigenvalue relaxation for binary least-squares estimation problems ⋮ A New Relaxation in Conic Form for the Euclidean Steiner Problem in ℜ ⋮ A Derivation of Lovász' Theta via Augmented Lagrange Duality ⋮ Generating cutting planes for the semidefinite relaxation of quadratic programs ⋮ Partial Lagrangian relaxation for general quadratic programming ⋮ A nonmonotone GRASP ⋮ Computational results of a semidefinite branch-and-bound algorithm for \(k\)-cluster ⋮ Exploiting sparsity in primal-dual interior-point methods for semidefinite programming ⋮ Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem ⋮ On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0--1 quadratic problems leading to quasi-Newton methods ⋮ SOME EXPERIENCES WITH SOLVING SEMIDEFINITE PROGRAMMING RELAXATIONS OF BINARY QUADRATIC OPTIMIZATION MODELS IN COMPUTATIONAL BIOLOGY ⋮ An efficient combined DCA and B\&B using DC/SDP relaxation for globally solving binary quadratic programs ⋮ Efficient Use of Semidefinite Programming for Selection of Rotamers in Protein Conformations ⋮ SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances ⋮ \texttt{EXPEDIS}: an exact penalty method over discrete sets ⋮ Ellipsoidal Relaxations of the Stable Set Problem: Theory and Algorithms ⋮ Ellipsoid Bounds for Convex Quadratic Integer Programming ⋮ An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem ⋮ Using Two-Dimensional Projections for Stronger Separation and Propagation of Bilinear Terms ⋮ Invariants of SDP exactness in quadratic programming ⋮ Enclosing ellipsoids and elliptic cylinders of semialgebraic sets and their application to error bounds in polynomial optimization ⋮ A fresh variational-analysis look at the positive semidefinite matrices world ⋮ Unbounded convex sets for non-convex mixed-integer quadratic programming ⋮ Improved semidefinite bounding procedure for solving max-cut problems to optimality ⋮ Bounds for Random Binary Quadratic Programs ⋮ Nonconvex quadratically constrained quadratic programming: Best D.C. Decompositions and their SDP representations ⋮ Best ellipsoidal relaxation to solve a nonconvex problem. ⋮ On duality gap in binary quadratic programming ⋮ Semidefinite programming relaxations for the graph partitioning problem ⋮ Using quadratic convex reformulation to tighten the convex relaxation of a quadratic program with complementarity constraints ⋮ A compact variant of the QCR method for quadratically constrained quadratic \(0-1\) programs ⋮ New bounds on the unconstrained quadratic integer programming problem ⋮ The spherical constraint in Boolean quadratic programs ⋮ A note on representations of linear inequalities in non-convex mixed-integer quadratic programs ⋮ A distributed continuous-time method for non-convex QCQPs ⋮ Enhancing semidefinite relaxation for quadratically constrained quadratic programming via penalty methods ⋮ A guide to conic optimisation and its applications ⋮ Valid inequalities for quadratic optimisation with domain constraints ⋮ Computing exact solution to nonlinear integer programming: convergent Lagrangian and objective level cut method ⋮ A New Approach to the Stable Set Problem Based on Ellipsoids ⋮ An exact solution method for quadratic matching: the one-quadratic-term technique and generalisations ⋮ Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems ⋮ Copositive realxation for genera quadratic programming ⋮ Semidefinite programming and combinatorial optimization ⋮ Semidefinite programming for discrete optimization and matrix completion problems ⋮ A continuous approch for globally solving linearly constrained quadratic ⋮ A projected gradient algorithm for solving the maxcut SDP relaxation ⋮ Second order cone programming relaxation of nonconvex quadratic optimization problems ⋮ Lagrangian decomposition of block-separable mixed-integer all-quadratic programs ⋮ On the gap between the quadratic integer programming problem and its semidefinite relaxation ⋮ Randomized heuristics for the Max-Cut problem ⋮ Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring ⋮ Parametric Lagrangian dual for the binary quadratic programming problem ⋮ Conic approximation to nonconvex quadratic programming with convex quadratic constraints ⋮ Distributed resource allocation with binary decisions via Newton-like neural network dynamics ⋮ Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons ⋮ The omnipresence of Lagrange ⋮ T-positive semidefiniteness of third-order symmetric tensors and T-semidefinite programming ⋮ A fast branch-and-bound algorithm for non-convex quadratic integer optimization subject to linear constraints using ellipsoidal relaxations ⋮ A semi-supervised random vector functional-link network based on the transductive framework ⋮ Intersection cuts for nonlinear integer programming: convexification techniques for structured sets ⋮ Computational Approaches to Max-Cut ⋮ An evaluation of semidefinite programming based approaches for discrete lot-sizing problems ⋮ Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem ⋮ A linearization framework for unconstrained quadratic (0-1) problems ⋮ Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems ⋮ Copositive Relaxation Beats Lagrangian Dual Bounds in Quadratically and Linearly Constrained Quadratic Optimization Problems ⋮ Mixed linear and semidefinite programming for combinatorial and quadratic optimization ⋮ Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem ⋮ Mathematical optimization ideas for biodiversity conservation ⋮ ``Miniaturized linearizations for quadratic 0/1 problems

Uses Software

• GQTPAR

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some applications of optimization in matrix theory
• On the equivalence between roof duality and Lagrangian duality for unconstrained \(0\)-\(1\) quadratic programming problems
• Laplacian eigenvalues and the maximum cut problem
• The sandwich theorem
• Semidefinite programming relaxations for the quadratic assignment problem
• A projection technique for partitioning the nodes of a graph
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• .879-approximation algorithms for MAX CUT and MAX 2SAT
• Computing a Trust Region Step
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• A tight bound for the boolean quadratic optimization problem and its use in a branch and bound algorithm¹
• A comparison of the Delsarte and Lovász bounds
• Cones of Matrices and Set-Functions and 0–1 Optimization
• On the Shannon capacity of a graph
• On Some Problems of Lovász Concerning the Shannon Capacity of a Graph
• Remarks on a difficult test problem for quadratic boolean programming
• Convex Relaxations of (0, 1)-Quadratic Programming

This page was built for publication: A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming