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

[Christian Schulte]

Hi Stefano,

Cool. One question: did you try restarts? That should help. A lot! (the next
version of Gecode 4.2.0 will even have no-goods from restarts...)

Cheers
Christian

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


> -----Original Message-----
> From: Stefano Gualandi [mailto:stefano.gualandi at gmail.com]
> Sent: Friday, June 28, 2013 10:27 PM
> To: cschulte at kth.se
> Subject: Re: [gecode-users] Symmetries, activity branching, and graph
coloring
> 
> Finally, I have posted about Graph Coloring, Gecode and LDBS:
> 
> http://stegua.github.io/blog/2013/06/28/gecol/
> 
> cheers,
> Stefano
> 
> 
> 
> 
> On May 23, 2013, at 5:56 PM, Christian Schulte <cschulte at kth.se> wrote:
> 
> > Brilliant, thanks! Of course, you are contributing author, you even
helped me a
> lot in getting the bug fixed!
> >
> > Thanks
> > Christian
> >
> > --
> > Christian Schulte, Professor of Computer Science, KTH,
> > www.ict.kth.se/~cschulte/
> >
> >
> > From: Stefano Gualandi [mailto:stefano.gualandi at gmail.com]
> > Sent: Thursday, May 23, 2013 11:36 AM
> > To: Christian Schulte
> > Subject: Re: [gecode-users] Symmetries, activity branching, and graph
> > coloring
> >
> > Everything works as a charm now, thanks!
> > (I have tested my own script with 135 DIMACS graph coloring instances)
> >
> > > 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.
> >
> > The modified gecode graph coloring example is attached, with a command
> > line option for using LDSB, and restricting the color domains in {0,.,
> > g.n_v-1}  :-)
> >
> > Regarding adding myself as a contributing author, it is up to you, my
> contribution is so *microscopic*.
> > As you like.
> >
> > cheers,
> > Stefano
> >
> >
> >
> >
> > On May 15, 2013, at 8:38 PM, Christian Schulte <cschulte at kth.se> wrote:
> >
> > >
> > > 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
> >