Local search heuristics for Quadratic Unconstrained Binary Optimization (QUBO)

Endre Boros, Peter L. Hammer, Gabriel Tavares

Research output: Contribution to journalArticle

44 Scopus citations

Abstract

We present a family of local-search-based heuristics for Quadratic Unconstrained Binary Optimization (QUBO), all of which start with a (possibly fractional) initial point, sequentially improving its quality by rounding or switching the value of one variable, until arriving to a local optimum. The effects of various parameters on the efficiency of these methods are analyzed through computational experiments carried out on thousands of randomly generated problems having 20 to 2500 variables. Tested on numerous benchmark problems, the performance of the most competitive variant (ACSIOM) was shown to compare favorably with that of other published procedures.

Original languageEnglish (US)
Pages (from-to)99-132
Number of pages34
JournalJournal of Heuristics
Volume13
Issue number2
DOIs
StatePublished - Apr 1 2007

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Computer Networks and Communications
  • Control and Optimization
  • Management Science and Operations Research
  • Artificial Intelligence

Keywords

  • Heuristics
  • Integer programming
  • Local optimization
  • Quadratic pseudo-Boolean functions
  • Quadratic unconstrained binary optimization

Fingerprint Dive into the research topics of 'Local search heuristics for Quadratic Unconstrained Binary Optimization (QUBO)'. Together they form a unique fingerprint.

  • Cite this