Leveraging special-purpose hardware for local search heuristics

Xiaoyuan Liu (), Hayato Ushijima-Mwesigwa (), Avradip Mandal (), Sarvagya Upadhyay (), Ilya Safro () and Arnab Roy ()
Additional contact information
Xiaoyuan Liu: University of Delaware
Hayato Ushijima-Mwesigwa: Fujitsu Research of America, Inc.
Avradip Mandal: Fujitsu Research of America, Inc.
Sarvagya Upadhyay: Fujitsu Research of America, Inc.
Ilya Safro: University of Delaware
Arnab Roy: Fujitsu Research of America, Inc.

Computational Optimization and Applications, 2022, vol. 82, issue 1, No 1, 29 pages

Abstract: Abstract As we approach the physical limits predicted by Moore’s law, a variety of specialized hardware is emerging to tackle specialized tasks in different domains. Within combinatorial optimization, adiabatic quantum computers, complementary metal-oxide semiconductor annealers, and optical parametric oscillators are a few emerging specialized hardware technologies to solve optimization problems. The Ising optimization model unifies all of these emerging special-purpose hardware for optimization in terms of mathematical framework. In other words, they are all designed to solve optimization problems expressed in the Ising model or equivalently as a quadratic unconstrained binary optimization model. Due to various constraints specific to each type of hardware, they usually suffer from a major challenge: the number of variables that the hardware can manage to solve is very limited. The local search meta-heuristic is one of the approaches to tackle large-scale problems. However, a general optimization step within local search is not traditionally formulated in the Ising form. In this work, we introduce a new modeling framework for modeling local search heuristics for special-purpose hardware. In particular, we propose models that take the limitations of the Ising model and current hardware into account. As such, we demonstrate the advantage of our approach compared to previous methods by carrying out experiments to show that our local search models produce higher-quality solutions.

Keywords: Combinatorial optimization; Local search; Ising model; QUBO model; Quadratic assignment problem; 68R05; 90C27; 90C59 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10589-022-00354-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:82:y:2022:i:1:d:10.1007_s10589-022-00354-2

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-022-00354-2

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().