Improved semidefinite bounding procedure for solving max-cut problems to optimality
From MaRDI portal
Publication:2436651
DOI10.1007/s10107-012-0594-zzbMath1285.90030MaRDI QIDQ2436651
Jérôme Malick, Nathan Krislock, Frédéric Roupin
Publication date: 25 February 2014
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-012-0594-z
90C22: Semidefinite programming
90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C27: Combinatorial optimization
Related Items
Global convergence of the alternating projection method for the Max-Cut relaxation problem, The Boolean Quadric Polytope, Mathematical Programming Models and Exact Algorithms, An Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event Seating, Semidefinite Approaches for MIQCP: Convex Relaxations and Practical Methods, BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints, Partial Lasserre relaxation for sparse Max-Cut, An entropy-regularized ADMM for binary quadratic programming, A new global algorithm for max-cut problem with chordal sparsity, Solving SDP relaxations of max-cut problem with large number of hypermetric inequalities by L-BFGS-B, Computational results of a semidefinite branch-and-bound algorithm for \(k\)-cluster, Computational study of valid inequalities for the maximum \(k\)-cut problem, On solving a large-scale problem on facility location and customer assignment with interaction costs along a time horizon, Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results, \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, Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints, Theoretical and computational study of several linearisation techniques for binary quadratic problems, On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study, Computational study of a branching algorithm for the maximum \(k\)-cut problem, A matrix nonconvex relaxation approach to unconstrained binary polynomial programs, Discrete Optimization with Decision Diagrams, From Graph Orientation to the Unweighted Maximum Cut, Exact Solution Methods for the k-Item Quadratic Knapsack Problem, Continuous Approaches to the Unconstrained Binary Quadratic Problems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Reflections on generating (disjunctive) cuts
- Handbook on semidefinite, conic and polynomial optimization
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
- The spherical constraint in Boolean quadratic programs
- Quadratic programming with one negative eigenvalue is NP-hard
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
- Convex analysis and nonlinear optimization. Theory and examples
- A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
- Gap inequalities for the cut polytope
- Solving \(k\)-cluster problems to optimality with semidefinite programming
- Computational aspects of a branch and bound algorithm for quadratic zero- one programming
- Introduction to Semidefinite, Conic and Polynomial Optimization
- Computational Approaches to Max-Cut
- Remark on “algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound constrained optimization”
- LAPACK Users' Guide
- Algorithm 778: L-BFGS-B
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- A Limited Memory Algorithm for Bound Constrained Optimization
- Reducibility among Combinatorial Problems
- Numerical optimization. Theoretical and practical aspects. Transl. from the French
- Benchmarking optimization software with performance profiles.
