An Efficient Mean Field Approach to the Set Covering Problem
| dc.creator | Ohlsson, Mattias | |
| dc.creator | Peterson, Carsten | |
| dc.creator | Söderberg, Bo | |
| dc.date | 1999-02-12 | |
| dc.date.accessioned | 2026-07-07T03:23:59Z | |
| dc.date.available | 2026-07-07T03:23:59Z | |
| dc.description | 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. | |
| dc.description | 17 pages, 2 figures | |
| dc.identifier | https://arxiv.org/abs/cs/9902025 | |
| dc.identifier | http://arxiv.org/abs/cs/9902025 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/33156 | |
| dc.subject | Neural and Evolutionary Computing | |
| dc.subject | G.1.6 | |
| dc.title | An Efficient Mean Field Approach to the Set Covering Problem | |
| dc.type | text |