Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
From MaRDI portal
Publication:2583135
DOI10.1007/s10107-005-0661-9zbMath1085.90044OpenAlexW2085647652WikidataQ59196591 ScholiaQ59196591MaRDI QIDQ2583135
Gerald Gruber, Renata Sotirov, Ilse Fischer, Franz Rendl
Publication date: 13 January 2006
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-005-0661-9
Related Items
An Improved Interior-Point Cutting-Plane Method for Binary Quadratic Optimization, On handling cutting planes in interior-point methods for solving semi-definite relaxations of binary quadratic optimization problems, Mathematical Programming Models and Exact Algorithms, Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations, A survey for the quadratic assignment problem, Dynamic bundle methods, Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem, A computational study and survey of methods for the single-row facility layout problem, Bounds for the quadratic assignment problem using the bundle method, Semidefinite relaxations of ordering problems, SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances, \texttt{EXPEDIS}: an exact penalty method over discrete sets, Partial Lasserre relaxation for sparse Max-Cut, A semidefinite optimization approach to the target visitation problem, Local Search Based on Genetic Algorithms, A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring, A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems, Using general triangle inequalities within quadratic convex reformulation method, \texttt{MADAM}: a parallel exact solver for max-cut based on semidefinite programming and ADMM, A branch-and-bound algorithm for solving max-\(k\)-cut problem, Mathematical optimization approaches for facility layout problems: the state-of-the-art and future research directions, Exploring the relationship between max-cut and stable set relaxations, Semidefinite relaxations for partitioning, assignment and ordering problems, Recent Progress in Interior-Point Methods: Cutting-Plane Algorithms and Warm Starts, Computational Approaches to Max-Cut, Semidefinite relaxations for partitioning, assignment and ordering problems, Mixing convex-optimization bounds for maximum-entropy sampling, Spectral bounds for the maximum cut problem, From Graph Orientation to the Unweighted Maximum Cut, Exact Solution Methods for the k-Item Quadratic Knapsack Problem, Spectral bounds for graph partitioning with prescribed partition sizes
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
- Bounds for the quadratic assignment problem using the bundle method
- Experiments in quadratic 0-1 programming
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
- Laplacian eigenvalues and the maximum cut problem
- The volume algorithm revisited: relation with bundle methods
- Graph partitioning using linear and semidefinite programming
- A computational study of a gradient-based log-barrier algorithm for a class of large-scale SDPs
- The volume algorithm: Producing primal solutions with a subgradient method
- Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring
- A cutting plane algorithm for convex programming that uses analytic centers
- New variants of bundle methods
- Complexity estimates of some cutting plane methods based on the analytic barrier
- Methods of descent for nondifferentiable optimization
- Computational aspects of a branch and bound algorithm for quadratic zero- one programming
- Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs
- A restricted Lagrangean approach to the traveling salesman problem
- Decomposition and Nondifferentiable Optimization with the Projective Algorithm
- Cones of Matrices and Set-Functions and 0–1 Optimization
- A Version of the Bundle Idea for Minimizing a Nonsmooth Function: Conceptual Idea, Convergence Analysis, Numerical Results
- On the Shannon capacity of a graph
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- A study of search directions in primal-dual interior-point methods for semidefinite programming
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- Generalized Bundle Methods
- Nonpolyhedral Relaxations of Graph-Bisection Problems
- An Interior-Point Method for Semidefinite Programming
- The Traveling-Salesman Problem and Minimum Spanning Trees
- Lower Bounds for the Partitioning of Graphs
- The omnipresence of Lagrange
