Compilation of Email Discussion on the topic of Interchangeability in CSPs CSCE976 Spring'2002 ============================= Date: Thu, 11 Apr 2002 12:25:40 -0500 From: Tibor Moldovan To: "Berthe Y. Choueiry" cc: amydavis@cse.unl.edu Subject: amy's evaluation and pointers [...] i can see the importance of her work since finding dynamic symmetries doesn't seem to be a well explored area, and furthermore hardware advancements have changed the playing field since they years when dynamic symmetry computation was declared too costly. some notes: slide 4 states that domain is the node label, but it seems that the nodes are labeled V1, V2 etc. i don't think it's very intuitive. questions: Interchangeability seems to lend itself very well to distributed/parallel computation, since there doesn't seem to be much data dependence once the sets are made. i think such computation would allow us to solve problems with huge depth and branching factor on machines such as prarie fire. DNPI seems to perform farly well compared to FC regarding # of nodes visited,and Const. checks performed. do we have any studies as to how it compares to FC-CBJ which blows FC out of the water on both accounts? slide 30 mentions "relationship to backbone and SAT" what is the "backbone"? nice job and good luck tibor ============================= Date: Thu, 11 Apr 2002 13:33:56 -0500 From: Amy Davis To: Tibor Moldovan cc: "Berthe Y. Choueiry" , amydavis@cse.unl.edu Subject: Re: amy's evaluation and pointers Thanks for the comments Tibor. With regard to your question on FC-DBJ. Indeed, it has beaten FC on all counts, as you state. Our method iscompletely independent of CBJ, and so, and thus would (I expect) similarly improve the performance of FC-DBJ. To be sure, it would have to be implemented, and tests made. Fc-DBJ is more costly in terms of space than FC, but I don't think that would be an issue until problems got quite large. Thanks, Amy O __ || / \_ CH2 -O- C - CH2 - CH2 - CH3 \ __ / Stop and smell the Roses! ============================= Date: Thu, 11 Apr 2002 14:05:27 -0500 (CDT) From: "Berthe Y. Choueiry" To: cse976-ml@cse.unl.edu Subject: Re: amy's evaluation and pointers Tibor raised some good questions that I would like to take into the discuss. Tibor> DNPI seems to perform farly well compared to FC regarding # of Tibor> nodes visited,and Const. checks performed. do we have any studies as Tibor> to how it compares to FC-CBJ which blows FC out of the water on both Tibor> accounts? Amy> With regard to your question on FC-DBJ. Indeed, it has beaten FC Amy> on all counts, as you state. Our method iscompletely independent Amy> of CBJ, and so, and thus would (I expect) similarly improve the Amy> performance of FC-DBJ. To be sure, it would have to be Amy> implemented, and tests made. Fc-DBJ is more costly in terms of space Amy> than FC, but I don't think that would be an issue until problems got Amy> quite large. In addition to what Amy just wrote, I know of no works testing FC-CBJ with *dynamic* orderings (this of course does not preclude their existence!). My *intuition* is that the advantages of intelligent backtracking are reduced in dynamic orderings *especially* promise, which tends to cluster conflicts "together." Tibor> slide 30 mentions "relationship to backbone and SAT" what is the Tibor> "backbone"? The backbone is another interesting phenomenon described in: @article{Kirkpatrick:85, AUTHOR = {Scott Kirpatrick and G. Toulouse}, TITLE = {{Configuration Space Analysis of Traveling Salesman Problems}}, YEAR = 1985, JOURNAL = {Journal de Physique}, VOLUME = {46}, PAGES = {1277-1292}, KEYWORDS = {}} and brought up back recently in the context of SAT: @article{Monasson:99, AUTHOR = {R{\'e}mi Monasson and Riccardo Zecchine and Scott Kirpatrick and Bart Selman and Lidror Troyansky}, TITLE = {{Determining Computational Complexity from Characteristic `Phase Transitions'}}, YEAR = 1999, JOURNAL = {Nature}, VOLUME = {400~(8)}, PAGES = {133-137}, KEYWORDS = {}} A backbon is the subset of variables that have the same values in *all* solutions to the problem. The idea is that to generalize the backbone from one value per variable to a bundle of values per variable, thus providing a stronger characterization. Tibor> Interchangeability seems to lend itself very well to Tibor> distributed/parallel computation, since there doesn't seem to be Tibor> much data dependence once the sets are made. i think such Tibor> computation would allow us to solve problems with huge depth and Tibor> branching factor on machines such as prarie fire. Parallelizing large search is a relatively old topic in AI. The novelty with interchangeability is to find some `good' conjunctive decomposition of the CSP. I have identified [1998] some good conditions for decomposition and Amy is aware of them, however I don't see how the current work impacts this. Xu Lin is working on something in this direction. Thanks for the feedback!! -Berthe Y. Choueiry choueiry@cse.unl.edu ============================= Date: Fri, 12 Apr 2002 09:05:01 -0500 From: Amy Davis To: Shabbir Ali Syed , cse976-ml@cse.unl.edu Subject: Comments to Rob In class Rob asked how a method called CPR compared to our DNPI method. I answered that in general CPR took less CPU time because it uses a more efficient data structure. I failed to mention: 1) CPR visits more nodes than DNPI by O(na^2). 2) CPR is not designed to work with dynamic variable ordering like DLD and LD-MB. As far as I can tell (or code), it only works with static variable ordering, because it relies on an ordered stack of partial solutions, which it incrementally pops, expands and pushes (see the paper for an explanation). When the top of the stack reaches a solution, it stops. (It can find one solution by continuing and exhausting the stack). In any case, DLD and LD-MB don't work with CPR, and DNPI-DLD performs better (faster too) in general than CPR-SLD. Does that make sense? Amy O __ || / \_ CH2 -O- C - CH2 - CH2 - CH3 \ __ / Stop and smell the Roses! ============================= Date: Fri, 12 Apr 2002 11:16:16 -0500 (CDT) From: "Berthe Y. Choueiry" To: cse976-ml@cse.unl.edu Subject: Re: Comments to Rob > 2) CPR is not designed to work with dynamic variable ordering like > DLD and LD-MB. Although CPR is not designed to work with dynamic orderings, I think: - we can CONCEPTUALLY extend it to work with dynamic variable ordering (e.g., DLD) - but it *cannot* be extended to work with dynamic variable-value ordering (e.g., LD-MB). Do you agree, Amy?? We may need to discuss this point. Anyway, this is a very important point. Carefuly to: - say it when your are presenting the 3d summary of the techniques - write it in your thesis. Thanks! -Berthe Y. Choueiry choueiry@cse.unl.edu ============================= To: "Berthe Y. Choueiry" cc: cse976-ml@cse.unl.edu Subject: Re: Comments to Rob To tell you the truth, I have no idea about how CPR extends. I can't immediately think of any reason that CPR couldn't theoretically work with both DLD and LD-MB. However, I don't think it's worth thinking about because my brain is far too overwhelmed as it is. Therefore, I vote to drop it topic. Amy O __ || / \_ CH2 -O- C - CH2 - CH2 - CH3 \ __ / Stop and smell the Roses! ============================= Date: Fri, 12 Apr 2002 11:25:15 -0500 (CDT) From: "Berthe Y. Choueiry" To: cse976-ml@cse.unl.edu Subject: Re: Amy's presentation Cory> First, on slide 21, why are there so many bounces in the graphs? Is Cory> it because of phase transition every time? good point. although some people have been seeing 2 or more phase transitions in some problems (too much is too much in my opinion), Amy's repeated phase transitions are related to 1 phase transition in a sequence of problem sets. Each problem set is generated with one particular level of embedded interchangeability. The sequence of problems is in an decreasing level of embedded interchangeability (or, if you wish, increasing embedded level of fragmenatataion). That is the last problem (right most) is built such that no interchangeanbility is present a priori, thus demonstrating the advantage of dynamic interchangeability. Cory> Lastly, a little confusion: are bundles good or bad? Towards the Cory> beginning it seemed to sound like they are good, but further on they Cory> sound bad. So I am confused about that... Bundles are good: they are multiple solutions representated as one solution. so they are very compact. Fruthermore, they represent "*robust* solutions" [Parkes & Ginsberg]: you are not happy with the solution you are using? here is another one that is almost equivalent! [Amy, you may want to add a slide with the advantages of bundling: compactcness and robustness] Cory, why did you get the impression bundles are not good? please explain as it is important... Thanks, -Berthe Y. Choueiry choueiry@cse.unl.edu ============================= Date: Fri, 12 Apr 2002 11:42:33 -0500 From: Amy Davis To: "Berthe Y. Choueiry" cc: cse976-ml@cse.unl.edu Subject: Re: Comments to Rob To tell you the truth, I have no idea about how CPR extends. I can't immediately think of any reason that CPR couldn't theoretically work with both DLD and LD-MB. However, I don't think it's worth thinking about because my brain is far too overwhelmed as it is. Therefore, I vote to drop it topic. Amy O __ || / \_ CH2 -O- C - CH2 - CH2 - CH3 \ __ / Stop and smell the Roses! ============================= Date: Fri, 12 Apr 2002 17:59:33 -0500 (CDT) From: "Berthe Y. Choueiry" To: cse976-ml@cse.unl.edu Subject: Re: Comments to Rob I think Amy is right: theoretically CPR should be expandable to any dynamic ordering. However, I can easily imagine that the implementation can be quite tricky... (nightmarish?) Thanks for a great discussion! -Berthe Y. Choueiry choueiry@cse.unl.edu =============================