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

[Christian Schulte]

Oh, btw: if you want me to add your modification of the example to Gecode, I’ll do that, provided you:

-        Add yourself as contributing author.

-     Make it controllable from the commandline whether to use LDSB or not.

 

Cheers

Christian

 

 

--

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

 

From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf Of Christian Schulte
Sent: Wednesday, May 15, 2013 8:34 PM
To: 'Stefano Gualandi'; users at gecode.org
Subject: Re: [gecode-users] Symmetries, activity branching, and graph coloring

 

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/de73ff62/attachment.html>