1

I am looking for an efficient solution to solve the following problem. Can anybody help?

S is a finite set of elements $k_i$

V is a subset of S, e.g. $v_4$={$k_1$,$k_3$}

E is a finite ensemble of V, e.g. 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}$, with $w_{ij}$ infinite if and only if $k_i$ ∉ $v_j$.

The problem is to find the ensemble M of distinct elements of E minimizing ∑ij $w_{ij}$ computed over all elements of S and M, under one of the following two constraints:

Problem 1) Each $k_i$ is member of exactly one element of M or not a member of any element of M.

Problem 2) each $k_i$ is member of exactly one element of M (for this case we assume that at least a valid solution exists in E)

Best,

Sébastien

Sebastien
  • 11
  • Your problem statement is not entirely clear. My understanding now is that you have some function $f : S \times 2^S \to \mathbb{R}$, and $g : 2^{2^S} \to \mathbb{R}$ defined by $g(M) = \sum_{A \in M} \sum_{i \in S} f(i,A)$. Then you want to minimize $g$ subject to some constraints (in particular subject to $M \subset E$, where $E$ is fixed). Is that much correct? Here $2^X$ is the power set of the set $X$. – Ian May 01 '15 at 13:32
  • Also, as usual: what are your thoughts? – Ian May 01 '15 at 13:33

1 Answers1

0

Yes that is correct if you also add the constraints defined for each problem.

The elements of S are edges on a planar directed graph and the elements of V are directed loops of the graph. E is an ensemble of loops, each with an associated metric.

Sebastien
  • 11