Your browser has javascript turned off or blocked. This will lead to some parts of our website to not work properly or at all. Turn on javascript for best performance.

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.

Mattias Ohlsson

Mattias Ohlsson

Professor

Mattias Ohlsson

An efficient mean field approach to the set covering problem

Author

  • Mattias Ohlsson
  • Carsten Peterson
  • Bo Söderberg

Summary, in English

A mean field feedback artificial neural network (ANN) algorithm is developed and explored for the set covering problem. A convenient encoding of the inequality constraints is achieved by means of a multilinear penalty function. An approximate energy minimum is obtained by iterating a set of mean field equations, in combination with annealing. The approach is numerically tested against a set of publicly available test problems with sizes ranging up to 5 × 103 rows and 106 columns. When comparing the performance with exact results for sizes where these are available, the approach yields results within a few percent from the optimal solutions. Comparisons with other approximate methods also come out well, in particular given the very low CPU consumption required - typically a few seconds. Arbitrary problems can be processed using the algorithm via a public domain server.

Department/s

  • Computational Biology and Biological Physics

Publishing year

2001-09-16

Language

English

Pages

583-595

Publication/Series

European Journal of Operational Research

Volume

133

Issue

3

Document type

Journal article

Publisher

Elsevier

Topic

  • Natural Sciences

Keywords

  • Combinatorial optimization
  • Mean field annealing
  • Neural networks
  • Set covering

Status

Published

ISBN/ISSN/Other

  • ISSN: 0377-2217