How to distribute n number of weighted articles of different colors to m groups

We have some articles having different colors and weight like :

  Blue(8) Blue(4) Blue(1) Red(4) Red(1) Black(16) Black(2) ...... n elements*

We need to divide these into m groups such that weight of all the groups is equal or very near to each other and variation of color in between each group is minimal. Variation is defined like in group 1 we have 1 crossing from blue to red. Crossing like these should be minimal.

Group 1 -> Blue(8) Blue(4) Blue(1) Red(1)

Group 2 -> Black(16) Black(2)

. . . . m groups

"groups such that weight .. and variation of color ..."

You have two unrelated objectives. It is easy to optimize for one or the other. But how to combine them? You need to specify your objective function - ideally a linear combination of your measures of weight variation and of color variation. When you have done that you can solve this by linear programming or a specialized bin packing algorithm.

Variation is defined like in group 1 we have 1 crossing from blue to red. Crossing like these should be minimal

Assuming you can order the articles in a group, this simplifies to the number of different colors in a group minus 1

Suggested objective function:

Let Cg be the number of different colors in group g minus 1

Let D be the standard deviation of total weight in each group

Let Ww be the relative importance you assign to weight variation

Let Wc be the relative importance you assign to color variation

Ww + Wc = 1

Minimize Ww * D + Wc * ( sum of Cg over m )

The objective function can be minimized using a mixed integer linear programming library.

You need the integers because the decision variables are binary 0 or 1. For example Xag is 1 or 0 depending if article a is assigned to group g.

==========================

Note that for the example you posted, when the 'even load' bin packing algorithm is used, it just so happens that the result for m = 2 is that each group has one 'color crossing'. This might be the solution you want? However, for a different example and certainly for significantly larger examples, thing will rareley work out so neatly. You will definitely need to specify an objective function that balances weight AND color variances.

For what it is worth, here is the code to run the even load bin packing algorithm:

void cSolver::solve()
{
    // construct packing engine
    // https://codeberg.org/JamesBremner/PackEngine
    raven::pack::cEngine PackEngine;

    // set algorithm to 'even bin weights'
    PackEngine.setAlgo(
        raven::pack::cEngine::eBestSpaceAlgo::evenBinLoad);

    // specify bins of almost infinite space
    for (int k = 0; k < myGroupCount; k++)
        PackEngine.addBin(INT_MAX);

    // specify loads
    for (auto &a : myArticles)
        PackEngine.addItem(raven::pack::cItem(a.myWeight))
            .data(&a);

    // Do the pack
    PackEngine.pack();

    // Store articles assigned to each bin
    myAssigns.clear();
    for (int k = 0; k < myGroupCount; k++)
    {
        std::vector<sArticle> group;
        for (auto &item : PackEngine.getPackBin(k))
        {
            group.push_back(*(sArticle *)item.data());
        }
        myAssigns.push_back(group);
    }
}

which outputs

Complete application code at https://codeberg.org/JamesBremner/ColouredWeights

=====================

Now, lets change the focus away from weight equalization to minimizing color variation inside groups. If Cn is the number of different colors then this is trivial of m >= Cn - just place each color in its own group.

If m < Cn we only need to be slightly more careful

1. Let V = floor( Cn / m ) : Place V colors in each group

2. Let E = floor ( Cn - V ) / m : Place E colors in each group

3. Repeat step 2 until E becomes zero

Code:

void cSolver::color()
{
    int Cn = sArticle::colorCount();
    myAssigns.clear();
    if (myGroupCount > Cn)
    {
        myAssigns.resize(Cn);
        for (auto &a : myArticles)
        {
            myAssigns[a.myColor - 1].push_back(a);
        }
    }
}

Displays: