Choco принуждава променлива да стане true, когато не трябва

Напълно нов съм в Choco и CP, но правя малък модел за решаване на проблема с дървото на Steiner и Choco продължава да принуждава първия възел да бъде верен, каквато и да е графиката (и не е правилен, проверих).

Имам масив es от IntVar, който ==1, ако ръбът е в решението, или ==0 в противен случай. Същото за масива vs, който задава върхове. Използвам масива activeEdgeW, за да мога да имам скаларно ограничение, където коефициентите са променливи. След това имам само ограниченията за канализиране, ограничението на дървото и ограничението сума == 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, които биха принудили ребро да бъде истина.

Благодаря за помощта!


person excalibur1491    schedule 04.05.2015    source източник


Отговори (2)


„Напълно нов съм в Choco и CP“

В миналото бях хващан от инструменти, които или започваха, или не, започваха да броят от нула, и предположих обратния случай (броенето започва от едно). Поведението, което описвате, попада в тази категория грешки, така че можете да проверите дали всичко това започва с масиви, базирани на нула.

person Michael Blankenship    schedule 24.05.2015

Версията на Choco3, която използвах, имаше грешка. Беше решен в 3.3.0. Моля, използвайте го, ако имате същия проблем :)

person excalibur1491    schedule 26.07.2015