[Potassco-users] Graph Coloring encoding in iClingo From: James Deng - 2012-12-25 14:15 Attachments: Message as HTML ```Hi all, According to the "finite model computation" paper, I wrote one incremental ASP (iclingo) program for graph coloring problem #cumulative k. { color(X, k) } :- node(X). :- color(X, C), color(X, k), node(X), C < k. :- edge(X, Y), color(X, k), color(Y, k). #volatile k. :- node(X), { color(X, D) : D <= k} 0. #base. #show color/2. I wonder if there is any more efficient iclingo encodings for the GC problem. Regards, -- James Deng Artificial Intelligence Research Group University of Western Sydney http://cnjdeng.appspot.com ```
 Re: [Potassco-users] Graph Coloring encoding in iClingo From: Martin Gebser - 2012-12-31 12:49 Attachments: color.lp ```Dear James, the attached encoding should be a bit more efficient. It aims at a gradual program extension when a new color is added. In particular, there are no volatile cardinality constraints. Regards and Happy New Year, Martin On 12/25/2012 03:14 PM, James Deng wrote: > Hi all, > > According to the "finite model computation" paper, I wrote one > incremental ASP (iclingo) program for graph coloring problem > > #cumulative k. > { color(X, k) } :- node(X). > :- color(X, C), color(X, k), node(X), C < k. > :- edge(X, Y), color(X, k), color(Y, k). > > #volatile k. > :- node(X), { color(X, D) : D <= k} 0. > > #base. > #show color/2. > > I wonder if there is any more efficient iclingo encodings for the GC > problem. > > > Regards, > -- > James Deng > > Artificial Intelligence Research Group > University of Western Sydney > > http://cnjdeng.appspot.com > > > ------------------------------------------------------------------------------ > LogMeIn Rescue: Anywhere, Anytime Remote support for IT. Free Trial > Remotely access PCs and mobile devices and provide instant support > Improve your efficiency, and focus on delivering more value-add services > Discover what IT Professionals Know. Rescue delivers > http://p.sf.net/sfu/logmein_12329d2d > > > > _______________________________________________ > Potassco-users mailing list > Potassco-users@... > https://lists.sourceforge.net/lists/listinfo/potassco-users > ```
 Re: [Potassco-users] Graph Coloring encoding in iClingo From: Roland Kaminski - 2012-12-31 13:44 Attachments: signature.asc ```On Monday, December 31, 2012 01:49:16 PM Martin Gebser wrote: > Dear James, > > the attached encoding should be a bit more efficient. It aims at a > gradual program extension when a new color is added. In particular, > there are no volatile cardinality constraints. > > Regards and Happy New Year, > Martin Also note that there are a lot of different ways to model the graph coloring problem. Furthermore, preprocessing steps might be useful. For example there are heuristics to determine large cliques. If a graph has a n-clique, then one needs at least n colors. Because this problem is quite well-studied, the internet should contain wealth of information. :) Regards, Roland ```
 Re: [Potassco-users] Graph Coloring encoding in iClingo From: Roland Kaminski - 2012-12-31 13:47 Attachments: signature.asc ```On Monday, December 31, 2012 02:44:45 PM Roland Kaminski wrote: > On Monday, December 31, 2012 01:49:16 PM Martin Gebser wrote: > > Dear James, > > > > the attached encoding should be a bit more efficient. It aims at a > > gradual program extension when a new color is added. In particular, > > there are no volatile cardinality constraints. > > > > Regards and Happy New Year, > > Martin > > Also note that there are a lot of different ways to model the graph coloring > problem. Furthermore, preprocessing steps might be useful. For example > there are heuristics to determine large cliques. If a graph has a n-clique, > then one needs at least n colors. Because this problem is quite > well-studied, the internet should contain wealth of information. :) Found these slides, which contain some possible encoding ideas and provide some pointers: http://www.maths.ed.ac.uk/~jmarecek/timetabling/warwick-slides.pdf ```
 Re: [Potassco-users] Graph Coloring encoding in iClingo From: James Deng - 2013-01-12 04:11 ```Dear Gebser and Roland, Sorry for this late reply. I really appreciate your provided information, it's very helpful! Your encoding is much faster than the naive version I proposed. Thanks very much! Actually I am busy implementing another incremental ASP solver based on clingo, which is different to iclingo's paradigm and requirements. Regards, James On 01/01/2013, at 12:47 AM, Roland Kaminski wrote: > On Monday, December 31, 2012 02:44:45 PM Roland Kaminski wrote: >> On Monday, December 31, 2012 01:49:16 PM Martin Gebser wrote: >>> Dear James, >>> >>> the attached encoding should be a bit more efficient. It aims at a >>> gradual program extension when a new color is added. In particular, >>> there are no volatile cardinality constraints. >>> >>> Regards and Happy New Year, >>> Martin >> >> Also note that there are a lot of different ways to model the graph coloring >> problem. Furthermore, preprocessing steps might be useful. For example >> there are heuristics to determine large cliques. If a graph has a n-clique, >> then one needs at least n colors. Because this problem is quite >> well-studied, the internet should contain wealth of information. :) > > Found these slides, which contain some possible encoding ideas and provide > some pointers: > > http://www.maths.ed.ac.uk/~jmarecek/timetabling/warwick-slides.pdf ```