[gecode-users] Newbie: space/solution copying & dynamically addedconstraints

[Christian Schulte]

Hi Peter,

looks interesting ;-) The basic insight that all search engines use is that
they do not manipulate the variables directly: instead they use the
branchings together with branching descriptions as a problem-independent
device to do so. A branching description contains space-independent
information about which variable and about how that variable is to be
constrained when used with a commit operation on a space: the commit
operation finds the appropriate branching and the branching then uses the
branching description to constraint the right variable accordingly.

What you could do to make the search distributed is to cook up an operation
for a branching description that turns it into something that can be send
over the wire: should not be to hard, the typical description contains just
two integers. Then in order to hand out a node, you just start from the same
basic space and add all branching descriptions corresponding to the path
leading to the node you want to explore (this is recomputation and looking
how recomputation is done in the search engines should give you an idea).

Much of the way search is done has been inherited from Mozart (apart from
batch recomputation). If you want to see an architecture for distributed
parallel search based on spaces, you might want to check:
	http://web.it.kth.se/~schulte/paper.html?id=Schulte:TRICS:2000
or, if you prefer the full story:
	http://web.it.kth.se/~schulte/paper.html?id=Schulte:LNAI:2002

As it comes to pause resume, check
	
http://www.gecode.org/gecode-doc-latest/group__TaskIntSearchStop.html

Cheers
Christian

--
Christian Schulte, http://www.imit.kth.se/~schulte/ 

-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Pieter Thysebaert
Sent: Tuesday, September 19, 2006 3:20 PM
To: users at gecode.org
Subject: [gecode-users] Newbie: space/solution copying & dynamically
addedconstraints


Hello,

I'm currently running Gecode 1.2.2 on debian Sarge and am using its built-in
BAB engine to solve a constraint optimization problem.

As I want to parallelize the search procedure (by using concurrent
distributed components) but haven't discovered such a solution in gecode
(does it exist already?), I have been entertaining myself by implementing a
prototype of such a concurrent distributed search procedure using MPICH2, in
which the concurrent components perform load distribution by dynamically
splitting up their assigned search space.

As it's just a prototype, I don't mind it being slightly naive. Therefore, I
use the Gecode-provided BAB search engine in each of the components. When
some component has finished its search, it will request work from a busy
component. Work consists of a description of variables to be bound, so the
querying component will start a new search in the problem space constrained
by these bound variables. These variable bindings can easily be passed on
using MPI messages.

My main problem, however, lies with controlling the BAB search engine
dynamically. Consider this (naive) approach:

BAB<solution> engine(...);
do {
   solution* currentSolution =  engine.next()

   currentSolution->getWorkToDistribute();
} while ...

The goal of the getWorkToDistribute call is to split the remaining search
space to be explored by engine.next() in two parts by a binary split on some
variable: one part will be assigned to a worker process asking for work (and
thus, the description of this part of the search space will be distributed
using MPI calls), and the  remainder will be explored by this process's
engine.next().

My problem lies with the latter.  Assuming that we have split the search
space on variable X, and that X=1 will be explored by the remote process, I
now want to "dynamically" constrain this process's search space by adding "X
<> 1".

Is there a way to achieve this without recreating the whole problem, adding
the extra constraint "X <> 1" and starting a new search engine (probably
revisiting lots of nodes)?

I'm asking because I'm really not sure how and when the search engine copies
solution objects.  It seems that naively  "adding" a constraint to the
currentSolution object does not have the effect I want.

Then I thought of the "constrain" function called by the BAB engine, used to
dynamically constrain the cost function. However, I'm not sure when it is
called, nor what the relationship is between the argument passed to this
function and previous values of currentSolution in the loop. That is, I
tried currentSolution->setSomeMemberData hoping that currentSolution would
be passed as argument to the constrain() function of another node, but upon
examination in the constrain() function the envisioned member data does not
have said member data. (My idea was to read this member data - representing
the constraint to be added "X <> 1"
- from the argument to constrain() : Space *s  - and add this constraint to
"this" just like reading the value of the cost function from Space s and
then adding a constraint requiring the cost to be less)

Can anyone enlighten me and tell me where my ideas are just plain wrong or
what I should try instead?

As an additional question: in the above code snippet, useful things (aside
from searching, that is) can only be performed when engine.next() returns.
Are there Pause/Resume objects or operators that will interrupt the search
procedure more timely but still allow the search engine to continue
afterwards?

Thanks
Pieter


_______________________________________________
Gecode users mailing list
users at gecode.org https://www.gecode.org/mailman/listinfo/gecode-users