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

[Vincent Barichard]

Hi,

I can give you an example of slow convergence :

#include <gecode/driver.hh>
#include <gecode/minimodel.hh>
#include <gecode/float.hh>

using namespace Gecode;

class SlowConvergenceTest : public Script {
protected:
  FloatVarArray x;
public:
  /// Actual model
  SlowConvergenceTest(const Options& opt)
    : Script(opt), x(*this,2,0,4) {
    FloatNum coeff = 0.999999;
    //FloatNum coeff = 1;

    // Post equations
    rel(*this, x[1] - x[0] == 0);
    rel(*this, x[1] + coeff * x[0] == 2);

    // Redondant constraint
    //rel(*this, 2 * x[1] + (coeff - 1) * x[0] == 2);
  }
  SlowConvergenceTest(bool share, SlowConvergenceTest& p)
    : Script(share,p) {
    x.update(*this,share,p.x);
  }
  virtual Space* copy(bool share) {
    return new SlowConvergenceTest(share,*this);
  }
  virtual void print(std::ostream& os) const {
    os << "x  = [" << x[0].min() << ";" << x[0].max() << "]" << std::endl
       << "y  = [" << x[1].min() << ";" << x[1].max() << "]" << std::endl
       << std::endl;
  }
};
int main(int argc, char* argv[]) {
  Options opt("SlowConvergenceTest");
  opt.parse(argc,argv);
  Script::run<SlowConvergenceTest,DFS,Options>(opt);
  return 0;
}

If you use this model, you will get a big number of propagations in order
to compute
the fix point (only 'status()' is called as there is no brancher). If you
uncomment the redondant constraint, you get the solution very quickly.
To identifiy a slow convergence, I count the number of calls of each
constraint in
the propagation step, then I try to tweek the model to overcome the
difficulty.
I hope it will help.

Cheers,
Vincent



2015-04-16 8:12 GMT+02:00 Kurt Van Den Branden <kurt.vandenbranden at agfa.com>
:

> 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*
> <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*
> <http://www.gecode.org/~schulte>
>
> Professor of Computer Science, KTH, *cschulte at kth.se* <cschulte at kth.se>
>
> Expert Researcher, SICS, *cschulte at sics.se* <cschulte at sics.se>
>
>
>
> *From:* *users-bounces at gecode.org* <users-bounces at gecode.org> [mailto:
> *users-bounces at gecode.org* <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* <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
>
>


-- 
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/7e9b3627/attachment.html>