Model transformation and code synthesis for combinatorial problems

L’utilisation de langages de haut niveau indépendants de la technologie de résolution sous-jacente et le besoin de modéliser finement des contraintes métiers très spécifiques nécessitent de traiter les deux aspects suivants :

• Model analysis and transformation: There is a fundamental need to move from modeling techniques dictated by the services offered by the technologies and solvers being used, to high-level modeling that captures the specifications of the problem being addressed independently of the underlying technology. The consequence is that given a high level model it is important (1) to provide tools to analyze this model, (2) to automatically identify and extract combinatorial sub-problems, (3) to find and break the symmetries of the problem to drastically reduce the size of the research space, and (4) to provide tools to transform models to different technologies.
• Code synthesis for business constraints: Faced with the growing need to provide software that adapts to specific needs and particular profiles, the major players (e.g. IBM, Microsoft, Google) prefer generic methods. The consequence is that while software verification aspects have become established, code synthesis aspects have remained more confined to niches while provoking renewed interest (see for example the Dagstuhl seminar "Software Synthesis" in which researchers from all backgrounds, including constraints, have participated). From a constraint point of view, given the diversity of business constraints, it is illusory to write manually a specific code for each potential constraint. The aim here is therefore to identify families of constraints and understand their structure, in order to synthesize services (propagation of constraints and acceleration of convergence at the fixed point, reformulation into linear programs, heuristic meta-metaphors, "checkers") based on structural properties of these constraints. Formal methods, rewriting and abstract interpretation will be used to automatically generate, prove and simplify formulas associated with properties of interest to us. On this theme, we will rely mainly on the team while calling on existing collaborations with A. Minet (Paris 6) in the field of abstract interpretation.

Dynamic decision support

As we move from strategic to operational planning aspects, there is a need to take into account dynamic decision support issues where constraints change over time. In such a context, it is necessary to vary a pre-existing model over time to take into account hazards or potential futures. This requires specific support at the solver level for incremental stress management. It is also necessary to address major issues. To this end, wide-neighbourhood research methods are a method of choice, with the important limitation, however, of choosing an appropriate neighbourhood. We intend to address this problem by simultaneously using learning and explanation techniques.

Probabilistic models to control combinatorics

In a stress propagation engine it has long been known that algorithms that reduce the range of variables by removing values that do not lead to any solution are most of the time triggered to deduce nothing. A first study on the "alldifferent" constraint was initiated in the previous five years, the aim being to properly trigger the filtering algorithms. In continuation with this work, other constraints will be considered. We will rely on the members of the team that initiated this work as well as on the collaboration with D. Gardy of PriSM.

Learning constrained models, heuristics, strategies and invariants

Learning techniques answer two questions: on the one hand, the question of facilitating access to constraint technology by facilitating the construction of models based on examples or by avoiding the manual search for heuristics, and on the other hand, the automatic capture of behaviours that can be used by decision support programs. In this context, we are interested in learning constraint models, enumeration heuristics and game strategy whose aspects are described by constraints. This work will take place within the framework of structured problems where only a very limited number of examples can be used and a parameterized model must be learned. They also concern problems involving semi-structured time series (i.e. there are measures in relation to an industrial process obeying a certain number of rules) for which the volumes of data are large.