setcover: Set cover problem

In adagio: Discrete and Global Optimization Routines

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

See Also

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]  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

adagio documentation built on Oct. 26, 2023, 5:08 p.m.