logo标签列表

加权装箱/背包优化

algorithmmachine-learningmixed-integer-programmingoperations-research
4

我正在努力将我正在处理的问题归类，这意味着我还没有找到是否有任何已建立的启发式解决方案。您认为这是什么样的问题，您会推荐我如何解决它？

我有一系列的桶A、B、C、D。每个桶都可以容纳一定数量的物品。桶的总大小与人口的大小相匹配。人口中的物品每个都有A、B、C、D的得分。

我想将物品分类到桶中，使得匹配桶的总得分最大化；即所有物品在桶A中的A分数、在桶B中的B分数等等。因此，即使一个物品的A分数更高，它也可能理想地放在桶B中，因为可能有许多具有高A分数和少量高B分数的物品。

2
应该在 cs stackexchange 上发布吗？ - shimao
你可以尝试使用列生成算法来得到一个好的解决方案。Column generation - hilberts_drinking_problem
我是否正确地认为，只有通过进行暴力搜索才能实现最优解，即问题是NP完全问题？ - PMF
@PMF 不是的，请看我的回答。它在多项式时间内找到了最优解，因为流量的最大容量受到物品数量的限制。这里有一堆适用的算法。 - Gassa
@PMF 如果没有其他更好的方法，对于四个组A、B、C和D，可以通过动态规划在O(n^5)的时间复杂度内解决，其中n是物品数量。函数将为：f（已访问物品数量，第1组中的剩余空间，第2组中的剩余空间，第3组中的剩余空间，第4组中的剩余空间）=最佳得分。 - Gassa
2个回答
2
这看起来像是最小费用最大流问题。 实际上是最大费用，但只需通过对权重取反即可进行修正。
考虑以下网络。 有一个源点s和一个汇点t。
每个项目i由顶点ui表示，具有容量为1且成本为0的边s->ui。
每个桶也由一个顶点表示：vA vB等等。有一条从vA到t的边，其容量为组A的大小，成本为0，并且其他组也有类似的边。
最后，有边ui->vG，其容量为1，成本等于将项目i放入组G的分数的负值。
观察到，该网络中的任何最大流都对应于将项目划分为各组，以使每个组具有给定的大小。
观察这个网络中的最小成本最大流，其结果是将所有物品分为若干组，且每组得分之和最大。这种方法适用于处理大量物品和分组，而且能够轻松地扩展到一些组的大小可以在特定限制范围内变化的情况，但每个物品仍需属于一个组。
实际上，看起来我们可以通过将s->u_i->v_G路径缩成容量为1且带有负分数成本的s->v_G边来消除实现中的顶点u_i。然而，这意味着在相同的顶点对之间引入多条边。我认为最初的解释更易于理解，所以将其保留为注释。 - Gassa
0
对于足够小的规模，元启发式算法（如局部搜索）可能效果良好。
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;
}
}

这个程序基本上会将项目随机分配到垃圾桶中，并迭代地试图改善初始情况。

因为使用这种技术很容易被困在局部最优解中，所以重复几次，使用不同的（随机）起始配置是有意义的。

以下程序使用WeightedKnapsackProblem类生成可能的解决方案：

    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));

这将打印出：

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

换句话说，演示问题的最高得分为34分。
超过容量的错位物品数量为0。
而该任务的分配方式如下：
  • 第一个项目放在第一个箱子里
  • 第二个项目放在第二个箱子里
  • 第三个项目放在第一个箱子里
  • 第四个项目放在第四个箱子里
  • 第五和第六个项目放在第三个箱子里
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接