[gecode-users] Memory problem using Gecode for local search

[Guido Tack]

On 6 Nov 2011, at 17:46, TeXitoi wrote:

> Guido Tack <tack at gecode.org> writes:
> 
>> Hi,
>> have you verified (e.g. using Gist) that your search tree actually
>> has that shape?
> 
> I cannot make gecode with gist compile here (OpenBSD).  But writing a
> minimal example, I think I understood why the tree do not have the
> shape I was thinking.
> 
> So, the question is: How can I branch to values different from sol_l
> (sol_l can be any solution, of course)? Ideally, a random value not
> the one of sol_l[i].

Ah, that makes sense.  With the second branch enabled (and using 10000 as the size), memory increases only very little over time.

You'll have to implement a brancher, see the relevant sections in the documentation. The brancher will have to store the sol_I array and use it to determine the value to branch on.

Cheers,
Guido

> 
> Here is the example:
> 
> ====8<========8<========8<========8<========8<========8<========8<====
> #include <gecode/int.hh>
> #include <gecode/search.hh>
> 
> using namespace Gecode;
> 
> class MySpace: public Space
> {
> public:
>    MySpace(int size_p, int nb_p):
>        machine_m(*this, size_p, 0, nb_p - 1)
>    {
>        IntArgs sol_l(machine_m.size());
>        for (int i_l = 0; i_l < machine_m.size(); ++i_l)
>            sol_l[i_l] = 0;
>        count(*this, machine_m, sol_l, IRT_EQ, machine_m.size() - 1);
>        // if using that, we will affect first according to sol_l, so
>        // we will need to go deep to find a solution
>        branch(*this, machine_m, INT_VAR_NONE, INT_VAL_MIN);
>        // using that, we will directly choose a value different from
>        // sol_l, and so we will have a right balanced tree
>        //branch(*this, machine_m, INT_VAR_NONE, INT_VAL_MAX);
>    }
> 
>    MySpace(bool share_p, MySpace &that): Space(share_p, that)
>    { machine_m.update(*this, share_p, that.machine_m); }
> 
>    virtual Gecode::Space *copy(bool share_p)
>    { return new MySpace(share_p, *this); }
> 
>    void print()
>    { std::cout << machine_m << std::endl; }
> 
> protected:
>    Gecode::IntVarArray machine_m;
> };
> 
> int main(void)
> {
>    MySpace *pSpace_l = new MySpace(10, 2);
>    Search::Options options_l;
>    options_l.c_d = 1;
>    options_l.clone = false;
>    DFS<MySpace> search_l(pSpace_l, options_l);
>    MySpace *pSol_l = 0;
>    while ((pSol_l = search_l.next()) != 0) {
>        pSol_l->print();
>        delete pSol_l;
>    }
> 
>    return 0;
> }
> ====8<========8<========8<========8<========8<========8<========8<====
> 
> -- 
> Guillaume Pinot                               http://www.texitoi.eu
> 
> « Il semble que la perfection soit atteinte non quand il n'y a plus
> rien à ajouter, mais quand il n'y a plus rien à retrancher. »
>                      -- Antoine de Saint-Exupéry, Terre des hommes
> 
> ()  ASCII ribbon campaign      -- Against HTML e-mail
> /\  http://www.asciiribbon.org -- Against proprietary attachments
> 
> 
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users