Global constraint

Overview

A global constraint is a named rule that ties together a whole group of variables and has a fixed meaning. Examples on the PyCSP3 card are allDifferent, regular, cumulative, circuit and knapsack, each posted as one rule over a list of variables 2009.00326 §3.5 2009.00326 §3.3 2009.00326 §3.22 2009.00326 §3.25 2009.00326 §3.24. The same meaning can often be written with simpler rules, but the guide's catalogue of named forms is the reason to prefer one.

The only source on this page is the PyCSP3 user guide. The guide lists the forms and their syntax. It does not explain how a solver filters values for each form, and it reports no timings. The page therefore states what the guide offers and where its backends were found to disagree with the guide's intent.

Variants

Set and sequence rules

Rules that relate the values of a group of variables as a whole. allDifferent requires every variable to take a different value 2009.00326 §3.5. regular requires the sequence of values to be accepted by a given automaton 2009.00326 §3.3. count fixes how many variables take a given value 2009.00326 §3.12. sum fixes a linear total 2009.00326 §3.11. Card: PyCSP3: Modeling Combinatorial Constrained Problems in Python.

Resource and packing rules

Rules that model capacity. cumulative is the named form for tasks that share a resource 2009.00326 §3.22. binPacking is the named form for placing items into bins 2009.00326 §3.23. knapsack is the named form for selecting items under a limit 2009.00326 §3.24. Card: PyCSP3: Modeling Combinatorial Constrained Problems in Python.

Structure and indexing rules

Rules that fix the shape of a solution. circuit is the named form for a cycle over the variables 2009.00326 §3.25. element makes a value equal to the entry of an array at a variable index 2009.00326 §3.19. Card: PyCSP3: Modeling Combinatorial Constrained Problems in Python.

Shortcut forms

Some named forms are written as shortcuts over Count or Sum, such as Exist and Hamming 2009.00326 ch. 9. The guide presents them as convenience names. It does not say whether a shortcut is compiled to the same instance as the form it stands for.

When to use which

The guide gives no performance comparison, so the choice rests on the shape of the problem. The table names the form the guide documents for each need.

Implementation sketch

Language-agnostic outline. The names are placeholders, and the steps follow the guide's workflow for posting rules.

# Declare the unknowns with their finite domains  [arxiv:2009.00326 §2.2]
variables = declare_variables(domains)

# Post one named rule over the whole group  [arxiv:2009.00326 §3.5]
post_global("allDifferent", variables)

# Post a resource rule over tasks, with start times, durations and demands  [arxiv:2009.00326 §3.22]
post_global("cumulative", starts, durations, demands, capacity)

# Compile and solve as in the guide's workflow  [arxiv:2009.00326 §5.1] [arxiv:2009.00326 §6.1]
instance = compile_model(model_file)
status = run_solver(instance, backend="ACE")

The argument lists here are schematic. Check the exact signature of each form in the guide's constraint sections before use 2009.00326 ch. 3.

Contradictions

• Indexing flag. The guide spells it -dontadjustindexing 2009.00326 §3.2. The repository registers dont_adjust_indexing. The card did not run the compiler, so the accepted spelling is unverified. Card: PyCSP3: Modeling Combinatorial Constrained Problems in Python.

Pitfalls

• Backend bugs for allDifferent. ACE raises an error on allDifferent over expressions when the combined domain size equals the number of terms 2009.00326 §3.5. The repository's tests record this bug.
• Backend bugs for regular. ACE fails on regular when the variables have different domains 2009.00326 §3.3. The repository's tests record this bug.
• Backend bugs for sum and element. Choco gives wrong solutions for a sum with notin. Choco also ignores reifiedBy on an element (member) constraint 2009.00326 §3.11 2009.00326 §3.19. The repository's tests record both bugs.
• Index range for element. An index whose domain reaches outside the array does not compile unless -force_element_index is set or options.force_element_index = True is written in the model. The guide also shows a workaround with an auxiliary variable 2009.00326 §3.19.
• Silent index adjustment. For arrays declared in the model, an index at or beyond the length is taken modulo the length, with a warning. Disable this with -dont_adjust_indexing 2009.00326 §3.2. The guide spells the flag -dontadjustindexing; the repository registers the underscore form. The card did not run the compiler, so the accepted spelling is unverified.
• Version of the bugs. The repository's tests record each bug at the time its test was written. Check them against current solver versions before relying on a backend for one of these forms.
• Unknowns. The guide does not state how long any form takes to solve, or which backend to prefer for which form.

Papers

• PyCSP3: Modeling Combinatorial Constrained Problems in Python: a Python layer that posts named global rules such as allDifferent, regular and cumulative, compiles them to XCSP3, and runs ACE or Choco; a user guide with no benchmark results.