Constraint, Rule, and Probabilistic Paradigms

Constraint programming expresses variables and conditions; a solver searches for assignments satisfying those conditions.

17.1 Constraint programming

Constraint programming expresses variables and conditions; a solver searches for assignments satisfying those conditions.

Example in pseudocode:

This expresses a scheduling constraint rather than prescribing a loop to search every combination. The exact solver language and syntax vary.

variables:
  startA, startB ∈ 0..10

constraints:
  startA + durationA <= startB
  startB + durationB <= 12

find a valid assignment

17.2 SAT and SMT

SAT: determine whether a Boolean formula is satisfiable.

SMT: extend satisfiability reasoning with theories such as integers, bit-vectors, arrays, and other domains.

These tools can support configuration validation, test generation, symbolic execution, verification, and scheduling.

17.3 Rule engines

A rule engine evaluates business rules separately from core application code. Benefits include centralizing policy and supporting business-managed rules. Risks include rule conflicts, order dependence, hidden control flow, difficult testing, and unsafe dynamic expression evaluation.

Rules should be versioned, validated, audited, and tested with representative and boundary inputs.

17.4 Probabilistic programming

Probabilistic programming expresses models containing random variables and probability distributions, often allowing inference over unknown quantities. It is useful for statistical modeling and uncertainty-aware applications.

Conceptual notation:

This is mathematical pseudocode, not a specific language. Probabilistic models require domain assumptions, appropriate data, diagnostics, and uncertainty interpretation.

prior: conversion_rate ~ Beta(2, 8)
observed_successes ~ Binomial(trials, conversion_rate)
infer posterior distribution of conversion_rate

17.5 Optimization paradigms

Optimization models define an objective and constraints, such as minimizing delivery time subject to capacity and scheduling limits. A solver's result depends on formulation, feasibility, objective choice, and solver guarantees.

Exercise

Model course-session scheduling with room capacity, instructor availability, and student conflicts. Compare a procedural heuristic with a constraint solver.

Quiz

? What does an SMT solver add to SAT?
+ Reasoning in theories such as integers, bit-vectors and arrays. :: SAT is purely Boolean.
- Faster Boolean solving only. :: The difference is expressiveness.
- Probabilistic inference. :: That is probabilistic programming.
- Garbage collection. :: Unrelated.

? What does the constraint program for two scheduled tasks express?
+ The conditions a valid assignment must satisfy; the solver searches for one. :: No search loop is written by hand.
- A loop over every combination. :: That would be a procedural approach.
- The fastest possible schedule. :: Without an objective it only finds a valid schedule.
- A probability distribution. :: Constraint programs state hard conditions.

? Which are risks of rule engines? (select all that apply)
+ Rule conflicts and order dependence :: Two rules may disagree.
+ Hidden control flow :: Which rule fired is not obvious.
+ Unsafe dynamic expression evaluation :: Rules must not execute arbitrary code.
- They cannot be versioned :: They can and should be.