Напълно нов съм в Choco и CP, но правя малък модел за решаване на проблема с дървото на Steiner и Choco продължава да принуждава първия възел да бъде верен, каквато и да е графиката (и не е правилен, проверих).
Имам масив es
от IntVar, който ==1, ако ръбът е в решението, или ==0 в противен случай. Същото за масива vs
, който задава върхове. Използвам масива activeEdgeW
, за да мога да имам скаларно ограничение, където коефициентите са променливи. След това имам само ограниченията за канализиране, ограничението на дървото и ограничението сума == w. И минимизирайте w. Доста просто, но по някаква причина vs[0] == true
винаги, за всяка графика.
Моят модел е честно казано доста прост, наистина не знам откъде идва това:
s = new Solver("Solver");
vs = VF.boolArray("vs", nbV, s);
es = VF.boolArray("es", nbE, s);
w = VF.integer("w", 0, maxW, s);
IntVar[] activeEdgeW = new IntVar[nbE];
for(int i = 0; i < nbE; i++) {
activeEdgeW[i] = VF.enumerated("activeEdgeW["+i+"]", new int[]{0,ws[i]}, s); //Weight is either 0 or ws[i]
ICF.arithm(activeEdgeW[i], "=", ws[i]).reifyWith(es[i]); //weight of edge is ws[i] if edge is in, 0 otherwise
}
UndirectedGraph UB = new UndirectedGraph(s, nbV, SetType.BITSET, false);
UndirectedGraph LB = new UndirectedGraph(s, nbV, SetType.BITSET, false);
//Building upper bound graph: has all nodes and edges
for (int i = 0; i < nbV; i++){
UB.addNode(i);
}
for (int i = 0; i < nbE; i++){
UB.addEdge(endnodes[i][0], endnodes[i][1]);
}
//Building lower bound graph. Must contain Steiner nodes
for (int i = 0; i < nbT; i++) {
LB.addNode(terminals[i]);
}
g = GraphVarFactory.undirected_graph_var("Solution", LB, UB, s);
s.post(GCF.tree(g));
s.post(ICF.sum(activeEdgeW, w));
s.post(GCF.nodes_channeling(g, vs));
for (int i = 0; i < nbE; i++) {
s.post(GCF.edge_channeling(g, es[i], endnodes[i][0], endnodes[i][1]));
}
s.plugMonitor((IMonitorSolution) () -> output());
s.findOptimalSolution(ResolutionPolicy.MINIMIZE, w);
Това е моят модел, останалата част от програмата са само данните от графиката.
Някой има ли представа къде идва това? Опитах се да поставя възлите в различен ред в UB
, но винаги първият възел настоява да бъде вътре. Опитах се да премахна ограничението за канализиране и то ми показа, че възелът не винаги е верен, но ръбът, който го достига, трябва да бъде, така че става истина. Въпреки това, както можете лесно да видите, нямам ограничения върху масива es
, които биха принудили ребро да бъде истина.
Благодаря за помощта!