Constraint satisfaction

Overview

A constraint satisfaction problem (CSP) gives each unknown a finite domain of values and a set of rules that the values must jointly obey. A solution is an assignment that breaks no rule. A constraint optimisation problem (COP) adds one quantity to minimise or maximise 2009.00326 §2.2 2009.00326 §2.3. The author states the problem; a solver does the search 2009.00326 intro.

The only source on this page so far is the PyCSP3 user guide. It documents one toolchain, reports no benchmark results and does not survey the field. The page therefore describes that toolchain and its stated limits.

Variants

Python-embedded model compiled to XCSP3

Variables, domains, rules and an optional objective are written as Python code. Instance data sits in a separate JSON file. The model and data compile to an XCSP3 XML instance, which a solver reads 2009.00326 §5.1. The guide's worked examples use this route. Card: PyCSP3: Modeling Combinatorial Constrained Problems in Python.

Solver backend chosen at solve time

The compiled instance is passed to a backend. The guide names ACE as the default and Choco as the other constant 2009.00326 §6.1. Options are a string passed through to the solver. The guide does not say which backend to prefer for which constraint form 2009.00326 §6.1. The card for the same paper records bugs that the repository's tests report for both backends. Check a backend against the form you need before relying on it. Card: PyCSP3: Modeling Combinatorial Constrained Problems in Python.

When to use which

Implementation sketch

Language-agnostic outline of the common core. The steps follow the guide's workflow; the names are placeholders.

# Declare each unknown with a finite domain: range, set or symbols  [§2.2]
variables = declare_variables(domains)

# Post rules that every solution must satisfy; calls may repeat  [§2.2]
post_constraints(rules)

# Optionally name one quantity to minimise or maximise  [§2.3]
set_objective(term)

# Compile model and data into a standard instance file  [§5.1]
instance = compile_model(model_file, data_file)

# Run a backend on the instance and read its status  [§5.2] [§6.1]
status = run_solver(instance, backend="ACE")

# Read values only when the status reports an answer  [§5.2]
if status in {SAT, OPTIMUM}:
    answers = read_values(variables)

Status values in the guide are UNSAT, SAT, OPTIMUM, UNKNOWN and CORE 2009.00326 §5.2.

Contradictions

• Solver backends. The guide's introduction names Picat and CP-SAT as solvers that read the XCSP3 instance 2009.00326 intro. The card for this paper checked the repository the guide points to and found backends for ACE, Choco and two other solvers, but none for Picat or CP-SAT. The card did not confirm whether an external route reaches them. Card: PyCSP3: Modeling Combinatorial Constrained Problems in Python.
• Model count. The arXiv abstract says "more than 50" illustrative models. The guide's own abstract says "more than 60" 2009.00326 intro. The card follows the guide. Card: PyCSP3: Modeling Combinatorial Constrained Problems in Python.
• Indexing flag. The guide spells the flag -dontadjustindexing 2009.00326 §3.2. The repository registers dont_adjust_indexing. The card did not run the compiler, so the accepted spelling is unverified.

Papers

• PyCSP3: Modeling Combinatorial Constrained Problems in Python: a Python layer that compiles finite-domain models to XCSP3 and runs ACE or Choco; a user guide with no benchmark results.