Hi. I have a problem I am hoping you all can shed some light on.(adsbygoogle = window.adsbygoogle || []).push({});

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 O_{i}as (W_{i}, S_{ij, j=(1,2,...,N, i!=j})(?).

Given an integer M and M < N I need to maximize the following function:

Sum_{i}(W_{i}/Sum_{j}(S_{ij, 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:

W_{1}/(S_{1,2}+S_{1,3})+W_{2}/(S_{2,1}+S_{2,3})+W_{3}/(S_{3,1}+S_{3,2})

W_{1}/(S_{1,2}+S_{1,4})+W_{2}/(S_{2,1}+S_{2,4})+W_{4}/(S_{4,1}+S_{4,2})

W_{1}/(S_{1,3}+S_{1,4})+W_{3}/(S_{3,1}+S_{3,4})+W_{4}/(S_{4,1}+S_{4,3})

W_{2}/(S_{2,3}+S_{2,4})+W_{3}/(S_{3,2}+S_{3,4})+W_{4}/(S_{4,2}+S_{4,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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Optimization problem

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**