Problema del conjunto de cobertura en R

Problema

Queremos resolver el problema del conjunto de cobertura en R. Calcular el número mínimo de conjuntos necesarios que contenga todos los elementos del universo. En nuestro ejemplo el universo es U = {1, 2, 3, 4, 5} y los conjuntos son s1 = {1, 2, 3}, s2 = {2, 4}, s3 = {3, 4}, s4 = {4, 5}.

  sets n
1   s1 1
2   s1 2
3   s1 3
4   s2 2
5   s2 4
6   s3 3
7   s3 4
8   s4 4
9   s4 5

df <- structure(list(sets = structure(c(1L, 1L, 1L, 2L, 2L, 3L, 3L, 
4L, 4L), .Label = c("s1", "s2", "s3", "s4"), class = "factor"), 
    n = c(1, 2, 3, 2, 4, 3, 4, 4, 5)), .Names = c("sets", "n"
), row.names = c(NA, -9L), class = "data.frame")

Solución

En nuestro ejemplo la solución es obvia, los conjuntos s1 y s4 serían el número de conjuntos mínimo necesario. Sin embargo, deseamos implementarlo en R para ser capaces de resolver problemas que comprendan miles de conjuntos con miles de elementos dentro de cada uno.

# El universo, elementos únicos de todos los conjuntos.
unique(df$n)

[1] 1 2 3 4 5

Empleamos el paquete lpSolve para resolver problemas de programación lineal.

# Creamos una representación matricial a partir del data frame
# Se asume que cada variable es  >= 0! (ver ?lp)
items.mat <- t(table(df$sets, df$n))
dimnames(items.mat) = list(items = 1:5, sets = paste0("s", 1:4))
items.mat
# Matriz
      sets
 items s1 s2 s3 s4
     1  1  0  0  0
     2  1  1  0  0
     3  1  0  1  0
     4  0  1  1  1
     5  0  0  0  1
f.obj <-  rep(1, 4)  # Valores de las variables de las inecuaciones
f.dir <- rep(">=", 5) # La cadena de texto de las restricciones por fila
f.rhs <- rep(1, 5)    # Los valores de la desigualdad por fila
lp("min", f.obj, items.mat, f.dir, f.rhs)$solution
[1] 1 0 0 1

La solución son los conjuntos s1 y s4 indicados por los coeficientes de las columnas: el 1º y el 4º.

Referencias

• Problema del conjunto de cobertura
• Set cover problem and examples
• Stackoverflow