Hi Joe,
There are two things you can do: 1) Try to remove some constraints and see whether this gives you a solution. Try to isolate the culprit. 2) Upgrade to 3.0 and read Modeling with Gecode: you are torturing yourself for example with linear constraints, the document says how it's done much easier (and hence, less bugs potentially)! Cheers Christian -- Christian Schulte, www.it.kth.se/~cschulte/ From: [email protected] [mailto:[email protected]] On Behalf Of Joe Porter Sent: Tuesday, April 28, 2009 11:03 PM To: [email protected] Subject: [gecode-users] Immediate search failure What are the possible reasons for an immediate search failure? I've changed something in my model, but I'm not sure what could be causing immediate failures (using Gecode 2.2.0). Setup code is below, and the output is at the bottom. This is solving a simple scheduling problem with a simple model instance that I can solve by hand. According to the debug statements, the model should be feasible. Or - maybe I've been looking at it for too long... Thanks, -Joe // CP Solver Engine CPEngine::CPEngine( InstanceKeeper * pIK, unsigned long long min, unsigned long long max ) : vars( this, pIK->NumVars(), (int) min, (int) max ), // instantiate constraint vars latencies( this, pIK->NumLatencies()+1, 0, (int) 2 * max ), lin_cstr(this, 1,0,1), /* not used in this model */ sat_cstr(this, 1, 0, (int) pIK->GetNumLinearRelations() ), /* not used in this model */ _pIK( pIK ) { // All equality constraints LinearRelation lrel; bool loop = pIK->GetNextEqualityPair( lrel, true ); while (loop) { IntVarArgs v(2); v[0] = vars[lrel.xvar]; v[1] = vars[lrel.yvar]; IntArgs a(2); a[0] = 1; // 'x' of x = y + o a[1] = -1; // 'y' of x = y + o linear( this, a, v, IRT_EQ, lrel.offset ); cout << "Posted equality relation (x,y) = (" << lrel.xvar << "," << lrel.yvar << ") w/ offset " << lrel.offset << std::endl; loop = pIK->GetNextEqualityPair( lrel ); } // All inequality constraints loop = pIK->GetNextInequalityPair( lrel, true ); while (loop) { IntVarArgs v(2); v[0] = vars[lrel.xvar]; v[1] = vars[lrel.yvar]; IntArgs a(2); a[0] = 1; // 'x' of x <= y + o a[1] = -1; // 'y' of x <= y + o linear( this, a, v, IRT_LQ, lrel.offset ); cout << "Posted inequality relation (x,y) = (" << lrel.xvar << "," << lrel.yvar << ") w/ offset " << lrel.offset << std::endl; loop = pIK->GetNextInequalityPair( lrel ); } // All duration constraints DurativeVariable dv; loop = pIK->GetNextDuration( dv, true ); while ( loop ) { IntVarArgs v(1); v[0] = vars[dv.xvar]; IntArgs a(1); a[0] = 1; linear( this, a, v, IRT_LQ, ((int)max) - dv.duration ); // don't run over the end cout << "Posted duration relation (x) = (" << dv.xvar << ") w/ length " << dv.duration << std::endl; loop = pIK->GetNextDuration( dv ); } // All serialization constraints int ser_count = 0; std::vector< DurativeVariable > vdv; loop = pIK->GetNextSerialization( vdv, true ); while (loop) // && false) { IntVarArgs v( (int) vdv.size() ); IntVarArgs e( (int) vdv.size() ); IntArgs d( (int) vdv.size() ); cout << "Serializing (x,d): "; for (unsigned int idx = 0; idx < vdv.size(); idx++ ) { v[idx] = vars[vdv[idx].xvar]; d[idx] = (int) vdv[idx].duration; e[idx].init(this,min,max); cout << "(" << vdv[idx].xvar << "," << vdv[idx].duration << "), "; } cout << endl; IntArgs height(v.size()), m(v.size()); for ( int idx = v.size(); idx--; ) { height[idx] = 1; m[idx] = 0 /*ser_count*/; } cumulatives(this, m, v, d, e, height, 1, true ); loop = pIK->GetNextSerialization( vdv ); ser_count++; } // Instantiate latency variables here std::vector< LatencyBound > vlb; loop = pIK->GetNextLatencyBound( vlb, true ); while ( loop ) { std::vector< LatencyBound >::iterator pLB = vlb.begin(); // First set up the range for the latency variables rel( this, latencies[pLB->latvar], IRT_GQ, 1 ); rel( this, latencies[pLB->latvar], IRT_LQ, pLB->maxdist ); cout << "Latency (l) = (" << pLB->latvar << ") alternatives: "; // Then define the relationship between the instances // and the latencies int k = 0; BoolVarArgs bs(vlb.size()); for ( pLB = vlb.begin(); pLB != vlb.end(); pLB++ ) { BoolVar b(this,0,1); IntVarArgs v(2); v[0] = vars[pLB->rcvrvar]; v[1] = vars[pLB->sendervar]; IntArgs a(2); a[0] = 1; // 'x' of x = y + o a[1] = -1; // 'y' of x = y + o cout << "(s,r) = (" << pLB->sendervar << "," << pLB->rcvrvar << ") "; linear( this, a, v, IRT_EQ, latencies[pLB->latvar], b ); bs[k++] = b; } cout << endl; linear( this, bs, IRT_GR, 0 ); // Force at least one of the constraints in this collection to be true loop = pIK->GetNextLatencyBound( vlb ); } // Dummy latency in case there are no latencies in the spec! // We have to branch on something! rel( this, latencies[pIK->NumLatencies()], IRT_GQ, 1 ); rel( this, latencies[pIK->NumLatencies()], IRT_LQ, 1 ); cout << "Dummy latency (==1)" << endl; // Do branching branch(this, vars, INT_VAR_REGRET_MAX_MAX, INT_VAL_MED); branch(this, latencies, INT_VAR_SIZE_MIN, INT_VAL_MAX ); // start with max latency and work down } Domain size: 100000 Posted equality relation (x,y) = (0,1) w/ offset -20000 Posted equality relation (x,y) = (1,2) w/ offset -20000 Posted equality relation (x,y) = (2,3) w/ offset -20000 Posted equality relation (x,y) = (3,4) w/ offset -20000 Posted duration relation (x) = (4) w/ length 19 (0,max-19) Posted duration relation (x) = (5) w/ length 57 (0, max-57) Serializing (x,d): (0,19), (1,19), (2,19), (3,19), (4,19), Dummy latency (==1) Stats: Search Stats Initial propagators: 4294967295 branchings: 4294967295 Summary propagations: 0 failures: 1 clones: 0 commits: 0 peak memory: 5 KB
_______________________________________________ Gecode users mailing list [email protected] https://www.gecode.org/mailman/listinfo/gecode-users
