Maximizing Sum of Weights w/ N Entities & M Constraints

[kmrstats]

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 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₁/(S_1,2+S_1,3)+W₂/(S_2,1+S_2,3)+W₃/(S_3,1+S_3,2)
W₁/(S_1,2+S_1,4)+W₂/(S_2,1+S_2,4)+W₄/(S_4,1+S_4,2)
W₁/(S_1,3+S_1,4)+W₃/(S_3,1+S_3,4)+W₄/(S_4,1+S_4,3)
W₂/(S_2,3+S_2,4)+W₃/(S_3,2+S_3,4)+W₄/(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.

 

[fresh_42]

You should consider to write a small program.