Mean Field Solver
for 
Set Covering Problems


Complex Systems Group
Department of Theoretical Physics 
Lund University
Sweden


Back to the Mean Field Solver home page


The Set Covering Problem (SCP)

The set covering problem (SCP) is the problem of finding a subset of the columns of an MxN zero-one matrix A that covers all rows at a minimum cost. More precisely,  SCP is defined as follows:
 


 

Defining a SCP

An instance of SCP is defined by specifying the costs ci and the matrix A. Two formats, row and column ordering, are supported for the file that lists ci and the none-zero entries of A. They are defined as follows:


 

Jump to the file submitting page



Hardware setup

The current hardware setup for the server is:

Processor: AMD K6-2 300 MHz
Memory: 64 MB
OS: Linux

The available amount of memory on the server imposes a limitation B on the size of the problems that can be submitted to the server. Instances of SCP with MNd > B will not be considered (where d is the density of ones in the matrix A).
Presently B is given by 3x106.


References

The mean field algorithm for set covering problems is described in An Efficient Mean Field Approach to the Set Covering Problem, by M. Ohlsson, C. Peterson and B. Söderberg [abstract][ps.gz].

More References


Last updated: Feb. 12 1998
Mail comments and queries to mattias@thep.lu.se