[gecode-users] Limiting the number of solutions of a search's subtree

[Christian Schulte]

Yes, you can share information: if you find a solution sol in your loop, you
can by

                this->constrain(*sol);

constrain the current space (which will be used for the outer search engine)
to yield a better solution than sol.

 

Cheers

Christian

 

--

Christian Schulte, Professor of Computer Science, KTH,
www.ict.kth.se/~cschulte/

 

From: Andrea Peano [mailto:andrea.peano at unife.it] 
Sent: Thursday, November 28, 2013 12:32 PM
To: Christian Schulte
Cc: users at gecode.org
Subject: Re: [gecode-users] Limiting the number of solutions of a search's
subtree

 

Hello,

thank you for your suggestion.

 

Taking a cue from this discussion:

http://www.gecode.org/pipermail/users/2013-January/003765.html

 

I've implemented this system:

once installed branchers for variables x and y, I install a brancher that
takes in input a function (nested_search()). This function installs the
brancher for variable z, instantiates a new search engine, calls the next()
method, then kills the brancher on z.

Here the code:

void MyModel::nested_search()

{

     IntVarArgs z;

 

     z << get_z();

     BrancherHandle b = branch(*this, z, INT_VAR_SIZE_MIN(), INT_VAL_MIN(),
NULL, &printZ);

 

     DFS<MyModel> dfs_first_sol(this);

     if( MyModel *sol = dfs_first_sol.next() ) {

          sol->print(cout);

          delete sol;

     }

 

     b.kill(*this);

     done();

 

}

 

This works pretty well, unless the fact that Gist "can't see" the nested
search tree, and I can't use inspectors for the nested solution. Moreover
the current solution space is the calling one, so it's a bit hard to use for
example a B&B search over the entire search tree. In fact, I've a search
engine for each leaf of the upper search tree, and they can't share
information, as it is.

Am I right?

 

Should I design a new search engine in order to achieve a more flexible
behaviour?

 

Best regards,

Andrea

 

On Wed, Nov 20, 2013 at 8:22 PM, Christian Schulte <cschulte at kth.se> wrote:

There has been a similar discussion along these lines (for only two
branchers) on this mailing list (using more than one search engine to get
the desired behavior). Please try to find it in the mailing list archives.

 

Christian

 

--

Christian Schulte, www.ict.kth.se/~cschulte/

 

From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Andrea Peano
Sent: Wednesday, November 20, 2013 8:08 PM
To: users at gecode.org
Subject: [gecode-users] Limiting the number of solutions of a search's
subtree

 

Hello all,

I've installed 4 branchers in order to solve my model.

Although I need to compute the entire search tree of the first three
branchers, It would be very effective to limit the number of solutions of
the remaining subtrees.

 

In other words, given a leaf of the search three produced by the first three
branchers, I would compute only the first solution of the last one.

 

I read section 8.1 of the guide, named "Executing code between branchers",
and this behaviour seems to be achievable by posting some contraints,
somehow...

Is it the right way?

 

Do you have any suggestion?

 

Thank you,

Andrea





 

-- 

 

Andrea Peano - PhD student

Department of Engineering - University of Ferrara

Tel: +39 0532 97 4827

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20131128/6f831d5b/attachment-0001.html>