Maximizing Sum of Weights w/ N Entities & M Constraints

  • Context: Graduate 
  • Thread starter Thread starter kmrstats
  • Start date Start date
  • Tags Tags
    Optimization
Click For Summary
SUMMARY

The discussion centers on maximizing the sum of weights for N entities, each defined by a weight W and similarity coefficients Sij. The goal is to optimize the function Sumi(Wi/Sumj(Sij)) under the constraint of selecting M entities from N, where M is less than N. The user faces challenges with larger values of N (approximately 50) and M (5), making brute-force enumeration impractical. Suggestions include developing an algorithm to efficiently compute the maximum sum.

PREREQUISITES
  • Understanding of combinatorial optimization techniques
  • Familiarity with similarity coefficients in data analysis
  • Knowledge of algorithm design and complexity analysis
  • Proficiency in programming for implementation of algorithms
NEXT STEPS
  • Research "Dynamic Programming for Combinatorial Optimization"
  • Explore "Greedy Algorithms for Maximum Weight Selection"
  • Learn about "Branch and Bound Techniques in Algorithm Design"
  • Investigate "Heuristic Methods for Large-Scale Optimization Problems"
USEFUL FOR

Data scientists, algorithm developers, and researchers in optimization who are dealing with complex weight and similarity calculations in large datasets.

kmrstats
Messages
2
Reaction score
0
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.
 
Mathematics news on Phys.org
You should consider to write a small program.
 

Similar threads

Graduate Heat equation and Theta, Parts I-III
  • · Replies 1 ·
Replies
1
Views
5K