An Efficient Mean Field Approach to the Set Covering Problem
<|reference_start|>An Efficient Mean Field Approach to the Set Covering Problem: 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.<|reference_end|>
@article{ohlsson1999an,
    title={An Efficient Mean Field Approach to the Set Covering Problem},
    author={Mattias Ohlsson, Carsten Peterson and Bo S"oderberg},
    journal={arXiv preprint arXiv:cs/9902025},
    year={1999},
    archivePrefix={arXiv},
    eprint={cs/9902025},
    primaryClass={cs.NE}
}