A recipe for semidefinite relaxation for (0,1)-quadratic programming
From MaRDI portal
Publication:1905964
DOI10.1007/BF01100205zbMATH Open0843.90088OpenAlexW2912475851MaRDI QIDQ1905964FDOQ1905964
Authors: Svatopluk Poljak, Franz Rendl, 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
Recommendations
- scientific article; zbMATH DE number 1380758
- Semidefinite programming relaxation for nonconvex quadratic programs
- A new semidefinite relaxation for \(L_{1}\)-constrained quadratic
- Semidefinite relaxation and nonconvex quadratic optimization
- Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons
- On equivalence of semidefinite relaxations for quadratic matrix programming
- Convex Relaxations of (0, 1)-Quadratic Programming
- Further Results on Approximating Nonconvex Quadratic Optimization by Semidefinite Programming Relaxation
- Semidefinite relaxations for non-convex quadratic mixed-integer programming
graph partitioningsemidefinite programstheta functionLagrangian dualityquadratic assignmentconcave quadratic maximizationmax-clique problemminmax eigenvalue problemsparametric trust region problemsrelaxations of \((0,1)\)-quadratic programming problems
Cites Work
- Computing a Trust Region Step
- On the Shannon capacity of a graph
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- Title not available (Why is that?)
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Laplacian eigenvalues and the maximum cut problem
- Convex Relaxations of (0, 1)-Quadratic Programming
- The sandwich theorem
- Semidefinite programming relaxations for the quadratic assignment problem
- .878-approximation algorithms for MAX CUT and MAX 2SAT
- Title not available (Why is that?)
- Roof duality, complementation and persistency in quadratic 0–1 optimization
- A comparison of the Delsarte and Lovász bounds
- Title not available (Why is that?)
- Some applications of optimization in matrix theory
- On Some Problems of Lovász Concerning the Shannon Capacity of a Graph
- On the equivalence between roof duality and Lagrangian duality for unconstrained \(0\)-\(1\) quadratic programming problems
- A projection technique for partitioning the nodes of a graph
- A tight bound for the boolean quadratic optimization problem and its use in a branch and bound algorithm1
- Remarks on a difficult test problem for quadratic boolean programming
Cited In (82)
- Some experiences with solving semidefinite programming relaxations of binary quadratic optimization models in computational biology
- The random QUBO
- A Derivation of Lovász' Theta via Augmented Lagrange Duality
- A guide to conic optimisation and its applications
- Distributed resource allocation with binary decisions via Newton-like neural network dynamics
- Ellipsoidal relaxations of the stable set problem: theory and algorithms
- T-positive semidefiniteness of third-order symmetric tensors and T-semidefinite programming
- Invariants of SDP exactness in quadratic programming
- \texttt{EXPEDIS}: an exact penalty method over discrete sets
- Bounds for random binary quadratic programs
- A semi-supervised random vector functional-link network based on the transductive framework
- Using two-dimensional projections for stronger separation and propagation of bilinear terms
- Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems
- A note on semidefinite relaxation for 0-1 quadratic knapsack problems
- A New Relaxation in Conic Form for the Euclidean Steiner Problem in ℜ
- Fixing variables in semidefinite relaxations
- A note on representations of linear inequalities in non-convex mixed-integer quadratic programs
- Lagrangian decomposition of block-separable mixed-integer all-quadratic programs
- Valid inequalities for quadratic optimisation with domain constraints
- Partial Lagrangian relaxation for general quadratic programming
- A distributed continuous-time method for non-convex QCQPs
- Mixed linear and semidefinite programming for combinatorial and quadratic optimization
- Convex Relaxations of (0, 1)-Quadratic Programming
- Second order cone programming relaxation of nonconvex quadratic optimization problems
- Using the eigenvalue relaxation for binary least-squares estimation problems
- Improved semidefinite bounding procedure for solving max-cut problems to optimality
- A fast branch-and-bound algorithm for non-convex quadratic integer optimization subject to linear constraints using ellipsoidal relaxations
- A linearization framework for unconstrained quadratic (0-1) problems
- Semidefinite programming relaxations for the graph partitioning problem
- The omnipresence of Lagrange
- A new approach to the stable set problem based on ellipsoids
- Conic approximation to nonconvex quadratic programming with convex quadratic constraints
- Unbounded convex sets for non-convex mixed-integer quadratic programming
- A strong conic quadratic reformulation for machine-job assignment with controllable processing times
- Copositive and semidefinite relaxations of the quadratic assignment problem
- Enhancing semidefinite relaxation for quadratically constrained quadratic programming via penalty methods
- Semidefinite programming for discrete optimization and matrix completion problems
- Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem
- Best ellipsoidal relaxation to solve a nonconvex problem.
- Ellipsoid bounds for convex quadratic integer programming
- Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons
- Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
- On the gap between the quadratic integer programming problem and its semidefinite relaxation
- Enclosing ellipsoids and elliptic cylinders of semialgebraic sets and their application to error bounds in polynomial optimization
- Parametric Lagrangian dual for the binary quadratic programming problem
- Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems
- Computational approaches to MAX-cut
- A continuous approch for globally solving linearly constrained quadratic
- Randomized heuristics for the Max-Cut problem
- An exact solution method for quadratic matching: the one-quadratic-term technique and generalisations
- Computing exact solution to nonlinear integer programming: convergent Lagrangian and objective level cut method
- 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
- Semidefinite programming and combinatorial optimization
- An evaluation of semidefinite programming based approaches for discrete lot-sizing problems
- Intersection cuts for nonlinear integer programming: convexification techniques for structured sets
- Generating cutting planes for the semidefinite relaxation of quadratic programs
- Nonconvex quadratically constrained quadratic programming: Best D.C. Decompositions and their SDP representations
- Exploiting sparsity in primal-dual interior-point methods for semidefinite programming
- Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring
- An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem
- A nonmonotone GRASP
- Computational results of a semidefinite branch-and-bound algorithm for \(k\)-cluster
- On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0--1 quadratic problems leading to quasi-Newton methods
- Fixing Variables in Semidefinite Relaxations
- Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
- A projected gradient algorithm for solving the maxcut SDP relaxation
- Copositive realxation for genera quadratic programming
- Copositive relaxation beats Lagrangian dual bounds in quadratically and linearly constrained quadratic optimization problems
- On equivalence of semidefinite relaxations for quadratic matrix programming
- On duality gap in binary quadratic programming
- New bounds on the unconstrained quadratic integer programming problem
- A fresh variational-analysis look at the positive semidefinite matrices world
- The spherical constraint in Boolean quadratic programs
- The Boolean quadric polytope
- Mathematical optimization ideas for biodiversity conservation
- SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances
- On Lagrangian relaxation of quadratic matrix constraints
- Using quadratic convex reformulation to tighten the convex relaxation of a quadratic program with complementarity constraints
- The equivalence of semidefinite relaxations of polynomial 0-1 and \(\pm 1\) programs via scaling
- ``Miniaturized linearizations for quadratic 0/1 problems
- A compact variant of the QCR method for quadratically constrained quadratic \(0-1\) programs
Uses Software
This page was built for publication: A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1905964)
