[gecode-users] model with float variables sometimes hangs during search

[Kurt Van Den Branden]

I did notice an enormous amount of propagations.
is there some way I can detect slow convergency?
or is there something I can do about it?

I'll try to make the model simpler.
see if I can reproduce the problem with a limited model.

thanks,

Kurt Van Den Branden | Agfa Graphics




From:   Vincent Barichard <Vincent.Barichard at univ-angers.fr>
To:     "cschulte at kth.se" <cschulte at kth.se>
Cc:     Kurt Van Den Branden/AMAUK/AGFA at AGFA, Gecode <users at gecode.org>
Date:   15/04/2015 17:05
Subject:        Re: [gecode-users] model with float variables sometimes 
hangs during search
Sent by:        vincent.barichard at gmail.com



Hi,

My first thought is that it is a slow convergency process. It often occurs 
when linear constraints are involved with particular coefficients. A first 
clue may be the number of propagations done in one call to 
Space::status(). For the cases where the search ends (with a big amount of 
time) you may check the number of propagations done. If it is abnormally 
huge, it's probably a slow convergence. Without digging in the model and 
trace the search, I can't say much more. Sorry ....

Regards,
Vincent

2015-04-15 16:05 GMT+02:00 Christian Schulte <cschulte at kth.se>:
Hi,
 
This could be a feature and not a bug in that constraint propagation is 
just very slow to converge. For floating point numbers there is this risk.
 
I would not know what to suggest without knowing how the model looks like 
but I am also not an expert in floating point. Vincent: do you have an 
idea?
 
Cheers
Christian
 
--
Christian Schulte, www.gecode.org/~schulte
Professor of Computer Science, KTH, cschulte at kth.se
Expert Researcher, SICS, cschulte at sics.se
 
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf 
Of Kurt Van Den Branden
Sent: Wednesday, April 15, 2015 4:00 PM
To: users at gecode.org
Subject: [gecode-users] model with float variables sometimes hangs during 
search
 
hi, 

I have a Gecode model that uses float variables. 
I use a BAB searchengine with a Search::TimeStop object to interrupt the 
search when it takes too long. 

I noticed that when the model is created with certain parameters, the 
search isn't interrupted at the requested timelimit. 
it either continues a lot longer than allowed, or it doesn't stop at all. 

in these cases, the debugger shows that it's the method Space::status that 
doesn't return sometimes. 
it keeps on propagating and never stops. 

I haven't been able to reproduce this with a limited test model yet. 

Does anybody have tips on what could cause this problem? 

Kind Regards,

Kurt Van Den Branden | Agfa Graphics



-- 
Vincent Barichard         Université d'Angers (LERIA)
Tel:  02 41 73 52 06      Département Informatique
Fax: 02 41 73 50 73      H203
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20150416/ec1cba46/attachment-0001.html>