Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

An efficient mean field approach to the set covering problem

Ohlsson, Mattias LU orcid ; Peterson, Carsten LU and Söderberg, Bo LU (2001) In European Journal of Operational Research 133(3). p.583-595
Abstract

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... (More)

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.

(Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Combinatorial optimization, Mean field annealing, Neural networks, Set covering
in
European Journal of Operational Research
volume
133
issue
3
pages
13 pages
publisher
Elsevier
external identifiers
  • scopus:0035899781
ISSN
0377-2217
DOI
10.1016/S0377-2217(00)00205-8
language
English
LU publication?
yes
id
f8185e12-cfa0-49a8-93c2-ebc7f22aa3bf
date added to LUP
2016-10-03 19:08:36
date last changed
2022-12-14 02:58:11
@article{f8185e12-cfa0-49a8-93c2-ebc7f22aa3bf,
  abstract     = {{<p>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 × 10<sup>3</sup> rows and 10<sup>6</sup> 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.</p>}},
  author       = {{Ohlsson, Mattias and Peterson, Carsten and Söderberg, Bo}},
  issn         = {{0377-2217}},
  keywords     = {{Combinatorial optimization; Mean field annealing; Neural networks; Set covering}},
  language     = {{eng}},
  month        = {{09}},
  number       = {{3}},
  pages        = {{583--595}},
  publisher    = {{Elsevier}},
  series       = {{European Journal of Operational Research}},
  title        = {{An efficient mean field approach to the set covering problem}},
  url          = {{http://dx.doi.org/10.1016/S0377-2217(00)00205-8}},
  doi          = {{10.1016/S0377-2217(00)00205-8}},
  volume       = {{133}},
  year         = {{2001}},
}