Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Optimization problem

  1. Nov 14, 2011 #1
    I have an optimization problem which am not able to figure out after much thought. Any suggestions on how to go about it are welcome. Thanks in advance.

    given a set of 'n' numbers. I have to find the optimal disjoint subset distribution of the set which minimizes the value given by a function ( The function values over each of the subsets are added to give the total value corresponding to a subset distribution). There's no polynomial formula for the function, the value is computed using a set of rules based on previous results. The function value can be calculated using a code for a given set. The upper bound is the sum of all the numbers in the set and the lower bound is the largest number in the set.

    The order of appearance of numbers in the subset is important (being time values). Within each susbset of the distribution an element appearing prior to a latter element should have a lower indice in the original set.

    Any suggestion will be highly appreciated. Thanks to all
  2. jcsd
  3. Nov 15, 2011 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    You haven't clearly defined a mathematical problem. I don't know what a "disjoint subset distribution" should mean. Let's take an example. Suppose the numbers are 1,2,3,4,5. Are you saying that you have an algorith A that assigns a numerical value to each possible partition of that set? So it assigns a number to the partition {{1},{2,3,4,5}} and another number to the partition {{1},{2,3},{4,5}} ?

    The normal definition of set ( and subset) does not include an "order of appearance" property. So {2,3} and {3,2} are the same set. Are we dealing with some mathematical object that has an order to its component parts, such as a vector?
  4. Nov 16, 2011 #3
    Stephen, thanks for replying.

    1) yeah disjoint subset distribution means the subsets should have no overlapping elements and their union should equal to the entire set in original.

    2) the function computes value for any set ( the value depends on the order of elements in the set. So for a particular subset distribution value is computed for all the subsets and added to give us the value corresponding to that distribution.

    3) The order of appearance is important because the values in a set are arranged according to time. So in any member of the subset distribution and element appearing prior to another element should have a lower indice in the original set than the latter element.


    this can be breaken into
    {a,d},{c,b} >>> this is wrong, cause b appears prior to c in original set (the function gives different value for different orders.

    and other combinations maintaining the order

    3) the problem aims at finding the least valued subset distribution.
    hope u get the problem now ? .
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook