Sono totalmente nuovo a Choco e CP, ma sto facendo un piccolo modello per risolvere il problema dell'albero di Steiner, e Choco continua a forzare il primo nodo ad essere vero qualunque sia il grafico è (e non è corretto, ho controllato).Choco impone una variabile a true quando non dovrebbe
Ho un array es di IntVar che == 1 se il bordo è nella soluzione o == 0 altrimenti. Lo stesso vale per l'array vs che imposta i vertici. Io uso l'array activeEdgeW per poter avere un vincolo scalare in cui i coefficienti sono variabili. Quindi ho solo i vincoli di canalizzazione, il vincolo dell'albero e il vincolo sum == w. E minimizzare w. Abbastanza semplice, ma per qualche motivo vs[0] == true sempre, per qualsiasi grafico.
Il mio modello è onestamente abbastanza semplice, io davvero non so dove che viene da:
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);
Questo è il mio modello, il resto del programma è solo i dati del grafico.
Qualcuno ha qualche idea di dove questo sta arrivando? Ho provato a mettere i nodi in diversi ordini in UB, ma sempre il primo nodo insiste nell'essere in. Ho provato a rimuovere il vincolo di canalizzazione, e mi ha mostrato che il nodo non è sempre vero, ma un margine che lo raggiunge deve essere, così diventa vero. Tuttavia, come si può facilmente vedere, non ho vincoli sull'array es che imporrebbe un vantaggio ad essere vero.
Grazie per l'aiuto!