Re: List partitioning

bborcic@xxxxxxxxx a écrit :
On 28 oct, 19:22, bim <inva...@xxxxxxxxxx> wrote:
I'm not sure to get exactly what you mean right now, given that I have
two values assigned to each solution (Balance and Dispersion), and that
I need first to get the solution with {min(Dispersion) and
min(Balance)],

How are they defined (well I gather one is related to "Size" and the
other to "Weight")

That's what I called "BalanceHeuristic" and "DispersionHeuristic" when I explained the problem:
" -BalanceHeuristic: sum of the groups weights deviation from the mean group weight
-DispersionHeuristic: sum of the initial groups (PreGroups) broken by each final group"

Sorry if didn't go too far in my explanations, but I didn't want it to look like I want someone to do the job for me :/

Actually I don't need these exact values, I just produced them as measurements of how well balanced (Balance) and how much respecting PreGroups (Dispersion) a solution is. So I can apply "labeling([min()]" to them.

Balance is indeed related to "Weight", however Dispersion isn't related to "Size" at all.
Here is how I chose to compute Dispersion:
For each group made (FinalGroup):
For each initial group (PreGroup):
if the FinalGroup contains at least one of the PreGroup items but not all of them, then Dispersion++
EndFor
EndFor

Concerning "Size", the constraint is "each group must have the same size, or only differ by 1 from the other if it isn't possible". I don't need any measurement of it from the final goal "balance", since all the solutions are already built in a way they respect this constraint (it can be considered as the first constraint a solution must fulfill).

and more importantly what does "and" mean if the
two minimizattions conflict ? Is it a lexicographical ordering, ie
min(Dispersion) and for the same value of Dispersion, min(Balance) ?

Actually, I plan to let the user choose the behaviour he wants, among these:

First possibility, PreGroups should not be broken:
- find a solution minimizing Dispersion first, and then minimizing Balance with this minimal value of Dispersion

Second possibility, PreGroups can be broken as long as it allows to improve Balance:
- find a solution minimizing Balance first, and then minimizing Dispersion with this minimal value of Balance (that's my example: "labeling([min(Bal),min(Dis)] [...]")

Third possibility, PreGroups can be broken as long as Balance isn't good enough:
- find a solution minimizing Dispersion first, and then minimizing Balance with this minimal value of Dispersion
- if balance isn't good enough in this first solution, then look for another solution with following constraints:
minimize Dispersion with Balance < X (X depends on initial conditions: total items size, number of groups to make...)

I also thought about a fourth possibility: minimizing "Balance+Dispersion" (with appropriate coefficients), but I'm not sure it's suitable in my case...

In your case, isn't Dispersion measured as the sum over component
groups, of the difference of the group's size to the average size
(which is fixed for a problem case),

The Dispersion is a measurement of how many PreGroups are broken by FinalGroups.
The Size constraint isn't measured as it must be fulfilled entirely (this contraint is directly integrated in the code).

and Balance samewise while exchanging weight for size ?

Yes

In that case, if it happens say that the
aggregate desirability of the complete solution can be expressed as a
linear function of both Dispersion and Balance, this value can be
viewed as the sum of a contribution by each group that does not depend
on that group being considered in the context of a particular
partition.

Yes but these groups aren't independant. I understand I have more chances to find a better solution in a given time using this method, however I can't be sure it is the best solution unless I try all of them , and then I don't see the benefit of this method (it's very rare to find a solution where both Dispersion=0 and Balance=0, which is the only case where I know I have a best solution).
.