Imagine you plan a trip with many stops and desired visits, but you also have time and budget constraints. Furthermore, imagine that you have a tool that tells you whether it is possible to satisfy all these constraints and requirements or whether no solution exists, meaning that a failure is obtained. In that case, you need to relax some of the constraints. But which ones? It is not sufficient that your constraint solver proves that the constraints have no solution, but it should also find the culprits for this failure.
An effective method for finding those culprits for arbitrary constraint satisfaction problems has long been an open problem. The publication of the article QuickXplain: Preferred Explanations and Relaxations for Over-Constrained Problems at AAAI 2004 addressed this problem and paved new ways for explanation generation. 20 years later, the AAAI paper about QuickXplain has got 585 citations according to Google scholar and even won the prestigious AAAI Classic Paper Award in 2020. It has influenced the research of many colleagues such as Barry O’Sullivan, Gerhard Friedrich, Alexander Felfernig, Dietmar Jannach, and even João Marques-Silva to name a few. Moreover, it is used as conflict detector in many software products, including a B2B configurator of a major CRM company, CPLEX, SAT4J (which is used in the eclipse dependency manager p2), and the missing rule generator of a rule management system.
QuickXplain thus is a rare example of a simple and effective method that had a significant impact in both academia and industry. But what did it take to discover this method, which amazed so many people? Has it been the result of a successful scientific research program? How much funding was necessary? And how much time did I work on this topic?
This article tells the story of the discovery of QuickXplain and gives answers to these questions even if they are not those that you may expect. Of course, this article is written from my personal perspective. It solely represents my opinion and not that of any other party. I try to adopt a somewhat entertaining and anonymizing style. Therefore, I won’t use any company names, but descriptions such as ‘the optimization company’. The article consists of the following five sections:
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.
