setcover | R Documentation |

Solves the Set Cover problem as an integer linear program.

setcover(Sets, weights)

`Sets` |
matrix of 0s and 1s, each line defining a subset. |

`weights` |
numerical weights for each subset. |

The Set Cover problems attempts to find in subsets (of a 'universe') a minimal set of subsets that still covers the whole set.

Each line of the matrix `Sets`

defines a characteristic function of
a subset. It is required that each element of the universe is contained
in at least one of these subsets.

The problem is treated as an Integer Linear Program (ILP) and solved
with the `lp`

solver in `lpSolve`

.

Returns a list with components `sets`

, giving the indices of subsets,
and `objective`

, the sum of weights of subsets present in the solution.

See the Wikipedia article on the "set cover problem".

`knapsack`

# Define 12 subsets of universe {1, ..., 10}. set.seed(7*11*13) A <- matrix(sample(c(0,1), prob = c(0.8,0.2), size = 120, replace =TRUE), nrow = 12, ncol = 10) sol <- setcover(Sets = A, weights = rep(1, 12)) sol ## $sets ## [1] 1 2 9 12 ## $no.sets ##[1] 4 # all universe elements are covered: colSums(A[sol$sets, ]) ## [1] 1 1 2 1 1 1 2 1 1 2

Embedding an R snippet on your website

Add the following code to your website.

For more information on customizing the embed code, read Embedding Snippets.