5

我对 Choco 和 CP 完全陌生，但我正在制作一个小模型来解决 Steiner 树问题，并且无论图表是什么，Choco 都会不断强制第一个节点为真（并且它不正确，我检查了）。

我有一个 IntVar 数组es，如果边缘在解决方案中，则 ==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，可以强制边缘为真。

谢谢您的帮助！

4

2 回答 2

0

“我对 Choco 和 CP 完全陌生”

在过去，我被一些工具所吸引，这些工具要么从零开始计数，要么不从零开始计数，我假设了相反的情况（计数从一开始）。您所描述的行为属于此类错误，因此您可以验证所有这些都是从从零开始的数组开始的。

于 2015-05-24T18:20:10.493 回答
0

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

于 2015-07-26T01:29:37.100 回答