Reasoning about Constraint Models - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2014

Reasoning about Constraint Models

Résumé

We propose a simple but powerful framework for reasoning about properties of models specified in languages like AMPL, OPL, Zinc or Essence. Using this framework, we prove that reasoning problems like detecting symmetries, redundant constraints or dualities between models are undecidable even for a very limited modelling language that only generates simple problem instances. To provide tools to help the human modeller (for example, to identify when a model has a particular symmetry), it would nevertheless be useful to automate many of these reasoning tasks. To explore the possibility of doing this, we describe two case-studies. The first uses the ACL2 inductive prover to prove inductively that a model contains a symmetry. The second identifies a tractable fragment of MiniZinc and uses a decision procedure to prove that a model implies a parameterized constraint.

Mots clés

Fichier non déposé

Dates et versions

hal-02742999 , version 2 (12-11-2015)
hal-02742999 , version 1 (03-06-2020)

Identifiants

  • HAL Id : hal-02742999 , version 1
  • PRODINRA : 372144
  • WOS : 000354778700063

Citer

Christian Bessiere, Emmanuel Hebrard, Georgios Katsirelos, Zeynep Kiziltan, Nina Narodytska, et al.. Reasoning about Constraint Models. 13th Pacific Rim International Conference on Artificial Intelligence, Dec 2014, Gold Coast, Australia. pp.14. ⟨hal-02742999v1⟩
260 Consultations
438 Téléchargements

Partager

Gmail Facebook X LinkedIn More