Non-binary quantified CSP: algorithms and modelling

Peter Nightingale

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)

Abstract

The Quantified Constraint Satisfaction Problem (QCSP) extends classical CSP in a way which allows reasoning about uncertainty. In this paper I present novel algorithms for solving QCSP. Firstly I present algorithms to perform constraint propagation on reified disjunction constraints of any length. The algorithms make full use of quantifier information to provide a high level of consistency. Secondly I present a scheme to enforce the non-binary pure value rule. This rule is capable of pruning universal variables. Following this, two problems are modelled in non-binary QCSP: the game of Connect 4, and a variant of job-shop scheduling with uncertainty, in the form of machine faults. The job shop scheduling example incorporates probability bounding of scenarios (such that only fault scenarios above a probability threshold are considered) and optimization of the schedule makespan. These contribute to the art of modelling in QCSP, and are a proof of concept for applying QCSP methods to complex, realistic problems. Both models make use of the reified disjunction constraint, and the non-binary pure value rule. The example problems are used to evaluate the QCSP algorithms presented in this paper, identifying strengths and weaknesses, and to compare them to other QCSP approaches.

Original languageEnglish
Pages (from-to)539-581
Number of pages43
JournalConstraints
Volume14
Issue number4
DOIs
Publication statusPublished - Dec 2009

Keywords

  • QCSP
  • Quantified constraints
  • Modelling
  • Propagation algorithm
  • Reasoning algorithm
  • BOOLEAN-FORMULAS

Fingerprint

Dive into the research topics of 'Non-binary quantified CSP: algorithms and modelling'. Together they form a unique fingerprint.

Cite this