Grouping a list of n integers (value = Xn) into m non-empty subsets of a maximum given size (S > sum(Xn) within group) such that m is minimized

[Appo]

Hello !

I hope the title didn’t scare you. I’m trying to regroup columns that i have into groups of a given size.

I have a table with is formatted the following way:

Descriptive Data 1 | Descriptive Data 2 | X1 | X2 | … | X722 | X723
…
…

Where X1,…, X723 are integers (a vast majority is zeros) that i want to base my groups on, such that the sum within the generated groups is equal to 80 or less. The important element is that i would like the number of groups per line to be the minimum.

Blabla 1 | Blabla 2 | 45 | 45 | 15 | 10 ------> the result i want for this line is the number of groups and their respective size —> 2 groups ( 45+15+10 = 70, 45=45)

I hope my question is clear,

Thanks

[Martyna]

Hi @Appo,

Thanks for your question, that sounds tricky.
I’m not sure if I got what you plan to do. When you mean groups, do you mean row-wise and it’s one group per row?
How about sorting every row X1,…, X723 first and then checking column-wise if the sum of every new column is still <= 80. This should give you the smallest number of groups (If I understood correctly what you want to do…).

Is this an optimization issue you are trying to solve? reminds me a bit of a bin-packing problem
Best,
Martyna

[Appo]

Thanks for the answer.

I indeed want to group row wise. The format i mentionned comes from me pivoting the source data. Not sure it is the best approach.

Never heard of the bin-packing problem but it surely looks like what i want to do for each of my lines of my table ! Going to look further into it.

Much appreciated

Bin Packing

Input: weight = {4, 8, 1, 4, 2, 1}
Bin Capacity c = 10
Output: 2
We need minimum 2 bins to accommodate all items
First bin contains {4, 4, 2} and second bin {8, 1, 1}

[Martyna]

Hi!

ok, so what I could imagine that could work (as there is no out-of-the-box solution/bode that can do that).
I would start to iterate through it row-wise using loop nodes and transpose it so it becomes a column, sort to get the max values on the top, and then summarize and check if it’s 80 or less.
This is at least how I would start

Best,
Martyna

[Appo]

@Martyna

to iterate through it row-wise using loop nodes and transpose it so it becomes a column, sort to get the max values on the top, and then summarize and check if it’s 80 or less.

I am not sure what you mean by summarizing ?

For the moment i went back prior to the pivoting, and i am summing within a group loop (which is the line resulting from the pivot) with the condition of the sums to not exceed 80.

Currently i have a non optimal solution, but it is one regardless.

I’m imagining something similar where i do a chunk loop where i have a list of values that i have to test until i run out of valable option to pack my 80s, then i create a new bin… and this for every group loop.

[Martyna]

I am not sure what you mean by summarizing ?

Probably the same as you with summing

Did you find your solution or are there any open questions that would need some examples to be solved?

[Daniel_Weikert]

There is a package in python. So maybe that is an option for you?

binpacking

[Appo]

@Martyna That should be alright i think, I just need to add a sort to what I have. To get what you proposed

@Daniel_Weikert I’m going to look into it ! I Looks promising, I haven’t touched Python in my life but i imagine i can figure this out. I’ll be back