Grouping constrained optimization

[Sebastien77]

Hi all,

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

Assume a set S of elements k_i and a set V of possible groupings G_j. A grouping G_j is a subset of S. Associate a weight w_ij to each mapping k_i to G_j. The weights are infinite if k_i ⊄ G_j, and finite signed number if k_i ⊂ G_j.

1) Find the set of mappings from S to V minimizing the sum of the associated weights under the constraint that each element of S can be involved in exactly one or no mapping.

2) Same question but by changing the constraint to "under the constraint that each element of S must be involved in exactly one mapping".

Note: For my application V is a minute fraction of all possible groupings of the elements of S.Sébastien

 

[Stephen Tashi]

A grouping G_j is a subset of S.

Perhaps you mean that a grouping is a collection of subsets of S that partition it in some way. If you want a "grouping" of S merely to be a subset of S, you should just call it a subset.

Associate a weight w_ij to each mapping k_i to G_j.

It isn't clear what set of mappings you are talking about. Let's consider one of these mappings. What is its domain and what is its codomain?

Does $w_{ij}$ depend only on the indices $i,j$ or can there be a different $w_{i,j}$ for each mapping?

 

[Sebastien77]

Yes, sorry. I hope the following will clarify:

S is a finite set of elements k_i
V is a subset of S, e.g. v₄={k₁,k₃}
E is a finite ensemble of V, e.g. E = { v₁={k₁}, v₂={k₁,k₂}, v₄={k₁,k₃}, v₄={k₂,k₄,k₅} }
f(S, V) → ]-∞,∞], (k_i,v_j) → w_ij, with w_ij infinite only if k_i ⊄ v_j.

The problem is to find the ensemble M of 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 one or no 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)

 

[Stephen Tashi]

Yes, sorry. I hope the following will clarify:

S is a finite set of elements k_i
V is a subset of S, e.g. v₄={k₁,k₃}

I think you mean that $V$ is a set whose members are each subsets of $S$. Do you want them to be distinct subsets? For example, can we have $v_4 = \{k_1, k_2\}$ and $v_5 = \{k_1, k_2\}$

E is a finite ensemble of V, e.g. E = { v₁={k₁}, v₂={k₁,k₂}, v₄={k₁,k₃}, v₄={k₂,k₄,k₅} }

f(S, V) → ]-∞,∞], (k_i,v_j) → w_ij, with w_ij infinite only if k_i ⊄ v_j.

Do you mean "infinite if and only if $k_i \notin v_j$" ?

The problem is to find the ensemble M of 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 one or no element of M

In that context, I think "member of one" means "member of exactly one" (as opposed to "member of at least one").

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)

If this problem arises from an application, it might help to tell about the application.

 

[Sebastien77]

I think you mean that $V$ is a set whose members are each subsets of $S$. Do you want them to be distinct subsets? For example, can we have $v_4 = \{k_1, k_2\}$ and $v_5 = \{k_1, k_2\}$

Do you mean "infinite if and only if $k_i \notin v_j$" ?

In that context, I think "member of one" means "member of exactly one" (as opposed to "member of at least one").

If this problem arises from an application, it might help to tell about the application.

Yes, I was inaccurate, they should be distinct subsets.
Yes, I meant "infinite if and only if $k_i \notin v_j$", thanks for the correction.
Yes, "member of exactly one" (problem 2) and "member of exactly one or not member of any" (problem 1).
The elements of S are the edges of a planar graph and I am looking for an ensemble of oriented loops with no common oriented edge that would optimize a given metric.