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.