Boltzmann machines for travelling salesman problems

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

Research output: Contribution to journalArticleScientificpeer-review

Abstract

Boltzmann machines are proposed as a massively parallel alternative to the (sequential) simulated annealing algorithm. Our approach is tailored to the travelling salesman problem, but it can also be applied to a more general class of combinatorial optimization problems. For two distinct 0–1 programming formulations of the travelling salesman problem (as a linear and as a quadratic assignment problem) it is shown that near-optimal solutions can be obtained by mapping the corresponding 0–1 variables onto the logic computing elements of a Boltzmann machine, and by transforming the cost functions corresponding to the 0–1 programming formulations into the consensus function associated with the Boltzmann machine. Results of computer simulations are presented for two problem instances, i.e. with 10 cities and 30 cities, respectively.
Original languageEnglish
Pages (from-to)79-95
Number of pages17
JournalEuropean Journal of Operational Research
Volume39
Issue number1
DOIs
Publication statusPublished - 1989
Externally publishedYes

Fingerprint

Boltzmann Machine
Traveling salesman problem
Travelling salesman problems
Combinatorial optimization
Programming
Simulated annealing
Cost functions
Quadratic Assignment Problem
Formulation
Sequential Algorithm
Simulated Annealing Algorithm
Combinatorial Optimization Problem
Cost Function
Computer simulation
Computer Simulation
Optimal Solution
Logic
Distinct
Computing
Alternatives

Cite this

@article{28d3247dd4f14075b050936709cac086,
title = "Boltzmann machines for travelling salesman problems",
abstract = "Boltzmann machines are proposed as a massively parallel alternative to the (sequential) simulated annealing algorithm. Our approach is tailored to the travelling salesman problem, but it can also be applied to a more general class of combinatorial optimization problems. For two distinct 0–1 programming formulations of the travelling salesman problem (as a linear and as a quadratic assignment problem) it is shown that near-optimal solutions can be obtained by mapping the corresponding 0–1 variables onto the logic computing elements of a Boltzmann machine, and by transforming the cost functions corresponding to the 0–1 programming formulations into the consensus function associated with the Boltzmann machine. Results of computer simulations are presented for two problem instances, i.e. with 10 cities and 30 cities, respectively.",
author = "E.H.L. Aarts and J.H.M. Korst",
year = "1989",
doi = "10.1016/0377-2217(89)90355-X",
language = "English",
volume = "39",
pages = "79--95",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier Science BV",
number = "1",

}

Boltzmann machines for travelling salesman problems. / Aarts, E.H.L.; Korst, J.H.M.

In: European Journal of Operational Research, Vol. 39, No. 1, 1989, p. 79-95.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Boltzmann machines for travelling salesman problems

AU - Aarts, E.H.L.

AU - Korst, J.H.M.

PY - 1989

Y1 - 1989

N2 - Boltzmann machines are proposed as a massively parallel alternative to the (sequential) simulated annealing algorithm. Our approach is tailored to the travelling salesman problem, but it can also be applied to a more general class of combinatorial optimization problems. For two distinct 0–1 programming formulations of the travelling salesman problem (as a linear and as a quadratic assignment problem) it is shown that near-optimal solutions can be obtained by mapping the corresponding 0–1 variables onto the logic computing elements of a Boltzmann machine, and by transforming the cost functions corresponding to the 0–1 programming formulations into the consensus function associated with the Boltzmann machine. Results of computer simulations are presented for two problem instances, i.e. with 10 cities and 30 cities, respectively.

AB - Boltzmann machines are proposed as a massively parallel alternative to the (sequential) simulated annealing algorithm. Our approach is tailored to the travelling salesman problem, but it can also be applied to a more general class of combinatorial optimization problems. For two distinct 0–1 programming formulations of the travelling salesman problem (as a linear and as a quadratic assignment problem) it is shown that near-optimal solutions can be obtained by mapping the corresponding 0–1 variables onto the logic computing elements of a Boltzmann machine, and by transforming the cost functions corresponding to the 0–1 programming formulations into the consensus function associated with the Boltzmann machine. Results of computer simulations are presented for two problem instances, i.e. with 10 cities and 30 cities, respectively.

U2 - 10.1016/0377-2217(89)90355-X

DO - 10.1016/0377-2217(89)90355-X

M3 - Article

VL - 39

SP - 79

EP - 95

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 1

ER -