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

[TeXitoi]

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].

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