[gecode-users] Immediate search failure
Christian Schulte
cschulte at kth.se
Wed Apr 29 00:33:42 CEST 2009
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: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Joe Porter
Sent: Tuesday, April 28, 2009 11:03 PM
To: users at gecode.org
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.ps.uni-sb.de/pipermail/users/attachments/20090429/70c94ee1/attachment.htm>
More information about the gecode-users
mailing list