[gecode-users] Problem solving simple model

[Guido Tack]

On 6 Sep 2011, at 15:57, Jefferson Soares Biernastki wrote:

> Hi people,
> 
> i m working on Gecode for 2 weeks and i model a simple constraint problem already resolved in ILOG CP.
> 
> Problem: Two trains (X01 and X02) must arrive in final station, each ocupation must be released, normally 1 minute for releasing.
> 
> the model bellow tries to represent this problem.
> 
> somebody could help me on what i m doing wrong?

The reason your code can't solve the problem is the search strategy.  ILOG CP uses advanced automatic search heuristics that work well for scheduling problems. The INT_VAR_SIZE_MIN search in your Gecode model simply makes bad decisions early on and can't recover from them (see the huge tree when you run with -mode gist).
For your problem, a simple dynamic heuristic (INT_VAR_SIZE_AFC_MIN) together with a restart based search seems to work - at least it does find a solution and can prove optimality, although I'd expect a more specific search strategy to perform better.  I attached a modified version of your model, it does the restart search when you invoke it with -search restart.

There are a number of small things you can improve in your model, too:
 * use unary instead of nooverlap (see attached file)
 * do not initialize the IntVarArrays during cloning (just call update, see attached file)
 * not store the instance data in the Scheduling class (to avoid copying it during search, where it is not needed)

Cheers,
Guido

-- 
Guido Tack, http://people.cs.kuleuven.be/~guido.tack/

-------------- next part --------------
A non-text attachment was scrubbed...
Name: TrainSchedule.cpp
Type: application/octet-stream
Size: 14096 bytes
Desc: not available
URL: <http://www.gecode.org/pipermail/users/attachments/20110907/d50f82b1/attachment.obj>
-------------- next part --------------