Advanced

Deterministic Annealing and Nonlinear Assignment

Söderberg, Bo LU and Jönsson, Henrik (2001) In LU TP 01-16.
Abstract (Swedish)
For combinatorial optimization problems that can be formulated as Ising or Potts spin systems, the Mean Field (MF) approximation yields a versatile and simple ANN heuristic, Deterministic Annealing. For problems involving assignments (or permutations), the situation is more complex -- the natural analog of the MF approximation lacks the simplicity present in the Potts and Ising cases. In this article the difficulties associated with this issue are investigated, and the options for solving them discussed. Improvements to existing Potts-based MF-inspired heuristics are suggested, and the possibilities for defining a proper variational approach are scrutinized.
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Book/Report
publication status
published
in
LU TP
volume
01-16
pages
16 pages
publisher
Lund University
language
English
LU publication?
yes
id
13d7fc0f-4d9b-496f-b001-97d583f67367
date added to LUP
2019-05-13 20:38:40
date last changed
2020-01-14 14:00:38
@techreport{13d7fc0f-4d9b-496f-b001-97d583f67367,
  abstract     = {For combinatorial optimization problems that can be formulated as Ising or Potts spin systems, the Mean Field (MF) approximation yields a versatile and simple ANN heuristic, Deterministic Annealing. For problems involving assignments (or permutations), the situation is more complex -- the natural analog of the MF approximation lacks the simplicity present in the Potts and Ising cases. In this article the difficulties associated with this issue are investigated, and the options for solving them discussed. Improvements to existing Potts-based MF-inspired heuristics are suggested, and the possibilities for defining a proper variational approach are scrutinized.},
  author       = {Söderberg, Bo and Jönsson, Henrik},
  institution  = {Lund University},
  language     = {eng},
  series       = {LU TP},
  title        = {Deterministic Annealing and Nonlinear Assignment},
  volume       = {01-16},
  year         = {2001},
}