[gecode-users] Symmetries, activity branching, and graph coloring

[Christian Schulte]

Hi Stefano,

 

Yes, that should be symmetric. The bug was a missing initialization and is now fixed in the trunk.

 

I also attached a patch

 

Thanks a lot!

Christian

 

--

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

 

From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf Of Stefano Gualandi
Sent: Wednesday, May 15, 2013 6:04 PM
To: users at gecode.org
Subject: [gecode-users] Symmetries, activity branching, and graph coloring

 

Hi,
the new Lightweight Dynamic Symmetry Breaking could be used also for the graph coloring
example, since the color values are symmetric, right?

Something like (referring to gecode/example/graph-color.cpp)

    Symmetries syms;
    syms << ValueSymmetry(IntArgs::create(g.n_v,0));
    […]
    branch(*this, v, INT_VAR_SIZE_MIN(), INT_VAL_MIN(), syms);

If the answer is "no", forget about the remaining of this email  :-)



If the answer is "yes", then there is something wrong when using symmetry breaking together
with an activity based branching as:

        branch(*this, v, INT_VAR_ACTIVITY_SIZE_MAX(opt.decay()), INT_VAL_MIN(), sums);

Since the example gives "seg fault". I have tried all the variable selection strategies,
but only those based on the "activity" have this issue.

You can find attached a modified graph-color.cpp example that exposes the problem
(with an additional option for the activity-based branching):

./examples/graph-color -branching sizeact

Thanks in advance,
cheers,
Stefano

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20130515/340f3435/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: actldsb.patch
Type: application/octet-stream
Size: 1828 bytes
Desc: not available
URL: <http://www.gecode.org/pipermail/users/attachments/20130515/340f3435/attachment-0001.obj>