Advanced

A study of the mean field approach to knapsack problems

Ohlsson, Mattias LU and Pi, Hong (1997) In Neural Networks 10(2). p.263-271
Abstract

The mean field theory approach to knapsack problems is extended to multiple knapsacks and generalized assignment problems with Potts mean field equations governing the dynamics. Numerical tests against 'state of the art' conventional algorithms shows good performance for the mean field approach. The inherently parallelism of the mean field equations makes them suitable for direct implementations in microchips. It is demonstrated numerically that the performance is essentially not affected when only a limited number of bits is used in the mean field equations. Also, a hybrid algorithm with linear programming and mean field components is showed to further improve the performance for the difficult homogeneous N x M knapsack problem.

Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
finite precision, generalized assignment problems, knapsack problems, mean field theory, neural networks
in
Neural Networks
volume
10
issue
2
pages
9 pages
publisher
Elsevier
external identifiers
  • scopus:0031106015
ISSN
0893-6080
DOI
10.1016/S0893-6080(97)89067-3
language
English
LU publication?
yes
id
b3d521ae-909b-4b1b-b00c-30d53374b47c
date added to LUP
2017-05-19 08:22:46
date last changed
2017-05-23 09:19:37
@article{b3d521ae-909b-4b1b-b00c-30d53374b47c,
  abstract     = {<p>The mean field theory approach to knapsack problems is extended to multiple knapsacks and generalized assignment problems with Potts mean field equations governing the dynamics. Numerical tests against 'state of the art' conventional algorithms shows good performance for the mean field approach. The inherently parallelism of the mean field equations makes them suitable for direct implementations in microchips. It is demonstrated numerically that the performance is essentially not affected when only a limited number of bits is used in the mean field equations. Also, a hybrid algorithm with linear programming and mean field components is showed to further improve the performance for the difficult homogeneous N x M knapsack problem.</p>},
  author       = {Ohlsson, Mattias and Pi, Hong},
  issn         = {0893-6080},
  keyword      = {finite precision,generalized assignment problems,knapsack problems,mean field theory,neural networks},
  language     = {eng},
  number       = {2},
  pages        = {263--271},
  publisher    = {Elsevier},
  series       = {Neural Networks},
  title        = {A study of the mean field approach to knapsack problems},
  url          = {http://dx.doi.org/10.1016/S0893-6080(97)89067-3},
  volume       = {10},
  year         = {1997},
}