[gecode-users] Problem solving simple model
Jefferson Soares Biernastki
jef_ti at hotmail.com
Wed Sep 7 17:14:14 CEST 2011
Thanks a lot Guido/Christian,
wonderful tips, i already downloaded the MPG to improve my knowledge on Gecode and in a soon future replace ILOG.
Regards,
Jefferson Soares BiernastkiJSK Soluções em Tecnologia Ltda
Desenvolvimento - Novas Tecnologias
41 88426214
http://www.onlaboral.com.br
http://pixeljef.wordpress.com
Subject: Re: [gecode-users] Problem solving simple model
From: tack at gecode.org
Date: Wed, 7 Sep 2011 14:39:47 +0200
CC: users at gecode.org
To: jef_ti at hotmail.com
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 --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20110907/f16c8ab7/attachment.htm>
More information about the users
mailing list