In this section, the ACP collects success stories of using constraint based technology. We aim to make these stories appeal to a wide audience, so they are written for a general audience.
This section was started in September 2015. We will update it regularly, so make sure to come back regularly!
If you want to share your story (or know someone who has a story to share), please contact us by email at stories@a4cp.org.
On June 13th 2015, the robot-lab Philae woke up on the comet 67P/Churyumov-Gerasimenko to resume a series of experiments interrupted seven months ago. These experiments were scheduled using Constraint Programming, and researchers of the team ROC developed propagation algorithms to help the Scientific Operations and Navigation Centre (SONC) to efficiently achieve this task. The Rosetta/Philae mission was launched in 2004 and it took more than ten years for the spacecraft, Rosetta, to reach its destination after a 6 billion kilometres long trip. On November 12th 2014, the lander module, Philae, was released and landed on the ground of the comet. Philae is fitted with ten instruments (see Figure 1) to conduct the experiments elaborated by as many research teams across Europe. These experiments, should they be imaging (CIVA, ROLIS), sampling (SD2, COSAC, PTOLEMY) or other types of signal analysis, correspond to sequences of activities constrained by two extremely scarce resources: ...
Do you want to improve the quality of your code? Unison is a code generator for compilers with a radically new approach. Unison rethinks code generation using combinatorial optimization techniques. Unison is available on Github and is integrated with the regular LLVM toolchain. A compiler is a program that transforms a source code from a high-level programming language into a lower level language (e.g., assembly language) to create an executable program. Compilers decompose code generation into multiple tasks (instruction selection, instruction scheduling, and register allocation) and solve each task in isolation with heuristics. Unison pursues a radically different route: it embraces and exploits the combinatorial, interdependent nature of code generation to drastically improve code quality. In Unison, the inter dependent code generation tasks are translated into a single combinatorial model that accurately reflects all inter dependencies. Solving the model with constraint programming, a modern combinatorial optimization technology, results in the desired high-quality assembly code. ...
Designing a stable and self-assembling protein requires to organize thousands of atoms in a favorable configuration in space. Researchers at INRA, Toulouse (France) worked in collaboration with biochemists in Belgium and Japan and used constraint programming technology, embodied in the toulbar2 solver, to optimize the intermolecular forces (captured by the Talaris14 force-field) of the full-atom representation of the targeted protein shape. Toulbar2 was able to identify a most stable molecular organization and to prove that no better organization exists. ...
You need to buy a new car and want to try out configurations to know what can be done or is affordable? It is now possible if your car dealer uses the SAP S/4HANA tool. SAP builds its variant configuration engine in their S/4HANA platform on top of the constraint solver Gecode. The configuration engine’s role is to keep track of a range of values, how these are combined, and to ensure that only meaningful configurations are offered to users. To do so, it uses Gecode to ensure that combinations are valid and that no restrictions are violated. ...
I’ve been offered the difficult job of writing the sequel to Patrick Prosser’s very entertaining yet insightful column on an old influential paper. I don’t think I can be as entertaining but hopefully I’ll present a complementary view of the same era, now far, far away… My story takes place around the same time as Pat’s, late 1990, as I was about to embark on a Ph.D. after a few months spent in industry which urged me back to graduate studies. It was a good company but my timing was bad: all development had been temporarily halted because much documentation on a government software contract was overdue, and guess who had to help out even though not a single line of code was his… So back to graduate school I went with a Master’s degree in computational geometry in my pocket and a recent interest in logic programming. As Pat pointed out, these were pretty early days for CP and one often wandered alone on the path to discovery. There weren’t very many supervisors who were well versed in the area. Mine was an expert in logic programming and he had recently heard about CP (actually CLP, but more on this later). And the very first paper he gave me to read (yes, made of real paper, not the electronic kind) is the one I’ll share with you. ...
In the 1970’s Artificial Intelligence was the new frontier. The research community divided into two camps: the “clean” ones, like me, who were wedded to logic, and the others for whom knowledge and inference was opaquely embedded in complex neural structures. For clean AI, the USA community used a language called Lisp, while the Europeans used Prolog: “Programmation en Logique”. Computer scientists were allowed to talk French in those days ;-) ...
For some reason, I have been asked to follow up on the great articles by Patrick Prosser and Gilles Pesant on articles with impact. Maybe this has to do with the fact that I started working in that field quite a long time ago, in 1989. As Patrick said, it was before lots of things taken for granted now (world wide web, mobile phones for everyone, Java, laptops, Google, etc) existed. Note that we were no longer using punch card either, we even had Apple Macintoshes in my lab, and we were connected to Internet! Still, can you imagine an Internet without the web? For me, the main things was email. ...
I’ve been asked to write an article “Old CP article with impact” so I am going to write from a personal viewpoint, i.e. an old CP article that had an impact on me. A long time ago (1989) in a University far, far away (Strathclyde) … before the internet, before Google, when researchers would visit the Library once a month, to explore strange new conference proceedings, seek out new journal articles, to boldly go to the librarians’ desk and ask that these findings be photocopied and that they would please phone the said researcher when the copies have been done and the researcher will then walk back to the library, wait in line, pay and pick up the copies. You know, having done all that, you sure as hell read the paper! ...