Dynamic abstractions and reformulations in constraint satisfaction problems

(short version) Constraint satisfaction is the most successful computational paradigm for problem-solving today. A major difficulty is efficient formulation of constraint satisfaction proiblems (CSP). This thesis describes several methods for abstractions and reformulations of CSPs. The thesis presents three major results. The first is a technique for finding context-dependent interchangeability, an abstraction that allows simplifying CSP. The second is a technique for abstracting a CSP solution space into a tree of abstractions, which can in particular be used for compiling CSP. The third is a general reformulation technique that allows enumerating all equivalent formulations of a CSP

    Thèse École polytechnique fédérale de Lausanne EPFL, n° 1825 (1998)
    Institut d'informatique fondamentale
    Laboratoire d'intelligence artificielle
    Chaire de recherche opérationnelle SO
    Jury: Ch. Bessière ; E. Freuder ; Th. M. Liebling


    Record created on 2005-03-16, modified on 2017-05-12


Related material