An efficient mean field approach to the set covering problem

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 × 10³ rows and 10⁶ 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.

• Author: Mattias Ohlsson; Carsten Peterson; Bo Söderberg
• Department/s: Computational Biology and Biological Physics - Has been reorganised
• Publishing year: 2001-09-16
• Language: English
• Pages: 583-595
• Publication/Series: European Journal of Operational Research
• Volume: 133
• Issue: 3
• Links: http://dx.doi.org/10.1016/S0377-2217(00)00205-8
• 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