Reification

🎓 If–Then–Else Constraints (Reification)

In this lesson, we explore a powerful concept that allows us to model logical “if–then–else” conditions directly in a constraint solver: reification.

🔑 What is Reification?

In everyday language, we often describe rules conditionally:

  • “If it rains, then I’ll take an umbrella; otherwise, I won’t.”
  • “If a student passes all exams, then they graduate.”
  • “If a machine is active, then it must consume at least 5 units of energy.”

These are if–then–else statements.

In constraint programming, reification is the mechanism that connects a constraint to a boolean statement that represents whether the constraint is satisfied. This lets us embed logic directly inside a CSP model.

📐 Formal View

  • Let b be a boolean statement (b ∈ {true, false}, such as b ↔ U < V).
  • Let C be a constraint (e.g., X > Y, A = B + 1).

The reified form is: b -> C

This means:

  • If b = true, then the constraint C must hold.
  • If C holds, then b = true.
  • If b = false, then the constraint C does not hold.

From here, we can combine boolean statements with logical operators (AND, OR, NOT) to encode complex if–then–else rules.

🛠️ If–Then–Else in CSPs

The classic logical rule IF (condition) THEN (consequence) ELSE (alternative) translates into reified constraints:

  1. Introduce a boolean statement b representing the condition.
  2. Tie b to the corresponding constraint.
  3. Use b to control whether the consequence or the alternative holds.

🎨 Example 1: Conditional Discount

Scenario:

  • A shop gives a 10% discount if you buy more than 5 items.
  • Otherwise, no discount applies.

Variables:

  • Qty ∈ {1..10} (number of items).
  • Discount ∈ {0, 10} (percentage).

Constraints:

  • b ↔ (Qty > 5)
  • If b = true, then Discount = 10.
  • If b = false, then Discount = 0.

This is a direct if–then–else encoded with reification.

🎨 Example 2: Machine Energy Usage

Scenario:

  • A machine may be on or off.
  • If it is on, it must consume at least 5 units of energy.
  • If it is off, its energy consumption must be exactly 0.

Variables:

  • MachineState ∈ {0,1}.
  • Energy ∈ {0..10}.

Constraints:

  • MachineState = 1 → Energy ≥ 5.
  • MachineState = 0 → Energy = 0.

Formally, this can be written as two reified implications:

  1. (MachineState = 1) → (Energy ≥ 5)
  2. (MachineState = 0) → (Energy = 0)

This models the machine’s behavior precisely.

🎨 Example 3: Scheduling with Alternatives

Scenario:

  • A task can be executed either on Machine A or on Machine B.
  • If on A, duration = 3.
  • If on B, duration = 5.

Variables:

  • UseA ∈ {0,1} (Boolean).
  • Duration ∈ {3,5}.

Constraints:

  • UseA = 1 → Duration = 3
  • UseA = 0 → Duration = 5

This encodes an exclusive choice between alternatives.

🧠 Why Is This Useful?

Reification and if–then–else constraints are crucial because they allow us to:

  • Express complex logic: rules that depend on conditions, exceptions, or alternatives.
  • Avoid case-splitting: instead of manually modeling separate branches for every possibility, reification keeps everything in a single unified model.
  • Combine optimization with logic: e.g., “If a job is chosen, then it contributes cost; otherwise, cost = 0.”
  • Enhance solver efficiency: by providing the solver with more information about dependencies, it can prune the search space more effectively.

📌 Takeaway

  • Reification connects a Boolean variable with a constraint, letting the solver “know” whether the constraint holds.
  • This enables modeling of if–then–else logic directly in CSPs.
  • It is the key to encoding conditional rules, alternative choices, and dependencies in a clean and solver-friendly way.