What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO

Though empirical testing is broadly used to evaluate heuristics, there are shortcomings with how it is often applied in practice. In a systematic review of Max-Cut and quadratic unconstrained binar...

• Publication year

  2018

• Venue

  INFORMS journal on computing

• Publication date

  2018-08-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1287/IJOC.2017.0798
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Points of Significance: Classification and regression trees

  2017influential reference
• Towards objective measures of algorithm performance across instance space

  2014cited by this paper
• DISTINGUISH HARD INSTANCES OF AN NP-HARD PROBLEM USING MACHINE LEARNING

  2013cited by this paper
• Selecting suitable solution strategies for Classes of graph coloring instances using data mining

  2013cited by this paper
• Estimation of Distribution Algorithm for the Max-Cut Problem

  2013influential reference
• Measuring instance difficulty for combinatorial optimization problems

  2012cited by this paper
• A Guide to Experimental Algorithmics

  2012cited by this paper
• Generalising Algorithm Performance in Instance Space: A Timetabling Case Study

  2011cited by this paper
• Simple algorithm portfolio for SAT

  2011cited by this paper
• Discovering the suitability of optimisation algorithms by learning from evolved instances

  2011influential reference
• A Classification of Hyper-heuristic Approaches

  2010cited by this paper
• Comparison of Metaheuristics

  2010cited by this paper
• Optimisation and Generalisation: Footprints in Instance Space

  2010cited by this paper
• Experimental Research in Evolutionary Computation - The New Experimentalism

  2010cited by this paper
• Diversification-driven tabu search for unconstrained binary quadratic problems

  2010cited by this paper
• Understanding TSP Difficulty by Learning from Evolved Instances

  2010influential reference
• A hybrid metaheuristic approach to solving the UBQP problem

  2010cited by this paper
• A self-adaptive multi-engine solver for quantified Boolean formulas

  2009cited by this paper
• Edge direction and the structure of networks

  2009cited by this paper
• Systematic literature reviews in software engineering - A systematic literature review

  2009cited by this paper
• Advanced Scatter Search for the Max-Cut Problem

  2009cited by this paper
• Hybridizing the cross-entropy method: An application to the max-cut problem

  2009cited by this paper
• Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations

  2009cited by this paper
• Exploring Network Structure, Dynamics, and Function using NetworkX

  2008cited by this paper
• Using Case-based Reasoning in an Algorithm Portfolio for Constraint Solving ?

  2008cited by this paper
• Understanding the Relationship between Scheduling Problem Structure and Heuristic Performance using Knowledge Discovery

  2008cited by this paper
• Towards insightful algorithm selection for optimisation using meta-learning concepts

  2008cited by this paper
• SATzilla: Portfolio-based Algorithm Selection for SAT

  2008cited by this paper
• Global equilibrium search applied to the unconstrained binary quadratic optimization problem

  2008cited by this paper
• Classification and Regression by randomForest

  2007cited by this paper
• On learning algorithm selection for classification

  2006cited by this paper
• Iterated Tabu Search for the Unconstrained Binary Quadratic Optimization Problem

  2006cited by this paper
• A low-level hybridization between memetic algorithm and VNS for the max-cut problem

  2005influential reference
• Phase Transitions in Combinatorial Optimization Problems - Basics, Algorithms and Statistical Mechanics

  2005cited by this paper
• Multistart Tabu Search Strategies for the Unconstrained Binary Quadratic Optimization Problem

  2004cited by this paper
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs

  2004cited by this paper
• Memetic algorithms for the unconstrained binary quadratic programming problem.

  2004cited by this paper
• New Benchmark Instances for the QAP and the Experimental Analysis of Algorithms

  2004cited by this paper
• Ranking Learning Algorithms: Using IBL and Meta-Learning on Accuracy and Time Results

  2003cited by this paper
• Statistical mechanics of the vertex-cover problem

  2003cited by this paper
• A portfolio approach to algorithm select

  2003cited by this paper
• Randomized heuristics for the Max-Cut problem

  2002cited by this paper
• Random graph models of social networks

  2002cited by this paper
• A Perspective View and Survey of Meta-Learning

  2002cited by this paper
• Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs

  2002influential reference
• Learning the Empirical Hardness of Optimization Problems: The Case of Combinatorial Auctions

  2002cited by this paper
• Greedy and Local Search Heuristics for Unconstrained Binary Quadratic Programming

  2002cited by this paper
• A Bayesian Approach to Tackling Hard Computational Problems (Preliminary Report)

  2001cited by this paper
• Experimental Evaluation of Heuristic Optimization Algorithms: A Tutorial

  2001cited by this paper
• Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem

  2001cited by this paper
• Modelling the relationship between problem characteristics and data mining algorithm performance using neural networks

  2001cited by this paper
• Random Forests

  2001cited by this paper
• A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics

  2001cited by this paper
• A comparison between simulated annealing, genetic algorithm and tabu search methods for the unconstrained quadratic Pseudo-Boolean function

  2000cited by this paper
• The Effects of Coefficient Correlation Structure in Two-Dimensional Knapsack Problems on Solution Procedure Performance

  2000cited by this paper
• Solving Large Binary Quadratic Programming Problems by Effective Genetic Local Search Algorithm

  2000cited by this paper
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs

  2000cited by this paper
• Random graphs with arbitrary degree distributions and their applications.

  2000cited by this paper
• Exploiting Competitive Planner Performance

  1999cited by this paper
• A theoretician's guide to the experimental analysis of algorithms

  1999cited by this paper
• Genetic algorithms for binary quadratic programming

  1999cited by this paper
• Emergence of scaling in random networks

  1999cited by this paper
• An evolutionary heuristic for quadratic 0-1 programming

  1999cited by this paper
• Emergence of Scaling in Random Networks

  1999cited by this paper
• A Spectral Bundle Method for Semidefinite Programming

  1999cited by this paper
• Adaptive Memory Tabu Search for Binary Quadratic Programs

  1998influential reference
• Collective dynamics of ‘small-world’ networks

  1998cited by this paper
• Heuristic algorithms for the unconstrained binary quadratic programming problem

  1998cited by this paper
• Simulated annealing for the unconstrained quadratic pseudo-Boolean function

  1998cited by this paper
• Network Design Using Cut Inequalities

  1996cited by this paper
• The TSP Phase Transition

  1996cited by this paper
• Testing heuristics: We have it all wrong

  1995cited by this paper
• Hiding Our Colors

  1995cited by this paper
• The landscape of the traveling salesman problem

  1992cited by this paper
• TSPLIB - A Traveling Salesman Problem Library

  1991cited by this paper
• Where the Really Hard Problems Are

  1991cited by this paper
• OR-Library: Distributing Test Problems by Electronic Mail

  1990cited by this paper
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design

  1988cited by this paper
• An algorithm for the selection problem

  1986cited by this paper
• On the evolution of random graphs

  1984cited by this paper
• Reducibility Among Combinatorial Problems

  1972cited by this paper
• An upper bound for the chromatic number of a graph and its application to timetabling problems

  1967cited by this paper
• The Facilities Layout Problem in Perspective

  1966cited by this paper
• Some Network Flow Problems Solved with Pseudo-Boolean Programming

  1965influential reference
• Konrad-zuse-zentrum F ¨ Ur Informationstechnik Berlin Steinlib: an Updated Library on Steiner Tree Problems in Graphs

  year unknowncited by this paper

• SLAM: Extending the Reach of Ising Machine Advantage

  2026cites this paper
• Enabling Population-Based Architectures for Neural Combinatorial Optimization

  2026cites this paper
• PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs

  2026cites this paper
• Large-scale quantum computing framework enhances drug discovery in multiple stages

  2026cites this paper
• Warm-Starting PCE for Traveling Salesman Problem

  2025cites this paper
• Hybrid Quantum Branch-and-Bound Method for Quadratic Unconstrained Binary Optimization

  2025cites this paper
• Quantum-Enhanced Optimization by Warm Starts

  2025influential citation
• Pangenome-guided sequence assembly via binary optimisation

  2025cites this paper
• Exact algorithms for quadratic optimization over roots of unity

  2025cites this paper
• A comprehensive benchmark of an Ising machine on the Max-Cut problem

  2025influential citation
• Compensating connectivity restrictions in quantum annealers via splitting and linearization techniques

  2025influential citation
• SSS Algorithms for Max-Cut

  2025cites this paper
• Predict and Conquer: Navigating Algorithm Trade-Offs with Quantum Design Automation

  2025cites this paper
• Characterizing QUBO Reformulations of the Max-k-Cut Problem for Quantum Computing

  2025cites this paper
• Probabilistic Computing Optimization of Complex Spin-Glass Topologies

  2025cites this paper
• Comparison of Hyperplane Rounding for Max-Cut and Quantum Approximate Optimization Algorithm over Certain Regular Graph Families

  2025cites this paper
• Enhanced open-source scatter search algorithm for solving quadratic unconstrained binary optimization problems

  2025cites this paper
• Solving Large-Scale QUBO with Transferred Parameters from Multilevel QAOA of Low Depth

  2025cites this paper
• MaxCutBench: Revisiting and Benchmarking Graph Neural Networks for Maximum Cut

  2025cites this paper
• Extrapolation method to optimize linear-ramp QAOA parameters: Evaluation of QAOA runtime scaling

  2025cites this paper
• Hybrid quantum optimization in the context of minimizing traffic congestion

  2025cites this paper
• Solving General QUBOs with Warm-Start QAOA via a Reduction to Max-Cut

  2025cites this paper
• Optimizing Distribution Network Design Using Conic Relaxation for Maximum Cut Formulations

  2025cites this paper
• Problem-Structure-Informed Quantum Approximate Optimization Algorithm for Large-Scale Unit Commitment with Limited Qubits

  2025cites this paper
• A Comparative Study of Quantum Optimization Techniques for Solving Combinatorial Optimization Benchmark Problems

  2025cites this paper
• QAOA in Quantum Datacenters: Parallelization, Simulation, and Orchestration

  2025cites this paper
• AppQSim: Application-oriented benchmarks for Hamiltonian simulation on a quantum computer

  2025cites this paper
• An Improved GAS Algorithm

  2025cites this paper
• Optimization via quantum preconditioning

  2025cites this paper
• Evolving Hard Maximum Cut Instances for Quantum Approximate Optimization Algorithms

  2025cites this paper
• A Collaborative Neurodynamic Algorithm for Quadratic Unconstrained Binary Optimization

  2025cites this paper
• QAOA-MaxCut has barren plateaus for almost all graphs

  2025influential citation
• Analyzing performance of commercial quantum annealing solvers for the capacitated vehicle routing problem

  2025cites this paper
• A quantum-classical hybrid branch&bound algorithm

  2025cites this paper
• An Information-Minimal Geometry for Qubit-Efficient Optimization

  2025cites this paper
• Learning to Solve Quadratic Unconstrained Binary Optimization in a Classification Way

  2024cites this paper
• Accuracy and Performance Evaluation of Quantum, Classical and Hybrid Solvers for the Max-Cut Problem

  2024cites this paper
• Benchmarking the optimization of optical machines with the planted solutions

  2024cites this paper
• Multiple-basis representation of quantum states

  2024cites this paper
• Solving Combinatorial Optimization Problems on a Photonic Quantum Computer

  2024cites this paper
• Large-scale quantum annealing simulation with tensor networks and belief propagation

  2024cites this paper
• Performance of quantum approximate optimization with quantum error detection

  2024cites this paper
• An Unsupervised Learning Framework Combined with Heuristics for the Maximum Minimal Cut Problem

  2024cites this paper
• A Multilevel Approach for Solving Large-Scale QUBO Problems with Noisy Hybrid Quantum Approximate Optimization

  2024cites this paper
• From Maximum Cut to Maximum Independent Set

  2024cites this paper
• Efficient digital quadratic unconstrained binary optimization solvers for SAT problems

  2024cites this paper
• Solving QUBO on the Loihi 2 Neuromorphic Processor

  2024cites this paper
• MARCO: A Memory-Augmented Reinforcement Framework for Combinatorial Optimization

  2024cites this paper
• Recursive Quantum Relaxation for Combinatorial Optimization Problems

  2024cites this paper
• Selecting fast algorithms for the capacitated vehicle routing problem with machine learning techniques

  2024cites this paper
• Qubit-efficient quantum combinatorial optimization solver

  2024cites this paper
• Optimal Data Center Energy Management With Hybrid Quantum-Classical Multi-Cuts Benders' Decomposition Method

  2024cites this paper
• Fixed Set Search Applied to the Max-Cut Problem

  2024cites this paper
• Circuit Partitioning and Transmission Cost Optimization in Distributed Quantum Circuits

  2024cites this paper
• Promise of Graph Sparsification and Decomposition for Noise Reduction in QAOA: Analysis for Trapped-Ion Compilations

  2024cites this paper
• Towards large-scale quantum optimization solvers with few qubits

  2024cites this paper
• Utilizing Graph Sparsification for Pre-processing in Maxcut QUBO Solver

  2024cites this paper
• A quadratic simplex algorithm for primal optimization over zero-one polytopes

  2024cites this paper
• Sparse autoregressive neural networks for classical spin systems

  2024cites this paper
• Quantum-Assisted Combinatorial Optimization for Reconfigurable Intelligent Surfaces in Smart Electromagnetic Environments

  2024cites this paper
• Toward a linear-ramp QAOA protocol: evidence of a scaling advantage in solving some combinatorial optimization problems

  2024cites this paper
• Towards Robust Benchmarking of Quantum Optimization Algorithms

  2024influential citation
• Benchmarking Quantum Annealers with Near-Optimal Minor-Embedded Instances

  2024cites this paper
• Benchmarking quantum optimization for the maximum-cut problem on a superconducting quantum computer

  2024influential citation
• QOPTLib: a Quantum Computing Oriented Benchmark for Combinatorial Optimization Problems

  2024cites this paper
• Benchmarking a heuristic Floquet adiabatic algorithm for the Max-Cut problem

  2024cites this paper
• MLQAOA: Graph Learning Accelerated Hybrid Quantum-Classical Multilevel QAOA

  2024cites this paper
• Application of a Hybrid Algorithm Based on Quantum Annealing to Solve a Metropolitan Scale Railway Dispatching Problem

  2023cites this paper
• TREE-QMC: Improving quartet graph construction for scalable and accurate species tree estimation from gene trees

  2023cites this paper
• An Experimental Evaluation of Semidefinite Programming and Spectral Algorithms for Max Cut

  2023cites this paper
• Milestones on the Quantum Utility Highway: Quantum Annealing Case Study

  2023cites this paper
• CCuantuMM: Cycle-Consistent Quantum-Hybrid Matching of Multiple Shapes

  2023cites this paper
• A New Global Algorithm for Max-Cut Problem with Chordal Sparsity

  2023cites this paper
• Mapping Quantum Circuits to Modular Architectures with QUBO

  2023cites this paper
• Self-contained relaxation-based dynamical Ising machines

  2023cites this paper
• A Dynamical Systems Perspective on Discrete Optimization

  2023cites this paper
• A review on Quantum Approximate Optimization Algorithm and its variants

  2023cites this paper
• HamLib: A Library of Hamiltonians for Benchmarking Quantum Algorithms and Hardware

  2023cites this paper
• A quantum computing approach for minimum loss problems in electrical distribution networks

  2023cites this paper
• QUBO.jl: A Julia Ecosystem for Quadratic Unconstrained Binary Optimization

  2023cites this paper
• Linearizing Binary Optimization Problems Using Variable Posets for Ising Machines

  2023cites this paper
• Custom CMOS Ising Machine Based on Relaxed Burer-Monteiro-Zhang Heuristic

  2023influential citation
• Comparing Solution Combination Techniques in Scatter Search for Quadratic Unconstrained Binary Optimization

  2023cites this paper
• TAQOS: A Benchmark Protocol for Quantum Optimization Systems

  2023cites this paper
• Hybrid Quantum-Classical Multilevel Approach for Maximum Cuts on Graphs

  2023cites this paper
• Improving the convergence of an iterative algorithm for solving arbitrary linear equation systems using classical or quantum binary optimization

  2023cites this paper
• An Enhanced 1440 Coupled CMOS Oscillator Network to Solve Combinatorial Optimization Problems

  2023cites this paper
• Milestones on the uantum Utility Highway: uantum Annealing Case Study

  2023cites this paper
• Benchmarking the optimization optical machines with the planted solutions

  2023cites this paper
• Solving rescheduling problems in heterogeneous urban railway networks using hybrid quantum-classical approach

  2023cites this paper
• Low-depth Clifford circuits approximately solve MaxCut

  2023cites this paper
• Challenges and opportunities in quantum optimization

  2023cites this paper
• New advances for quantum-inspired optimization

  2023cites this paper
• Improving quartet graph construction for scalable and accurate species tree estimation from gene trees

  2023cites this paper
• A Review on Quantum Approximate Optimization Algorithm and its Applications

  2023cites this paper
• FastHare: Fast Hamiltonian Reduction for Large-scale Quantum Annealing

  2022influential citation
• The max k-cut problem on classical and quantum solvers

  2022influential citation
• Formulations of the max k-cut problem on classical and quantum computers

  2022influential citation
• Strategic Solution Combination in Scatter Search for Quadratic Unconstrained Binary Optimization

  2022cites this paper
• Fast Algorithms for the Capacitated Vehicle Routing Problem using Machine Learning Selection of Algorithm's Parameters

  2022cites this paper