All geek questions in one place

Choco forces a variable to true when it shouldn't

I am completely new to Choco and CP, but I am making a small model to solve the Steiner tree problem, and Choco continues to force the first node to be true no matter what the graph is (and this is not correct, I checked).

I have an es array for IntVar that is == 1 if the edge is in the solution, or == 0 otherwise. The same goes for the vs array, which sets the vertices. I use the activeEdgeW array to have a scalar constraint where the coefficients are variables. Then I have channel limits, tree limit and sum limit == w. And minimize w. Pretty simple, but somehow vs[0] == true always, for any chart.

My model is honestly pretty simple, I really don't know where this 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);

What is my model, the rest of the program is just the graph data.

Are there any clues about where this is happening? I tried putting the nodes in different orders in UB , but always the first node insists on being in. I tried to remove the channel restriction, and it showed me that the node is not always true, but the edge reaching it should be, so it becomes true. However, as you can easily see, I have no restrictions on the es array, which would make the edge be true.

Thanks for the help!

+6
source share
2 answers

There was a bug in the version of Choco3 that I used. This was resolved in 3.3.0. Use this option if you have the same problem :)

0
source

"I'm completely new to Choco and CP."

Previously, I was captured by instruments that either started or did not start counting to zero, and I took the opposite case (counting starts with one). The behavior you describe belongs to this category of errors, so you can verify that it all starts with arrays with a zero value.

0
source

Source: https://habr.com/ru/post/986489/

More articles:


All Articles