The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Photo of Mattias Ohlsson

Mattias Ohlsson

Professor

Photo of Mattias Ohlsson

A study of the mean field approach to knapsack problems

Author

  • Mattias Ohlsson
  • Hong Pi

Summary, in English

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.

Department/s

  • Computational Biology and Biological Physics - Undergoing reorganization

Publishing year

1997-03

Language

English

Pages

263-271

Publication/Series

Neural Networks

Volume

10

Issue

2

Document type

Journal article

Publisher

Elsevier

Topic

  • Other Computer and Information Science

Keywords

  • finite precision
  • generalized assignment problems
  • knapsack problems
  • mean field theory
  • neural networks

Status

Published

ISBN/ISSN/Other

  • ISSN: 0893-6080