[gecode-users] Skipping branching alternatives?

[Mikael Zayenz Lagerkvist]

On 7/10/06, Luis Quesada <luque at info.ucl.ac.be> wrote:
> Guido Tack wrote:
>
> > [...]
> >
> >This is slightly against the general architecture of Gecode. One of the main
> >achievements in CP research was the clear separation of concerns between
> >propagation, branching, and search. Propagation does the inferences within
> >one space, branching determines the shape of the search tree, and search
> >explores the tree.
> >Cutting off branches is normally considered part of exploration. [...]
> >
> I don't agree with this bit Guido. Cutting off branching (i.e. pruning)
> is the very purpose of propagation. When you remove 5 from X's domain
> you are cutting off the branch associated with X=5.

While propagators do cut of branches through propagation, this is
based on local information in the current Space only. The difference
here is when we want to cut of branches based on some global property,
like symmetries in the search-tree. These properties are probably best
addressed by the exploration, since the exploration part is the only
part that has a global view.

Some of the common schemes for exploiting global properties do use
propagators in their implementation (for example, Branch-and-bound and
SBDS), since the global information can be localized. Posting these
propagators is controlled by the exploration. Others, like SBDD for
example, cuts off parts of the search tree without posting
propagators.

Cheers,
Mikael Zayenz Lagerkvist

-- 
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/