[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