Published in

Elsevier, European Journal of Operational Research, 3(133), p. 583-595

DOI: 10.1016/s0377-2217(00)00205-8

Links

Tools

Export citation

Search in Google Scholar

An Efficient Mean Field Approach to the Set Covering Problem

Journal article published in 1999 by Mattias Ohlsson ORCID, Carsten Peterson, Bo Söderberg
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Upload
Orange circle
Postprint: archiving restricted
Upload
Red circle
Published version: archiving forbidden
Policy details
Data provided by SHERPA/RoMEO

Abstract

A mean field feedback artificial neural network 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 5x10^3 rows and 10^6 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. ; Comment: 17 pages, 2 figures