当我在java中使用chocosolver运行背包问题求解器时,我在基准测试中的somme问题示例上发现了这个错误:“objective variable(total_value={516..568})没有在solution上示例化。检查约束和/或决策变量。”
我的代码与choco解算器的默认设置完美配合。但是我在这个.solver.setsearch(intvarsearch(…))中加入了一个研究启发之后发现了这个错误;
查看“如何初始化研究算法”一节。
我的代码
一般行为:我为问题中的每一项创建一个变量。这些值可以等于1(在解决方案中获取的对象)或0(未获取的对象)。我还添加了一个目标变量,即每个项目的值之和。这就是我们要最大化的法鲁。然后在这些变量上添加约束。
如果要运行完整代码,请将其放在publig github存储库中:https://github.com/hbonnavaud/knapsackproblemsolver.
如何初始化:
this.problem = problem;
// Init choco
this.model = new Model("BackPackProblem");
// variables initialisation
// Pour chaque objet, on ajoute une variable booléenne.
// Si cette variable vaut 1, on prend l'objet, si non on ne le prend pas.
this.vars = model.intVarArray("X", problem.getItemsSize(), 0, 1, false);
this.totalValue = model.intVar("Total_Value", 0, problem.getTotalValueUpperBound());
// Constraints initialisation
int[] poids = new int[problem.getItemsSize()];
int[] valeurs = new int[problem.getItemsSize()];
for (int i = 0; i < problem.getItemsSize(); i++) {
poids[i] = problem.getItem(i).getWeight();
valeurs[i] = problem.getItem(i).getValue();
}
// add constraints on objects weights
model.scalar(vars, poids, "<=", problem.getBagCapacity()).post();
// add constraint on the total value, the one that isn't instanciated at the end
model.scalar(vars, valeurs, "=", totalValue).post(); // objects value
model.setObjective(Model.MAXIMIZE, totalValue); // define objective function
this.solver = model.getSolver(); // Solver initialisation
我如何初始化研究算法:
this.solver.setSearch(intVarSearch(
// variable selector
(VariableSelector<IntVar>) variables -> {
// Before to select an item to take in our bag, we need to know it there is enough place for it.
// Let calculate the bag current size
int totalWeight = 0;
for (int index = 0; index < this.vars.length; index ++) {
if (this.vars[index].isInstantiated()) {
totalWeight += this.vars[index].getValue() * problem.getItem(index).getWeight();
}
}
// We should return the variable that correspond to the item with the best weight
// in every unset variables
Double bestRatioFound = null;
Integer bestItemIndex = null;
for (int index = 0; index < this.vars.length; index ++) {
double itemRatio = problem.getItem(index).getRatio();
if (!this.vars[index].isInstantiated()
&& (bestRatioFound == null || bestRatioFound < itemRatio)
&& totalWeight + problem.getItem(index).getWeight() < problem.getBagCapacity()) {
bestRatioFound = itemRatio;
bestItemIndex = index;
}
}
// Now we found our variable index, we can return it.
if (bestItemIndex == null) {
return null;
} else return this.vars[bestItemIndex];
},
// value selector
(IntValueSelector) var -> 1,
// variables to branch on
vars
));
我如何启动决议:
// Final solution interface initialisation
this.solution = new int[problem.getItemsSize()];
this.solutionTotalBagValue = 0;
this.solutionTotalBagWeight = 0;
// Find the final solution
while(solver.solve()){
for (int i = 0; i < problem.getItemsSize(); i ++) {
solution[i] = vars[i].getValue();
}
solutionTotalBagValue = totalValue.getValue();
this.resolutionTime = (double) solver.getTimeToBestSolution();
}
然后我把结果打印出来,但这里没用。
我试过的
我试图强制这个.totalvalue示例化,但它没有用,因为它是一个“目标变量”,然后它需要进行研究,因为它需要在之前示例化所有其他变量。
我试图强制解析循环继续,直到这个“目标变量”被示例化,但我没有找到如何在互联网上做到这一点。
现在我没有更多的想法,也没有在网上找到任何关于它的东西。因此,任何帮助/新想法都将不胜感激。
祝你好运,赫德温。
暂无答案!
目前还没有任何答案,快来回答吧!