A Potts Neuron Approach to Communication Routing
Häkkinen, Jari LU
; Lagerholm, Martin
; Peterson, Carsten
LU
and Söderberg, Bo
LU
(1998)
In Neural Computation
10.
p.1587-1599
- Abstract
- A feedback neural network approach to communication routing problems
is developed, with emphasis on Multiple Shortest Path problems,
with several requests for transmissions between distinct start- and
endnodes. The basic ingredients are a set of Potts neurons for each request,with interactions designed to minimize path lengths and to
prevent overloading of network arcs. The topological nature of the
problem is conveniently handled using a propagator matrix approach.
Although the constraints are global, the algorithmic steps are based
entirely on local information, facilitating distributed implementations.
In the polynomially solvable single-request case, the... (More) - A feedback neural network approach to communication routing problems
is developed, with emphasis on Multiple Shortest Path problems,
with several requests for transmissions between distinct start- and
endnodes. The basic ingredients are a set of Potts neurons for each request,with interactions designed to minimize path lengths and to
prevent overloading of network arcs. The topological nature of the
problem is conveniently handled using a propagator matrix approach.
Although the constraints are global, the algorithmic steps are based
entirely on local information, facilitating distributed implementations.
In the polynomially solvable single-request case, the approach reduces
to a fuzzy version of the Bellman-Ford algorithm.
The method is evaluated for synthetic problems of varying sizes and
load levels, by comparing to exact solutions from a branch-and-bound
method, or to approximate solutions from a simple heuristic.
With very few exceptions, the Potts approach gives legal solutions of
very high quality. The computational demand scales merely as the
product of the numbers of requests, nodes, and arcs. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/1543946
- author
- Häkkinen, Jari
LU
; Lagerholm, Martin
; Peterson, Carsten
LU
and Söderberg, Bo
LU
- organization
- publishing date
- 1998
- type
- Contribution to journal
- publication status
- published
- subject
- in
- Neural Computation
- volume
- 10
- pages
- 1587 - 1599
- publisher
- MIT Press
- external identifiers
-
- scopus:0142020266
- ISSN
- 1530-888X
- DOI
- 10.1162/089976698300017322
- language
- English
- LU publication?
- yes
- id
- 7bd6802b-c9d4-4986-a3f0-6e75fc03eff3 (old id 1543946)
- date added to LUP
- 2016-04-04 13:32:25
- date last changed
- 2022-12-13 20:54:35
@article{7bd6802b-c9d4-4986-a3f0-6e75fc03eff3,
abstract = {{A feedback neural network approach to communication routing problems<br/><br>
is developed, with emphasis on Multiple Shortest Path problems,<br/><br>
with several requests for transmissions between distinct start- and<br/><br>
endnodes. The basic ingredients are a set of Potts neurons for each request,with interactions designed to minimize path lengths and to <br/><br>
prevent overloading of network arcs. The topological nature of the <br/><br>
problem is conveniently handled using a propagator matrix approach. <br/><br>
Although the constraints are global, the algorithmic steps are based <br/><br>
entirely on local information, facilitating distributed implementations.<br/><br>
In the polynomially solvable single-request case, the approach reduces<br/><br>
to a fuzzy version of the Bellman-Ford algorithm.<br/><br>
The method is evaluated for synthetic problems of varying sizes and<br/><br>
load levels, by comparing to exact solutions from a branch-and-bound<br/><br>
method, or to approximate solutions from a simple heuristic.<br/><br>
With very few exceptions, the Potts approach gives legal solutions of<br/><br>
very high quality. The computational demand scales merely as the<br/><br>
product of the numbers of requests, nodes, and arcs.}},
author = {{Häkkinen, Jari and Lagerholm, Martin and Peterson, Carsten and Söderberg, Bo}},
issn = {{1530-888X}},
language = {{eng}},
pages = {{1587--1599}},
publisher = {{MIT Press}},
series = {{Neural Computation}},
title = {{A Potts Neuron Approach to Communication Routing}},
url = {{http://dx.doi.org/10.1162/089976698300017322}},
doi = {{10.1162/089976698300017322}},
volume = {{10}},
year = {{1998}},
}