1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Grouping constrained optimization

  1. Apr 28, 2015 #1
    Hi all,

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

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

    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.

  2. jcsd
  3. Apr 30, 2015 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    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.

    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 [itex] w_{ij} [/itex] depend only on the indices [itex]i,j [/itex] or can there be a different [itex] w_{i,j} [/itex] for each mapping?
  4. May 1, 2015 #3
    Yes, sorry. I hope the following will clarify:

    S is a finite set of elements ki
    V is a subset of S, e.g. v4={k1,k3}
    E is a finite ensemble of V, e.g. E = { v1={k1}, v2={k1,k2}, v4={k1,k3}, v4={k2,k4,k5} }
    f(S, V) → ]-∞,∞], (ki,vj) → wij, with wij infinite only if kivj.

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

    Problem 1) each ki is member of one or no element of M
    Problem 2) each ki is member of exactly one element of M (for this case we assume that at least a valid solution exists in E)
  5. May 1, 2015 #4

    Stephen Tashi

    User Avatar
    Science Advisor

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

    Do you mean "infinite if and only if [itex] k_i \notin v_j [/itex]" ?

    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.
  6. May 1, 2015 #5
    Yes, I was inaccurate, they should be distinct subsets.
    Yes, I meant "infinite if and only if [itex] k_i \notin v_j [/itex]", 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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook