Deduce New Constraints

Inference refers to the process of deducing new constraints that are logically implied by the existing constraints. This allows propagating indirect constraints to further reduce the search space.

For example, consider a problem with constraints:

A < B B < C

We can infer and add a new constraint:

A < C

Because if A < B and B < C, then logically A < C must also hold based on transitivity.

Some common types of inference:

• Transitive inference - Apply transitive closure over inequality relationships

• Subsumption - If X < Y and X < Z, infer Z < Y

• Path consistency - For every pair of variables Xi and Xj, ensure constraints are consistent along all paths between them.

• Database constraints - Apply database constraint rules like functional dependencies.

By applying logic and deductive reasoning, inference expands the scope of constraints and propagates indirect constraints that are implied logically. This further prunes inconsistent values through chains of deduction.

So in summary, inference allows leveraging dependencies between constraints to deduce new constraints automatically. This expands the impact of each constraint on pruning the search space.