From: James Deng <cnjamesdeng@gm...>  20121225 14:15:04
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 <cnJamesDeng@...> http://cnjdeng.appspot.com 
From: Martin Gebser <gebser@cs...>  20121231 12:49:35
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 > <mailto:cnJamesDeng@...> > http://cnjdeng.appspot.com <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 valueadd services > Discover what IT Professionals Know. Rescue delivers > http://p.sf.net/sfu/logmein_12329d2d > > > > _______________________________________________ > Potasscousers mailing list > Potasscousers@... > https://lists.sourceforge.net/lists/listinfo/potasscousers > 
From: Roland Kaminski <kaminski@cs...>  20121231 13:44: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 nclique, then one needs at least n colors. Because this problem is quite wellstudied, the internet should contain wealth of information. :) Regards, Roland 
From: Roland Kaminski <kaminski@cs...>  20121231 13:47:26
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 nclique, > then one needs at least n colors. Because this problem is quite > wellstudied, 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/warwickslides.pdf 
From: James Deng <cnjamesdeng@gm...>  20130112 04:11:46

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 nclique, >> then one needs at least n colors. Because this problem is quite >> wellstudied, 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/warwickslides.pdf 