Now as I have discovered the basic decomposition scheme for computing explanations of failure, the question was how to proceed in turn. If this work were part of a scientific inquiry, I would have first worked on a paper. And if I were in a research department, I would just provide a prototypical implementation, which might then be turned into a product feature by a team of software engineers. But reality was different. The product feature was needed first and was the only thing that truly mattered for ‘the optimization company’. And as you might imagine there was not a whole team, but just the person who discovered the method. If all design and development happens in one mind, it should not be surprising that this leaves no traces whatsoever in any software development project management tool.
Once the discovery had been made, I quickly provided a complicated and unpublished implementation of the conflict detector in Winter 1999. A small hint: the detection is done within a single tree search that adds different constraints in different branches. I provided different strategies and gave them names such as detect-and-backtrack or detect-and-divide. No, the name QuickXplain wasn’t there yet and does not at all appear in this code. Despite this fact, we can say that the first implementation of QuickXplain has been shipped in Summer 2000 as part of a configuration engine. It was thus generally available in code form 24 years ago. Mission completed!
Not really! I could not make a major discovery without telling the world about it. In Winter 2000, I “stole” two weeks to write up the idea. In the CP RnD team, taking time for writing papers was not necessarily easy, even though publications have been appreciated. This paper took me quite some time since I faced a major difficulty. My code was too complicated to be explained easily. Furthermore, you don’t necessarily want to give all secrets away. Therefore, I tried to find a simplification of the complicated code that was easier to explain. I decided to use iterative algorithms that add or retract constraints in each iteration. And I needed a better name than detect-and-divide. The name QuickXplain instantly popped up in my mind. It really sounded good!
Please note that the resulting paper was a first attempt to explain an implemented method. It was not driven by a theoretical inquiry. It lacked a clear problem formulation and its scope was limited to find constraints that cause the failure of constraint propagation. Nevertheless, this first paper describes the basic decomposition idea.
The paper has been rejected at IJCAI 2001, but I could present it at the workshop on Modeling and Solving Problems with Constraints of this conference. The audience has been amazed. I gave them what they had been looking for!
In spite of this excitement at the IJCAI constraints workshop, I did not pursue this work further immediately after this conference. The paper has not been completely in line with my personal research on preference handling, which I presented at the configuration workshop of the same conference. As my time for personal inquiries had been quite limited, I put the topic of explanation detection aside again. ►
This web site expresses personal reflections about scientific topics with the purpose of contributing to discussions in scientific communities. As such, this content is not related to any organization, association, or employment.
