๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Combinatorial optimization on a Boltzmann machine

โœ Scribed by Jan H.M. Korst; Emile H.L. Aarts

Publisher
Elsevier Science
Year
1989
Tongue
English
Weight
483 KB
Volume
6
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

โœฆ Synopsis

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

๐Ÿ“œ SIMILAR VOLUMES

A boltzmann machine approach to code opt
A boltzmann machine approach to code optimization
โœ A. De Gloria; P. Faraboschi ๐Ÿ“‚ Article ๐Ÿ“… 1991 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 691 KB

De Gloria, A. and P. Faraboschi, A Boltzmann Machine approach to code optimization, Parallel Computing 17 (1991) 969-982\_ In this paper we present a statistical approach to the problem of horizontal code compaction for the class of parallel synchronous non-homogeneous architectures. The proposed t

A Continuous-Time Asynchronous Boltzmann
A Continuous-Time Asynchronous Boltzmann Machine
โœ Kazuo Yamanaka; Masahiro Agu; Teruyuki Miyajima ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 814 KB

We propose an asynchronous neural network model having the same structure as the binary Hopfield model. Each neuron operates with continuous time and randomly changes its state according only to its membrane potential. The proposed model settles in a steady-state fluctuation, in which the probabilit

On simple combinatorial optimization pro
On simple combinatorial optimization problems
โœ A.J. Hoffman ๐Ÿ“‚ Article ๐Ÿ“… 1992 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 228 KB

We characterize (0,l) linear programming matrices for which a greedy algorithm and its dual solve certain covering and packing problems. Special cases are shortest path and minimum spanning tree algorithms.