5

私は Choco と CP をまったく初めて使用しますが、Steiner ツリーの問題を解決するための小さなモデルを作成しています。Choco は、グラフが何であれ、最初のノードが true になるように強制し続けます (正しくないことを確認しました)。

esエッジがソリューション内にある場合は ==1、それ以外の場合は ==0 の IntVarの配列があります。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

私が使用していた Choco3 のバージョンにはバグがありました。3.3.0 で解決されました。同じ問題がある場合は、それを使用してください:)

于 2015-07-26T01:29:37.100 に答える