[gecode-users] Immediate search failure

[Joe Porter]

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/20090428/71e8ffd0/attachment.htm>