A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
From MaRDI portal
Publication:1905964
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
theta functionquadratic assignmentgraph partitioningsemidefinite programsLagrangian dualityconcave quadratic maximizationmax-clique problemminmax eigenvalue problemsparametric trust region problemsrelaxations of \((0,1)\)-quadratic programming problems
Related Items
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
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 algorithm1
- 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
