Local search heuristics for Quadratic Unconstrained Binary Optimization (QUBO)

Endre Boros, Peter L. Hammer, Gabriel Tavares

Research output: Contribution to journalArticle

41 Citations (Scopus)

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

Fingerprint

Local Search
Heuristics
Binary
Optimization
Rounding
Computational Experiments
Fractional
Experiments
Benchmark
Local search (optimization)
Local search
Family
Experiment

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

Cite this

Boros, Endre ; Hammer, Peter L. ; Tavares, Gabriel. / Local search heuristics for Quadratic Unconstrained Binary Optimization (QUBO). In: Journal of Heuristics. 2007 ; Vol. 13, No. 2. pp. 99-132.
@article{702dd130ee9d4d5586cd583e2f86f8a0,
title = "Local search heuristics for Quadratic Unconstrained Binary Optimization (QUBO)",
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.",
keywords = "Heuristics, Integer programming, Local optimization, Quadratic pseudo-Boolean functions, Quadratic unconstrained binary optimization",
author = "Endre Boros and Hammer, {Peter L.} and Gabriel Tavares",
year = "2007",
month = "4",
day = "1",
doi = "10.1007/s10732-007-9009-3",
language = "English (US)",
volume = "13",
pages = "99--132",
journal = "Journal of Heuristics",
issn = "1381-1231",
publisher = "Springer Netherlands",
number = "2",

}

Local search heuristics for Quadratic Unconstrained Binary Optimization (QUBO). / Boros, Endre; Hammer, Peter L.; Tavares, Gabriel.

In: Journal of Heuristics, Vol. 13, No. 2, 01.04.2007, p. 99-132.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Local search heuristics for Quadratic Unconstrained Binary Optimization (QUBO)

AU - Boros, Endre

AU - Hammer, Peter L.

AU - Tavares, Gabriel

PY - 2007/4/1

Y1 - 2007/4/1

N2 - 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.

AB - 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.

KW - Heuristics

KW - Integer programming

KW - Local optimization

KW - Quadratic pseudo-Boolean functions

KW - Quadratic unconstrained binary optimization

UR - http://www.scopus.com/inward/record.url?scp=33847640544&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33847640544&partnerID=8YFLogxK

U2 - 10.1007/s10732-007-9009-3

DO - 10.1007/s10732-007-9009-3

M3 - Article

AN - SCOPUS:33847640544

VL - 13

SP - 99

EP - 132

JO - Journal of Heuristics

JF - Journal of Heuristics

SN - 1381-1231

IS - 2

ER -