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

Question

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

我有一个 IntVar 数组 es 如果边在解中则 ==1，否则 ==0。对于设置顶点的数组 vs 也是如此。我使用数组 activeEdgeW 能够在 coeffs 可变的情况下具有标量约束。然后我只有 channel 约束、树约束和 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 中，但总是第一个节点坚持在。我试图移除 channel 约束，它告诉我节点并不总是正确的，但到达它的边缘必须是正确的，所以它变成了正确的。尽管如此，正如您可以轻松看到的那样，我对数组 es 没有任何强制边缘为真的限制。

感谢您的帮助!

Answer 1

"I am totally new to Choco and CP"

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