Optimización con restricciones de agrupación

Question

Estoy buscando una solución eficiente para resolver el siguiente problema. ¿Puede alguien ayudarme?

S es un conjunto finito de elementos $k_i$

V es un subconjunto de S, por ejemplo $v_4$ ={ $k_1$ , $k_3$ }

E es un conjunto finito de V, por ejemplo, E = { v1={ $k_1$ }, v2={ $k_1$ , $k_2$ }, v4={ $k_1$ , $k_3$ }, v4={ $k_2$ , $k_4$ , $k_5$ } }

f: S x V ]-,], ( $k_i$ , $v_j$ ) $w_{ij}$ con $w_{ij}$ infinito si y sólo si $k_i$ $v_j$ .

El problema es encontrar el conjunto M de elementos distintos de E que minimiza ij $w_{ij}$ calculado sobre todos los elementos de S y M, bajo una de las dos restricciones siguientes:

Problema 1) Cada $k_i$ es miembro de exactamente un elemento de M o no es miembro de ningún elemento de M.

Problema 2) cada uno $k_i$ es miembro de exactamente un elemento de M (para este caso suponemos que existe al menos una solución válida en E)

Lo mejor,

Sébastien

Answer 1

Sí, eso es correcto si también se añaden las restricciones definidas para cada problema.

Los elementos de S son aristas de un grafo dirigido planar y los elementos de V son bucles dirigidos del grafo. E es un conjunto de bucles, cada uno con una métrica asociada.