¿Cómo minimizar la cardinalidad de un conjunto y particiones disjuntas sujetas a restricciones en el tiempo polinómico?

El verdadero problema al que me enfrento es el siguiente.

INSTANCIA : tengo juegos $N:=\{1,\ldots,n\}$ y $K:=\{1,\ldots,k\}$ y matriz $a_{ij}>0$ para todos $i\in K$ y $j\in N$ .

PREGUNTA : necesito encontrar un subconjunto $S$ de $N$ de tamaño lo más pequeño posible y particione el conjunto $K$ dentro $|S|$ conjuntos disjuntos $K_j$ cuya unión es igual $K$ tal que para todos $j\in S$ , Yo tengo

\sum_{j^{'} \in S j^{'} \neq j} a_{i j^{'}} ⩽ a_{i j} - 1,

$\sum_{j'\in S\\j'\neq j} a_{ij'} \leqslant a_{ij}-1,$ para todo .

i \in K_{j}

$i\in K_j$

Ejemplo:

Dado y la matriz $n=k=3$

[\begin{matrix} 0.6 & 2.7 & 1.2 \\ 1.3 & 2.6 & 0.8 \\ 1.5 & 0.4 & 0.6 \end{matrix}] .

$\begin{bmatrix} 0.6 & 2.7 & 1.2\\ 1.3 & 2.6 & 0.8\\ 1.5 & 0.4 & 0.6 \end{bmatrix}.$

En este ejemplo, debería ser igual a y y . $S$ $S=\{1, 2\}$ $K_1=\{3\}$ $K_2=\{1,2\}$

Noté dos hechos:

Si existe alguna tal que para todo entonces y ; y $j\in N$ $a_{ij}\geqslant 1$ $i\in K$ $S=\{j\}$ $K_j=K$
Si existe alguna tal que entonces . $i\in K$ $a_{ij}<1$ $S=\emptyset$

Mi pregunta : ¿es posible resolver este problema de optimización en tiempo polinómico (al menos con algoritmo de aproximación)?

Lo primero que intenté hacer es transformarlo en un problema conocido y luego apliqué un algoritmo conocido para eso. Pensé en transformarlo en una tapa de conjunto o en un contenedor de basura, pero fallé y tampoco creo que esto sea interesante.

El problema que intenté formular.

Tengo conjuntos y y la matriz para todo y . Además, tengo conjuntos disjuntos para cada , (agregué como entradas porque de lo contrario no podría formularlo). $N:=\{1,\ldots,n\}$ $K:=\{1,\ldots,k\}$ $a_{ij}>0$ $i\in K$ $j\in N$ $n$ $K_j\subset K$ $j\in N$ $K_j$

Finalmente, obtengo esto:

\begin{aligned} \underset{S}{minimize} & | S | \\ subject to & \sum_{j^{'} \in S j^{'} \neq j} a_{i j^{'}} ⩽ a_{i j} - 1, \forall j \in S, i \in K_{j}, \\ S \subseteq N . \end{aligned}

$\begin{align*} & {\underset{S}{\text{minimize}}} & & |S|\\[3pt] & \text{subject to} & & \sum_{j'\in S\\j'\neq j} a_{ij'} \leqslant a_{ij}-1,\forall\, j\in S,i\in K_j,\\[3pt] & & & S\subseteq N.\\ \end{align*}$

Gracias.

algorithms optimization drzbir
fuente

¿Has intentado reformular como ILP usando variables binarias ? Su objetivo cambia a min con un cambio similar en la restricción. Un solucionador de ILP listo para usar puede manejarlo bien.

x_{j}

$x_j$

\sum x_{j}

$\sum x_j$

Nicholas Mancuso

¿Pero creo que eso no me daría un algoritmo de tiempo polinómico?

drzbir

Quizás en teoría, pero no en la práctica. Los solucionadores modernos como CPLEX son increíblemente buenos para encontrar soluciones óptimas en un tiempo relativamente corto gracias a las heurísticas de ramificación y unión y otras.

Nicholas Mancuso

¿Son los todos ? Si es así, entonces creo que la formulación de su "problema real" tiene un problema, ya que se optimiza trivialmente al permitir que sea cualquier conjunto único : esto hace que la suma en el LHS de su función objetivo sea 0 .

a_{i j}

$a_{ij}$

\geq 1

$\ge 1$

S

$S$

{j}

$\{j\}$

j_random_hacker

No todos los son mayores que .

a_{i j}

$a_{ij}$

1

$1$

drzbir

Respuestas:

Incluso la versión de decisión de este problema, en la que tratamos de determinar simplemente si existe alguna solución factible, es NP-difícil por reducción de Exact Cover . (La versión de optimización, donde buscamos una solución factible que minimice , es claramente al menos tan difícil como esta). $|S|$

La matriz de una sola fila y una sola columna que contiene el valor 0.5 es un ejemplo de una entrada para la cual no hay una solución factible. Aquí está otro:

[\begin{matrix} 0.2 & 4 \\ 3.1 & 3 \\ 5 & 0.6 \end{matrix}] .

$\begin{bmatrix} 0.2 & 4\\ 3.1 & 3\\ 5 & 0.6 \end{bmatrix}.$

Creación de un gadget "Elija como máximo uno"

Primero, observe que si el valor máximo en alguna fila es , y esta fila contiene (al menos) dos copias de , digamos en y , , entonces no puede contener tanto como , ya que si lo hiciera, entonces debería surgir uno de los siguientes dos casos, cada uno de los cuales conduce a una contradicción: $a_i$ $x > 0$ $x$ $a_{ij}$ $a_{ij'}$ $j' \ne j$ $S$ $j$ $j'$

$i \in K_j \cup K_{j'}$ : supongamos que wlog es . Pero entonces , contradiciendo el requisito de que . $i \in K_j$ $\Sigma_{m \in S, m \ne j}{a_{im}} \ge a_{ij'} = x = a_{ij}$ $\Sigma_{m \in S, m \ne j}{a_{im}} \le a_{ij} - 1$
$i \notin K_j \cup K_{j'}$ : Entonces supongamos que . Pero entonces , y dado que es máximo en la fila , el más alto que podría ser claramente , por lo que debemos estar violando la misma desigualdad que antes. $i \in K_p, p \notin \{j, j'\}$ $\Sigma_{m \in S, m \ne p}{a_{im}} \ge a_{ij} + a_{ij'} = 2x$ $x$ $i$ $a_{ip}$ $x$

De este modo podemos elegir un valor máximo que es con seguridad mayor que la suma de todos los valores que no son máximas en la fila, y el uso de copias de este valor máximo para hacer cumplir que a lo sumo una de esas columnas se incluye en . $S$

Podemos convertir esta restricción de "elegir como máximo una" en una restricción de "elegir exactamente una" usando cualquier valor positivo menor que 1 como el valor "no máximo". Esto se debe a que cada fila pertenece a alguna parte de la partición de la fila, y si , el RHS de la desigualdad se vuelve negativo para la fila , por lo que no hay forma de satisfacerlo: por lo tanto, al menos un debe ser forzado a modo que . $i$ $K_j$ $a_{ij} < 1$ $i$ $j$ $S$ $a_{ij} \ge 1$

Por lo tanto, para asegurarse de que exactamente una de las columnas en algún conjunto sea forzada a , cree una fila siguiente manera: $T \subseteq N$ $S$ $a_i$

Set para cada . $a_{ij} = n+1$ $j \in T$
Establezca para cada dos . $a_{ij} = 0.5$ $j$

Por lo tanto, la reducción de Exact Cover es sencilla: hay una fila para cada elemento, una columna para cada conjunto, con siempre que el conjunto incluya el elemento y contrario. Ambas direcciones ("La instancia EC de entrada es una instancia YES una instancia construida del problema de OP es una instancia YES", y "La instancia construida del problema de OP es una instancia YES una instancia EC de entrada es una instancia YES") están claros. $a_{ij} = n+1$ $j$ $i$ $a_{ij} = 0.5$ $\implies$ $\implies$

j_random_hacker
fuente

El ejemplo que diste creo que tiene una solución de .

2 \times 2

$2\times2$

S = {2}

$S=\{2\}$

drzbir

Tengo y . Entonces mi desigualdad es para . Porque la desigualdad debe ser válida para todo .

S = {2}

$S=\{2\}$

K_{2} = K = {1, 2}

$K_2=K=\{1,2\}$

0 ⩽ a_{i 2} - 1

$0\leqslant a_{i2}-1$

i \in K_{2} = {1, 2}

$i\in K_2=\{1,2\}$

i \in K_{j}

$i\in K_j$

drzbir

Tienes razón, lo siento. Lo arreglaré ahora.

j_random_hacker

He escrito este problema como un programa entero y lo resolví. Ahora, necesito resolverlo con un algoritmo codicioso (mejor, un algoritmo con garantías de rendimiento). Como sugirió, busqué el salto de portada exacto para encontrar ideas sobre cómo diseñar un buen algoritmo para esto. ¿Tienes alguna idea?

drzbir

Es NP-hard, por lo que casi con certeza no existe un algoritmo de poli-tiempo. Intentaría verificar todas las columnas individuales, todos los pares de columnas, todos los triples, etc. hasta que encuentre un conjunto satisfactorio. El subproblema que necesita resolver para cada fila (es decir, decidir qué elemento en elegir para esta fila) es fácil.

S

$S$

j_random_hacker