Complex Systems Group
Department of Theoretical Physics
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
The current hardware setup for the server is:
Processor: AMD K6-2 300 MHz
Memory: 64 MB
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.
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].