• PhD defended on :
  • 2015-09-17

Abstract

The different languages from the valued decision diagrams (VDD) family benefit from polynomial-time algorithms for some tasks of interest (such as optimization, global inverse consistency, inference) for which no polynomial-time algorithm exists (unless P = NP) when the input is a constraint network or a Bayesian network considered at start.

In this talk, we focus on configuration product problems, and more specifically on-line configuration with an associated valuation function (typically, a price). In this case, the existence of an on-line user forces us to quickly answer to his requests, making impossible the use of languages that does not admit polynomial-time algorithm for this requests. Therefore, our solution consists in an off-line compilation of these problems into languages that admit such polynomial-time algorithms, and thus decreasing the latency for the user.

The first part of the talk is dedicated to the theoretical study of VDDs, an more specifically Algebraic Decision Diagrams (ADDs), Semi ring Labelled Decision Diagrams (SLDDs) and Affine Algebraic Decision Diagrams (AADDs). We revisit the SLDD framework, propose translation procedures between these languages and study the succinctness of these languages. In a second part, we establish a knowledge compilation map of these languages, in which we determine the complexity of requests and transformations corresponding to our needs. We also propose a bottom-up compilation algorithm and several variables and constraints ordering heuristics whose aim is to reduce the size of the compiled form, and the compilation time. The last part is an experimental study of the compilation and the use of the compiled form in product configuration. These experimentations confirm the interest of our approach for on-line product configuration. We also implemented a fully functional bottom-up compiler (the SALADD compiler), which is capable of compiling constraints network and Bayesian network into SLDDs. We also developed a set of functions dedicated to product configuration. The proper functioning and good performances of this program was validated by a validation protocol common to several solvers.

Key-words: Compilation, product configuration, recommendation, valued decision diagram, ordering heuristic, CSP