Faster exact solution of sparse maxcut and QUBO problems
From MaRDI portal
Abstract: The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems -- by using mathematical programming techniques on digital computers. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse MaxCut and QUBO instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.
Recommendations
- Mathematical programming models and exact algorithms
- Improved semidefinite bounding procedure for solving max-cut problems to optimality
- QUBO software
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations
Cites work
- \texttt{MADAM}: a parallel exact solver for max-cut based on semidefinite programming and ADMM
- Adaptive memory tabu search for binary quadratic programs
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- An Efficient Heuristic Procedure for Partitioning Graphs
- BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints
- BiqCrunch: a semidefinite branch-and-bound method for solving binary quadratic problems
- Engineering Kernelization for Maximum Cut
- Exact Facetial Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization
- Experiments in quadratic 0-1 programming
- scientific article; zbMATH DE number 7525500 (Why is no real title available?)
- scientific article; zbMATH DE number 5937963 (Why is no real title available?)
- scientific article; zbMATH DE number 7124428 (Why is no real title available?)
- scientific article; zbMATH DE number 3249560 (Why is no real title available?)
- Implications, conflicts, and reductions for Steiner trees
- Lifting and separation procedures for the cut polytope
- Logical and inequality implications for reducing the size and difficulty of quadratic unconstrained binary optimization problems
- On the cut polytope
- Presolve Reductions in Mixed Integer Programming
- QPLIB: a library of quadratic programming instances
- Quantum annealing versus digital computing. An experimental comparison
- Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs
- Reducibility among combinatorial problems
- Roof duality, complementation and persistency in quadratic 0–1 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
- What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO
Cited in
(15)- BiqCrunch: a semidefinite branch-and-bound method for solving binary quadratic problems
- scientific article; zbMATH DE number 2159019 (Why is no real title available?)
- Mathematical programming models and exact algorithms
- QUBO software
- Exact Facetial Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization
- What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO
- Optimal design of line replaceable units
- A universal quantum algorithm for weighted maximum cut and Ising problems
- Solving MaxCut with quantum imaginary time evolution
- The set partitioning problem in a quantum context
- McSparse: exact solutions of sparse maximum cut and sparse unconstrained binary quadratic optimization problems
- Quantum computing for discrete optimization: a highlight of three technologies
- Enhanced open-source scatter search algorithm for solving quadratic unconstrained binary optimization problems
- A family of spanning-tree formulations for the maximum cut problem
- A preprocessing technique for quadratic unconstrained binary optimization
This page was built for publication: Faster exact solution of sparse maxcut and QUBO problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6095734)
