Weighted Bin Packing/Knapsack optimization

Question

I'm struggling to categorise a problem that I'm working on, which means that I haven't been able to figure out if there's any established heuristic solutions. What sort of problem do you think this is, and how would you recommend I solve it?

I have a series of buckets A, B, C, D. Each one can contain a certain number of items. The total size of the buckets matches the size of the population. The items in the population each have a score for A, B, C, D.

I want to sort the items into the buckets such that the total score for matching buckets is maximised; i.e. the A scores for all the items in bucket A, the B scores for all the items in bucket B and so on. It follows that it is possible for an item to ideally be in bucket B even if its A score is higher, as there might be many items with high A scores and few with high B scores.

Answer 1

This looks like minimum-cost maximum flow problem. It's maximum-cost, really, but that can be amended by just negating the weights.

Consider the following network. There is a source, s, and a sink, t.

Every item i is represented by a vertex u_i, with an edge s -> u_i with capacity 1 and cost 0.

Every bucket is also represented by a vertex: v_A v_B, and so on. There is an edge v_A -> t with capacity being the size of group A and cost 0, and similar edges for other groups.

And finally, there are edges u_i -> v_G which have capacity 1 and cost equal to (minus score of putting item i in group G).

Observe that any maximum flow in this network corresponds to a partition of items into groups so that each group has the given size.

Observe that the minimum-cost maximum flow in this network is a partition where the total score of the partition is maximized.

This scales well with the number of items and the number of groups. Also, this easily extends to the case where the size of the groups can vary up to a certain limit, but each item must still belong to one group.

Answer 2

For small enough sizes, a meta heuristic (like local search) might work well.

public class WeightedKnapsackProblem {

private int numberOfBins = 0;
private int numberOfItems = 0;

private int[][] scoreMatrix;
private int[] maxItemsPerBin;

public WeightedKnapsackProblem(int[][] score, int[] maxItemsPerBin){
    this.numberOfItems = score.length;
    this.numberOfBins = score[0].length;
    this.scoreMatrix = score;
    this.maxItemsPerBin = maxItemsPerBin;
}

public int score(int[] assignment){
    int s = 0;
    for(int i=0;i<numberOfItems;i++){
        int item = i;
        int bin = assignment[item];
        s += scoreMatrix[item][bin];
    }
    return s;
}

public int cost(int[] assignment){
    int c = 0;
    int[] tmp = new int[numberOfBins];
    for(int i=0;i<numberOfItems;i++){
        tmp[assignment[i]]++;
    }
    for(int i=0;i<numberOfBins;i++){
        if(tmp[i] > maxItemsPerBin[i])
            c++;
    }
    return c;
}

private java.util.Random RANDOM = new java.util.Random(System.currentTimeMillis());

private int[] mutate(int[] orig){
    int[] out = new int[orig.length];
    for(int i=0;i<orig.length;i++)
        out[i] = orig[i];
    out[RANDOM.nextInt(out.length)] = RANDOM.nextInt(numberOfBins);
    return out;
}

public int[] localSearch(){
    // initial assignment
    int[] a0 = new int[numberOfItems];
    for(int i=0;i<numberOfItems;i++)
        a0[i] = RANDOM.nextInt(numberOfBins);

    // max score for any item
    int max = scoreMatrix[0][0];
    for(int i=0;i<scoreMatrix.length;i++)
        for(int j=0;j<scoreMatrix[i].length;j++)
            max = java.lang.Math.max(max, scoreMatrix[i][j]);

    // local search
    int[] a1 = mutate(a0);
    int c0 = score(a0) - cost(a0) * max * max;
    int c1 = score(a1) - cost(a1) * max * max;
    for(int i=0;i<1000;i++){
        if(c1 > c0){
            a0 = a1;
            c0 = c1;
        }
        a1 = mutate(a0);
        c1 = score(a1) - cost(a1) * max;
    }

    // return
    return a0;
}

public int[] repeatedLocalSearch(int k){

    // max score for any item
    int max = scoreMatrix[0][0];
    for(int i=0;i<scoreMatrix.length;i++)
        for(int j=0;j<scoreMatrix[i].length;j++)
            max = java.lang.Math.max(max, scoreMatrix[i][j]);

    int[] a0 = localSearch();
    int c0 = score(a0) - cost(a0) * max * max;

    for(int i=0;i<k;i++){
        int[] a1 = localSearch();
        int c1 = score(a1) - cost(a1) * max * max;

        if(c1 > c0){
            c0 = c1;
            a0 = a1;
        }
    }

    return a0;
}
}

This program essentially generates a random assignment of items to bins, and iteratively attempts to improve upon that initial situation.

Because you can easily get trapped in local optimums using this technique, it makes sense to repeat this a couple of times, with different (random) starting configurations.

The following program uses the WeightedKnapsackProblem class to generate a possible solution:

    int[][] score = {   {9,5,2,3},
                        {8,9,2,1},
                        {3,2,1,4},
                        {1,2,1,2},
                        {7,8,9,2},
                        {0,1,2,3}
                    };
    int[] maxItemsPerBin = {2,1,2,1};

    WeightedKnapsackProblem wkp = new WeightedKnapsackProblem(score, maxItemsPerBin);
    int[] assignment =  wkp.repeatedLocalSearch(10);

    System.out.println(wkp.score(assignment));
    System.out.println(wkp.cost(assignment));
    System.out.println(Arrays.toString(assignment));

This prints out:

34
0
[0, 1, 0, 3, 2, 2]

In other words, the demo problem can be solved for a maximum score of 34.
The number of misplaced items (that would exceed bin capacity) is 0.

And the assignment is:

• first item in first bin
• second item in second bin
• third item in first bin
• fourth item in fourth bin
• fifth and sixth item in third bin