# setcover: Set cover problem In adagio: Discrete and Global Optimization Routines

 setcover R Documentation

## Set cover problem

### Description

Solves the Set Cover problem as an integer linear program.

### Usage

```  setcover(Sets, weights)
```

### Arguments

 `Sets` matrix of 0s and 1s, each line defining a subset. `weights` numerical weights for each subset.

### Details

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`.

### Value

Returns a list with components `sets`, giving the indices of subsets, and `objective`, the sum of weights of subsets present in the solution.

### References

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

`knapsack`

### Examples

```# 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  2  9 12
## \$no.sets
## 4

# all universe elements are covered:
colSums(A[sol\$sets, ])
##  1 1 2 1 1 1 2 1 1 2
```

adagio documentation built on Oct. 3, 2022, 5:07 p.m.