Problema del conjunto de cobertura

El problema del Set Covering , también conocido por sus siglas SCP pertenece a la familia de los problemas no polinomiales duros, es un problema clásico en las Ciencias de la computación, consiste en encontrar las soluciones que minimicen el problema de cubrir un conjunto de necesidades con el menor costo posible. También se puede entender como el problema de encontrar el mínimo de subconjuntos que contengan todos los elementos de un conjunto dado, con el fin de minimizar algún valor.

Definición formal

De una forma más formal se puede definir el problema de la cobertura como dado un universo U, una familia S de subconjuntos de U, una cobertura o solución para el problema es una subfamilia ${C}\subseteq{S}$ cuya unión de por resultado el mismo U.

Ejemplo

Figura 1: Ejemplo de set covering para la cobertura de comunas.

Una estación de bomberos tiene la capacidad de cubrir las emergencias tanto de su comuna como de las comunas adyacentes a ella, por ejemplo una estación construida en la comuna 1 (Figura 1) podrá cubrir las emergencias de todo su vecindario, es decir, de la comuna 1, comuna 2 , comuna 3 y comuna 5. Se necesitan construir tantas estaciones de bomberos sean necesarias para cubrir todas las comunas ante posibles emergencias cuidando que todas las comunas estén cubiertas por al menos una estación (una o más) resguardando que la cantidad de estaciones construidas sea el mínimo.

Modelo matemático

$Min \sum_{i=1}^{12} x_i$

Sujeto a :

$x_1+x_2+x_3+x_5 \ge 1$

$x_2+x_1+x_5 \ge 1$

$x_3+x_1+x_4 +x_5+x_6+x_7+x_8\ge 1$

$x_4+x_3+x_5+x_6+x_{11}\ge 1$

$x_5+x_1+x_2+x_3+x_4+x_{10}+x_{11}\ge 1$

$x_6+x_3+x_4+x_5+x_8+x_{11}\ge 1$

$x_7+x_3+x_8+x_{12}\ge 1$

$x_8+x_3+x_6+x_7+x_9+x_{11}+x_{12}\ge 1$

$x_9+x_8+x_{10}+x_{11}+x_{12}\ge 1$

$x_{10}+x_5+x_9+x_{11}\ge 1$

$x_{11}+x_4+x_5+x_6+x_8+x_9+x_{10}\ge 1$

$x_{12}+x_7+x_8+x_9\ge 1$

$X_{i} = \left\{ \begin{array}{l l} 1 &Si \, en \, la \, comuna \, i \, se \, construye \, una \, estacion \, \\ 0 & Si \, no \\ \end{array} \right.$

Solución

Una solución para este problema seria construir estaciones en la comuna 1, 11 y 12. Con un total de 3 estaciones construidas se lograría cubrir las necesidades de todas las comunas del problema.