PROPAGATION DE CONTRAINTES OU PROGRAMMATION AUTOMATIQUE

J.-L. LAURIERE

IBP-Laforia 1996/19: Rapport de Recherche Laforia / Laforia research reports
34 pages - Octobre/October 1996 - French document.

PostScript : 103 Ko /Kb

Titre / Title: PROPAGATION DE CONTRAINTES OU PROGRAMMATION AUTOMATIQUE

Résumé : Après avoir effectué un bilan sur les problèmes NP-complets et les résolveurs de problèmes disponibles, nous nous intéressons aux cas où le schéma propagation+choix n'est pas efficace.
Soit parce que le système ne trouve pas les symétries de l'énoncé et répète inlassablement l'étude de situations équivalentes, ou bien parce qu'il a déterminé une solution quasi-optimale mais perd son temps sur la preuve de l'optimalité ou encore parce que, après avoir effectivement pris en compte la plupart des contraintes, il est devant un problème très peu contraint et perd son temps à propager des informations sans intérêt.
Nous pensons que dans ces conditions la solution est la programmation automatique.
Des exemples concrets sont explicités. Le nouveau logiciel RABBIT est présenté. Il est effectivement capable de générer des programmes de plusieurs milliers d'instructions qui permettent de conclure en un temps CPU jusqu'à cent fois inférieur à un pur CSP.

Abstract : After an initial assessment of NP-complete problems and existing problem solvers, the author goes on to consider all the cases where a propagation + choice approach is not efficient. The system is incapable of finding the symmetries of the problem and either it endlessly studies equivalent situations or it determines a quasi-optimal solution and then wastes time proving this optimality, or else it takes most of the constraints into account but then, when having to deal with an under-constrained problem, wastes time propagating useless information.
To overcome these problems,, automatic programming would seem to be an ideal solution for the author.
Concrete examples are given and RABBIT, a new software deriving from ALICE, is described. This software can generate programs containing thousands of instructions which can be run up to one hundred times faster than a pure CSP.

Publications internes Laforia 1996 / Laforia research reports 1996