Thesis (EN): Knowledge Compilation in Product Configuration
The constraint-based product configurator CAS Merlin has to solve an NP-complete problem (similar to Boolean satisfiability – SAT) after every user click. Therefore, in the worst case, each click may take exponential time (in the size of the product structure) to evaluate. One way to guarantee polynomial time execution is to use knowledge compilation techniques. In general, these techniques compile the product rules into data structures that allow SAT solving queries in polynomial time. On the other hand, the compilation may take exponential time and the resulting data structures have exponential size. Examples of such data structures are Binary Decision Diagrams (BDD) and their newest variant – Sentential Decision Diagrams (SDD). The goal of the thesis is to examine and evaluate these techniques in the context of product configuration using real industrial benchmarks.
- Do a literature research regarding knowledge compilation and SAT based product configuration.
- Identify concrete techniques that are applicable in the product configurator Merlin.
- Implement and experimentally evaluate the applicable methods in Merlin using real-world customer data.
- Summarize the results in your thesis and/or scientific publication(s).
- You can find, read and understand scientific papers relevant for a given topic.
- Can write performant Java code (fast running programs).
- Not being scared off by hard (NP-Hard) problems.
- Communicating your ideas clearly and precisely in writing (in English).
Benefits of your thesis at CAS
- An ideal environment for you and your thesis: With us you can spend 100% of your worktime on your thesis where you combine state-of-the-art research with real industry use-cases.
- Professional supervision of your thesis in the CAS Future Labs in Karlsruhe: Every year we accompany many students to their successful graduation – you too can benefit from our experience.
- Get to know the CAS culture (offline and online): by working with business coaches and taking part in many other interactive formats. You will experience our unique WeSpirit and make connections across multiple units.