Combinatorial optimization on a Boltzmann machine

J.H.M. Korst, E.H.L. Aarts

Research output: Contribution to journalArticleScientificpeer-review

Abstract

We discuss the problem of solving (approximately) combinatorial optimization problems on a Boltzmann machine. It is shown for a number of combinatorial optimization problems how they can be mapped directly onto a Boltzmann machine by choosing appropriate connection patterns and connection strengths. In this way maximizing the consensus in the Boltzmann machine is equivalent to finding an optimal solution of the corresponding optimization problem. The approach is illustrated by numerical results obtained by applying the model of Boltzmann machines to randomly generated instances of the independent set, the max cut, and the graph coloring problem. For these instances the Boltzmann machine finds near-optimal solutions whose quality is comparable to that obtained with sequential simulated annealing algorithms. The advantage of the Boltzmann machine is the potential for carrying out operations in parallel. For the problems we have been investigating, this results in a considerable speedup over the sequential simulated annealing algorithms.
Original languageEnglish
Pages (from-to)331-357
Number of pages27
JournalJournal of Parallel and Distributed Computing
Volume6
Issue number2
DOIs
Publication statusPublished - 1989
Externally publishedYes

Cite this

@article{694bfa34811244baa6a9615d4c191c38,
title = "Combinatorial optimization on a Boltzmann machine",
abstract = "We discuss the problem of solving (approximately) combinatorial optimization problems on a Boltzmann machine. It is shown for a number of combinatorial optimization problems how they can be mapped directly onto a Boltzmann machine by choosing appropriate connection patterns and connection strengths. In this way maximizing the consensus in the Boltzmann machine is equivalent to finding an optimal solution of the corresponding optimization problem. The approach is illustrated by numerical results obtained by applying the model of Boltzmann machines to randomly generated instances of the independent set, the max cut, and the graph coloring problem. For these instances the Boltzmann machine finds near-optimal solutions whose quality is comparable to that obtained with sequential simulated annealing algorithms. The advantage of the Boltzmann machine is the potential for carrying out operations in parallel. For the problems we have been investigating, this results in a considerable speedup over the sequential simulated annealing algorithms.",
author = "J.H.M. Korst and E.H.L. Aarts",
year = "1989",
doi = "10.1016/0743-7315(89)90064-6",
language = "English",
volume = "6",
pages = "331--357",
journal = "Journal of Parallel and Distributed Computing",
issn = "0743-7315",
publisher = "Academic Press Inc.",
number = "2",

}

Combinatorial optimization on a Boltzmann machine. / Korst, J.H.M.; Aarts, E.H.L.

In: Journal of Parallel and Distributed Computing, Vol. 6, No. 2, 1989, p. 331-357.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Combinatorial optimization on a Boltzmann machine

AU - Korst, J.H.M.

AU - Aarts, E.H.L.

PY - 1989

Y1 - 1989

N2 - We discuss the problem of solving (approximately) combinatorial optimization problems on a Boltzmann machine. It is shown for a number of combinatorial optimization problems how they can be mapped directly onto a Boltzmann machine by choosing appropriate connection patterns and connection strengths. In this way maximizing the consensus in the Boltzmann machine is equivalent to finding an optimal solution of the corresponding optimization problem. The approach is illustrated by numerical results obtained by applying the model of Boltzmann machines to randomly generated instances of the independent set, the max cut, and the graph coloring problem. For these instances the Boltzmann machine finds near-optimal solutions whose quality is comparable to that obtained with sequential simulated annealing algorithms. The advantage of the Boltzmann machine is the potential for carrying out operations in parallel. For the problems we have been investigating, this results in a considerable speedup over the sequential simulated annealing algorithms.

AB - We discuss the problem of solving (approximately) combinatorial optimization problems on a Boltzmann machine. It is shown for a number of combinatorial optimization problems how they can be mapped directly onto a Boltzmann machine by choosing appropriate connection patterns and connection strengths. In this way maximizing the consensus in the Boltzmann machine is equivalent to finding an optimal solution of the corresponding optimization problem. The approach is illustrated by numerical results obtained by applying the model of Boltzmann machines to randomly generated instances of the independent set, the max cut, and the graph coloring problem. For these instances the Boltzmann machine finds near-optimal solutions whose quality is comparable to that obtained with sequential simulated annealing algorithms. The advantage of the Boltzmann machine is the potential for carrying out operations in parallel. For the problems we have been investigating, this results in a considerable speedup over the sequential simulated annealing algorithms.

U2 - 10.1016/0743-7315(89)90064-6

DO - 10.1016/0743-7315(89)90064-6

M3 - Article

VL - 6

SP - 331

EP - 357

JO - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

SN - 0743-7315

IS - 2

ER -