Soy un aplicadas matemáticas de los estudiantes de pregrado. En mi proyecto, me encuentro con una programación lineal entera pregunta como sigue:
Dado $x_0,x_1,...,x_n$: $\forall$ i $\in$ [0,n], $x_i$ = 0 o 1
min Z = $\sum_{i=0}^n x_i $
con m números de restricciones en el formato"$\sum x_j \ge 1$: j $\in$ [0,n].
Sé que esto es generalmente un problema con NP dureza, pero me preguntaba si existe un algoritmo eficaz para resolver este problema.
En realidad, esto no es un problema de difícil solución, que puede ser resuelto de manera eficiente mediante la interpretación como una red de flujo de problema. Suponga que tiene el siguiente problema: $$ \min \; x_1+x_2+x_3 $$ sujeto a $$ x_1+x_2 \ge 1\\ x_1+x_3 \ge 1 \\ x_1,x_2,x_3 \in \{0,1\} $$
Ahora, cree el siguiente gráfico:
Añadir un coste unitario en arcos de la $(s,1), (s,2), (s,3)$, e imponer que el flujo de $f$ en todos los arcos que terminan en el nodo $t$ es al menos igual a $1$. El uso de cualquier coste mínimo de flujo del algoritmo para resolver el problema y listo.
EDICIÓN de $1$: Hay una contradicción entre esta respuesta y @hardmath la respuesta: uno de los dos no es posible. El problema no puede ser NP-duro y ser resuelto en el polinomio de tiempo. Sospecho que hay algo mal con mi modelo de flujo, pero no puedo averiguar por qué. Ahuja y Magnanti (Redes de Flujos) han propuesto algoritmos de camino más corto para este problema si no son consecutivos 1 en las columnas de la matriz, pero no para el caso general. Esta es una sugerencia que creo que algo debe de estar mal con mi modelo de flujo para el caso general. A continuación se muestra su red de flujo modelo si no son consecutivos 1 en las columnas de la matriz. Ver su libro para obtener más detalles.
EDICIÓN de $2$:
Como @Erwin Kalvelagen señaló, por encima de la red de flujo modelo es incorrecto. La razón para esto es que el flujo en el nodo $s$ no es igual a la función objetivo (número de variables). Se cuenta el número total de veces que cada variable se utiliza, que no es lo que queremos.
En resumen:
La reducción del problema a una instancia de SetCover es claro tal vez. Vamos a demostrar que la inversa también es posible, para formular cualquier SetCover instancia como un entero binario programa de el tipo que usted está preguntando acerca de, y esto va a establecer que el resultado de la minimización de la computación es NP-duro.
Un buen estudio de métodos aproximados para este tipo de problemas (como el redondeo de programación lineal) está dada por Fatema Akhter (2015), "Una Aproximación Heurística para el Conjunto Mínimo de la Cubierta Problema", donde una modificación de escalada el algoritmo que se propone y su rendimiento en comparación con la de una biblioteca de SetCover problemas.
Primero vamos a aclarar la notación utilizada para las restricciones, porque lo que estaba escrito en la Pregunta: $$m \text{ numbers of constraints in the form } \sum x_j \ge 1: j \in [0,n]$$
no distinguir adecuadamente entre los diferentes restricciones. Para cada restricción debe ser un subconjunto $C_k \subseteq \{0,\ldots,n\}$ de los índices más que la suma se toma:
$$ \sum_{j \in C_k} x_j \ge 1 $$
Para su comodidad, nos referiremos a esta última restricción por su índice subconjunto $C_k$, por lo que la colección de $m$ restricciones es $\mathscr{U} = \{C_1,\ldots,C_m\}$.
Esta $\mathscr{U}$ será el universo de nuestra SetCover instancia, y la familia de conjuntos a partir de la cual una cobertura mínima será encontrado es $\mathscr{S} = \{S_0,S_1,\ldots,S_n\}$ donde:
$$ S_i = \{ C_k : x_i \in C_k \} \text{ for } i=0,1,\ldots,n $$
Tenga en cuenta que los conjuntos de $S_i$ están en una correspondencia uno a uno con las variables,$x_i$. Deje un mínimo de cobertura $\mathscr{S}' \subseteq \mathscr{S}$ del universo, y establecer $x_i = 1$ si y sólo si $S_i \in \mathscr{S}'$, $x_i = 0$ de lo contrario. Un poco de pensamiento debe convencernos de esta asignación minimiza el objetivo:
$$ Z = \sum_{i=0}^n x_i $$
sujeto a las restricciones $C_k$, la cantidad que se requiere que cada subconjunto $C_k$ contiene al menos una variable $x_i$ que se le asigna un valor de $1$.
En otras palabras, hemos descrito cómo elegir qué variables$x_i=1$, de modo que su suma $Z$ es mínimo.
Con un poco más de pensamiento y de explicación, esta reducción puede ser la contraria, así que cualquier SetCover instancia puede ser expresado como una similar entero binario de un problema de programación. Va en esta dirección nos da un universo finito $\mathscr{U}$ que nos sugestivamente escribir como un conjunto de $m$ puntos de:
$$ \mathscr{U} = \{c_1,\ldots,c_m\} $$
y un finito no vacío de la familia de subconjuntos de a $\mathscr{S} = \{S_0,S_1,\ldots,S_n\}$ cuya unión es todo de $\mathscr{U}$.
Definir binario "indicador" variables $x_i \in \{0,1\}$ correspondiente a los subconjuntos $S_i$, por lo que para la elección de la subfamilia $\mathscr{S}' \subseteq \mathscr{S}$:
$$ x_i = \begin{cases} 1 & \text{if } S_i \in \mathscr{S}' \\ 0 & \text{otherwise} \end{cases} $$
Ahora como antes de pedirle a minimizar $Z = \sum_{i=0}^n x_i$ $m$ restricciones:
$$ \sum_{i \in C_k} x_i \ge 1 $$
para $k = 1,\ldots,m$ donde $C_k = \{ i : c_k \in S_i \}$.
Una solución viable $x_0,x_1,\ldots,x_n$ nos proporciona una cubierta de $\mathscr{S}'$ del universo a través de la configuración de variables indicadoras $x_i$. Que es, ya que cada restricción se satisface, cada una de las $c_k \in \mathscr{U}$ va a pertenecer al menos a una $S_i \in \mathscr{S}'$. Una solución que minimiza $Z$, al mismo tiempo, minimizar el tamaño de $\mathscr{S}'$, ya que el $Z = |\mathscr{S}'|$.
Habiéndose demostrado que el problema, al menos en la generalidad ha descrito anteriormente, es NP-duro, puede ser de interés señalar algoritmos para aproximar soluciones a SetCover que producen en el polinomio de tiempo, cubre a los que están dentro de algún factor de la verdadera cubierta mínima de tamaño.
En el contexto de un universo de tamaño $m$, el algoritmo voraz (elegir en cada paso, un subconjunto $S_i$ que contiene la mayoría de los puntos que todavía no están cubiertos), que produce una solución cuyo tamaño es en la mayoría de las $\log m$ veces el verdadero tamaño mínimo.
El artículo de la Wikipedia en SetCover que estamos vinculados de arriba da referencia a una bastante reciente papel por Dinur y Steurer (2013), que demuestra que el polinomio de algoritmos en tiempo no puede dar mucho mejor aproximación a los factores a menos que P = NP. Esta es la culminación de diversas investigaciones, que muestran "que el algoritmo voraz es esencialmente el mejor de los posibles polinomio tiempo algoritmo de aproximación para el conjunto de la cubierta para reducir los términos de orden."
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
