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!

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:

    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted