I am totally new to Choco and CP, but I am making a little model to solve the Steiner tree problem, and Choco keeps forcing the first node to be true whatever the graph is (and its not correct, I checked).
I have an array es of IntVar that ==1 if the edge is in the solution, or ==0 otherwise. Same for the array vs that sets vertices.
I use the array activeEdgeW to be able to have a scalar constraint where the coeffs are variable.
Then I just have the channeling constraints, the tree constraint and the sum == w constraint. And minimize w. Fairly simple, but for some reason vs[0] == true always, for any graph.
My model is honestly pretty simple, I really don't know where that comes from:
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);
That's my model, the rest of the program is just the graph data.
Does any one have any clue of where this is coming? I tried putting the nodes in different orders in UB, but always the first node insists in being in.
I tried to remove the channeling constraint, and it showed me that the node is not always true, but an edge reaching it must be, so it becomes true. Nevertheless, as you can easily see, I have no constraints on the array es that would force an edge to be true whatsoever.
Thanks for the help!
