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

[Pieter Thysebaert]

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