Mixed linear and semidefinite programming for combinatorial and quadratic optimization

DOI10.1080/10556789908805761zbMath0973.90055OpenAlexW1967781705MaRDI QIDQ4504791

Yinyu Ye, Steven Benson, Xiong Zhang

Publication date: 10 December 2001

Published in: Optimization Methods and Software (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/10556789908805761

zbMATH Keywords

maximum cutrandomized algorithmgraph bisectionsemidefinite relaxationbounded QPdual potential reduction algorithm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Semidefinite programming (90C22) Quadratic programming (90C20) Combinatorial optimization (90C27) Software, source code, etc. for problems pertaining to operations research and mathematical programming (90-04)

Related Items

Metaheuristic Algorithms, Simple solution methods for separable mixed linear and quadratic knapsack problem, A discrete dynamic convexized method for the max-cut problem, Randomized heuristics for the Max-Cut problem, Positive semidefinite relaxations for distance geometry problems., An inexact dual logarithmic barrier method for solving sparse semidefinite programs, LFTB: an efficient algorithm to bound linear fractional transformations

Uses Software

• SDPA
• COL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The quasi-isometry classification of lattices in semisimple Lie groups
• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Solving Graph Bisection Problems with Semidefinite Programming
• A Spectral Bundle Method for Semidefinite Programming
• Semidefinite Programming