A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
From MaRDI portal
Publication:646707
DOI10.1007/S10479-008-0481-4zbMath1225.90144OpenAlexW1994932713MaRDI QIDQ646707
Frauke Liers, Miguel F. Anjos, Bissan Ghaddar
Publication date: 17 November 2011
Published in: Annals of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10479-008-0481-4
Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)
Related Items (28)
SDP-based bounds for graph partition via extended ADMM ⋮ A computational study for bilevel quadratic programs using semidefinite relaxations ⋮ An extended edge-representative formulation for the \(K\)-partitioning problem ⋮ Computational study of valid inequalities for the maximum \(k\)-cut problem ⋮ Conic approximation to quadratic optimization with linear complementarity constraints ⋮ Exploiting sparsity for the min \(k\)-partition problem ⋮ On semidefinite programming relaxations of maximum \(k\)-section ⋮ Computational study of a branching algorithm for the maximum \(k\)-cut problem ⋮ SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering ⋮ Orbitopal fixing ⋮ New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph ⋮ An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem ⋮ A semidefinite relaxation based global algorithm for two-level graph partition problem ⋮ A branch-and-bound algorithm for solving max-\(k\)-cut problem ⋮ Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem ⋮ A framework for solving mixed-integer semidefinite programs ⋮ An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming ⋮ A two-level graph partitioning problem arising in mobile wireless communications ⋮ A multiple search operator heuristic for the max-k-cut problem ⋮ Projection results for the \(k\)-partition problem ⋮ A branch‐and‐price approach to k‐clustering minimum biclique completion problem ⋮ Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints ⋮ Semidefinite relaxations for partitioning, assignment and ordering problems ⋮ SDP Relaxations for Some Combinatorial Optimization Problems ⋮ Computational Approaches to Max-Cut ⋮ Robust Critical Node Selection by Benders Decomposition ⋮ Semidefinite relaxations for partitioning, assignment and ordering problems ⋮ New Formulations for the Conflict Resolution Problem in the Scheduling of Television Commercials
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
- Minimizing breaks by maximizing cuts.
- Graph partitioning using linear and semidefinite programming
- On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
- Facets of the \(k\)-partition polytope
- The partition problem
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- On the Shannon capacity of a graph
- New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
- Realignment in the National Football League: Did they do it right?
- CSDP, A C library for semidefinite programming
- On the cut polytope
- Orbitopal Fixing
- A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations
- Geometry of cuts and metrics
This page was built for publication: A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
