MATLAB Answers

Minimize Difference in Partition Sums from Experimental Data

2 views (last 30 days)
Jeffrey Corbets
Jeffrey Corbets on 26 Nov 2020
Edited: Bruno Luong on 27 Nov 2020
I have a 2,000 row dataset representing measured data. I would like to create 60 partitions of 30 measurements (discarding the 200 outliers or "worst contributors") with the partitions created to minimize the differences in the sum of the measurements in each partition. Or, perhaps more simply, I want each partition to have as close as possible to the same sum of the measurements in partition.
My first attempt was based on a random sampling approach, which was inefficient as expected. I am considering a histogram-based approach for my next attempt, but wanted to sample the community for ideas or best practices first.
Thanks!

  2 Comments

Bjorn Gustavsson
Bjorn Gustavsson on 26 Nov 2020
This sounds like a variant of the knapsack-problem - that similarity makes me think that it is a hard problem, but that also means that there should be algorithms for this available...
Bruno Luong
Bruno Luong on 27 Nov 2020
Do you really want to find the best partitions (which is very hard to solve) or you just want to have partitions having the sums that are "close enough"?

Sign in to comment.

Answers (1)

Bjorn Gustavsson
Bjorn Gustavsson on 26 Nov 2020
Yup, you will find the algorithm and information here: partition problem (wikipedia).
HTH

  2 Comments

Jeffrey Corbets
Jeffrey Corbets on 27 Nov 2020
I looked at those algorithms and they seem limited to the sets of positive integers without easy ways to generalize to real numbers. In my situation the measurements are real numbers and the differences between the measurements are to the right of the decimal place.
The knapsack problem is a good generalization of my situation. I will read up and see if any of the algorithms available will meet my needs.
Thanks!
Bjorn Gustavsson
Bjorn Gustavsson on 27 Nov 2020
That's a bit of a bummer - and also slightly confusing to me, I cannot see why they should be that restricted, perhaps that is somewhat of a artificial limitation (since you will be using finite precision numbers they are not really real numbers anyway?). Perhaps some of the algorithms can be adapted anyway....

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!