使用 Choco Solver 在背包中分配物品

Question

我尝试通过 JAVA 使用 Choco Solver 实现一个多维背包问题。我的想法是在 2 个背包中分配 3 个项目。

我的物品有重量和背包限制： int[] itemWeight = {2, 2, 2}; int[] 背包限制 = {4, 4};

还有我的决策变量，其中 3 个项目在 {0, 1} 之间有一个背包： int[] itemAllocation = {1, 1, 0};

我用 Choco Solver 写了这个问题:

Model model = new Model("KnapsackProblem");

// Allocation variable
IntVar[] x = new IntVar[3];
for (int i = 0; i < itemNumber; i++) {
    x[i] = model.intVar("x"+i, 0, knapsackNumber-1);
}

// Knapsack capacities variables
IntVar[] limitVar = new IntVar[knapsackNumber];
for (int i = 0; i < knapsackNumber; i++) {
    limit[i] = model.intVar(knapsackLimit[i]);
}

IntVar[] itemWeightVar = new IntVar[itemNumber];
for (int i = 0; i < itemNumber; i++) {
    itemWeightVar[i] = model.intVar(0, 2);
    model.element(itemWeightVar[i], itemWeight,x[i]);
}

// Limit Cosntraints
for (int i = 0; i < knapsackNumber; i++) {
    model.sum(itemWeightVar, "<=", limit[x[i].getValue()]);
}

model.getSolver().solve();

很遗憾，此方法无效。我总是得到以下分配：[x0 = 0, x1 = 0, x2 = 0]

提前致谢。

Answer 1

这是一个常见的错误，您只是忘记了 POST 您的约束，所以它们没有被考虑在内。例如，您应该替换

model.element(itemWeightVar[i], itemWeight,x[i]);

来自

model.element(itemWeightVar[i], itemWeight,x[i]).post();

请注意，post 不是自动的，因为您可能希望具体化约束而不是 posting 它（例如发生在 ifThen 语句中）。

最佳，

https://www.cosling.com/

使用 Choco Solver 在背包中分配物品

Item allocation in a knapsack with Choco Solver

java

choco