🎓 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
bbe a boolean statement (b ∈ {true, false}, such asb ↔ U < V). - Let
Cbe a constraint (e.g.,X > Y,A = B + 1).
The reified form is: b -> C
This means:
- If
b = true, then the constraintCmust hold. - If
Cholds, thenb = true. - If
b = false, then the constraintCdoes 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:
- Introduce a boolean statement
brepresenting the condition. - Tie
bto the corresponding constraint. - Use
bto 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, thenDiscount = 10. - If
b = false, thenDiscount = 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:
(MachineState = 1) → (Energy ≥ 5)(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 = 3UseA = 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.