Choco 在不应该的情况下强制变量为真

Question

我对 Choco 和 CP 完全陌生，但我正在制作一个小模型来解决 Steiner 树问题，Choco 一直强制第一个节点为真，无论图形是什么（它不正确，我检查过).

我有一个 es 的 IntVar 数组，如果边在解中则 ==1，否则 ==0。与设置顶点的数组 vs 相同。我使用数组 activeEdgeW 来实现系数可变的标量约束。然后我只有通道约束、树约束和 sum == 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 没有任何强制边缘为真的约束。

感谢您的帮助！

Answer 1

"I am totally new to Choco and CP"

过去，我曾遇到过从零开始计数或不从零开始计数的工具，我假设情况正好相反（计数从一开始）。您描述的行为属于此类错误，因此您可以验证所有这些都是从零开始的数组。

Answer 2

我使用的 Choco3 版本有一个错误。它在 3.3.0 中得到解决。如果您有同样的问题，请使用那个:)

Choco 在不应该的情况下强制变量为真

Choco forces a variable to true when it shouldn't

java

constraint-programming

choco