You are here

CP Invited Speakers

Constraint-based Problems and Solutions in the Global Enterprise

Claire Bagley, Oracle, USA


Industrial Success Stories of ASP and CP:  What's still open? (joint with ICLP2015)

Gerhard Friedrich, Institute of Applied Informatics, Universität Klagenfurt, Austria

More than 25 years ago together with Siemens we started to investigate the possibility of substituting the classical rule-based configuration approach by model-based techniques. It turned out that in those days only  constrained programming (CP) had any real chance of meeting the application demands. By exploiting CP we were able to significantly improve the productivity of highly trained employees  (by more than 300%) and to substantially reduce software development and maintenance costs (by more than 80%). Consequently, CP has been  our method of choice for problem solving in industrial projects since 1989. 

Some years ago, we started to investigate answer set programming (ASP) techniques, mainly because of the possibility to apply a very expressive logical first-order language for specifying problems. It emerged that, by using simply problem encoding, we were able to solve difficult real world problem instances witnessing the enormous improvements of logic programming over the last decades.

Although ASP and CP have proven their practical applicability, we will point out challenges of large problems of the electronic and the semiconductor industry. In particular, we will stress the power of problem-specific heuristics which turned out to be the key in many applications of problem solvers.

Looking at the famous equation "algorithm = logic + control" most of the current work in the AI community assumes that control should be problem-independent and only the logical specification depends on the problem to be solved, i.e. "algorithm = logic(problem) + control". It is not surprising that for the current problem solving technology this is a practical approach up to a certain size of the problem instances, since we deal with NP-hard problems in many cases. However, it is observed (and examples are given) that problem-specific heuristics allow enormous run-time improvements. This success is based on problem-specific control, i.e. "algorithm = logic(problem) + control(problem)". Unfortunately, the design of such problem-specific heuristics is very time-consuming and redesigns are frequently required because of recurrent changes of the problem. Interestingly, humans are very successful at developing such problem-specific heuristics. Therefore, we argue that the automation of generating problem-specific heuristics with satisfying quality is still an important basic AI research goal with high practical impact that should be achievable.

This invited talk is sponsored by the European Coordinating Committee for Artificial Intelligence (ECCAI).



Synthesis of Constraint Solvers

Douglas Smith, Kestrel Institute, USA