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. Jul 23, 2008 #1
    Hi. I have a problem I am hoping you all can shed some light on.

    I have N entities, O, each described by N values - a weight W and N-1 similarity coefficients to the other N-1 entities. I guess we can represent Oi as (Wi, Sij, j=(1,2,...,N, i!=j)(?).

    Given an integer M and M < N I need to maximize the following function:
    Sumi(Wi/Sumj(Sij, j=(1,2,...,N), i!=j))
    where i and j in the sums are constrained to the unique combinations of the integers 1 to N of size M.
    As an example let N=4, M=3 there are then 4 unique combinations of the numbers 1,2,3,4 of size 3: (1,2,3), (1,2,4), (1,3,4) and (2,3,4). The values for the function are therefore:
    W1/(S1,2+S1,3)+W2/(S2,1+S2,3)+W3/(S3,1+S3,2)
    W1/(S1,2+S1,4)+W2/(S2,1+S2,4)+W4/(S4,1+S4,2)
    W1/(S1,3+S1,4)+W3/(S3,1+S3,4)+W4/(S4,1+S4,3)
    W2/(S2,3+S2,4)+W3/(S3,2+S3,4)+W4/(S4,2+S4,3).

    For small N and M I can enumerate the combinations and calculate the maximum sum but my problem has N~50 and M~5.

    Any suggestions or thoughts of an akgorithm to calulate the max? I hope I have made it clear.

    Thanks in advance.
     
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?
Draft saved Draft deleted



Similar Discussions: Optimization problem
  1. Optimization problem (Replies: 5)

  2. Optimization problems (Replies: 0)

  3. Optimization Problem (Replies: 1)

  4. Optimalization problem (Replies: 4)

Loading...