12 April 2022
In Logic conditions as constraints - Part 1 we introduced a technique for converting a broad class of logic conditions into constraints. While that technique is effective, it can be difficult to apply.
In this article, we present an alternative technique specifically designed to improve the proficiency of students learning to formulate models.
That is, we use two techniques for converting logic conditions into constraints:
- Decomposition and Translation (D&T). This technique is described in the paper "Teaching use of binary variables in integer linear programs: Formulating logical conditions".
- Conjunctive Normal Form (CNF). We described the CNF technique in Part 1.
After describing the D&T technique, we focus on replicating the paper's examples, applying both the D&T and the CNF techniques to illustrate how each technique can be applied to a variety of logic condition formulation situations.
Decomposition and Translation technique
Motivation for the D&T technique
Binary variables are often used in mixed integer linear programs to impose logical conditions. However, it is often not obvious how to formulate constraints to enforce the required conditions. As the paper's authors note:
A quantitative approach to problem solving involves more than just numbers: It requires creating a mathematical model of the situation being analyzed. Unfortunately, this modeling step is frequently a major stumbling block for students.
... As a result, we began investigating obstacles to modeling logical conditions and searching for ways to help our students overcome them.
The result of their investigation is the Decomposition and Translation (D&T) technique, which we summarize below.
The paper describes the D&T technique in more detail. It is worthwhile reading the paper to understand the context of the technique more fully.
Summary of the D&T technique
We start with a set of Boolean propositions, \(A_i, i=1..n\), each of which could be true or false. For example, \(A_i\) might mean "Speaker \(i\) is present."
If all the \(A_i\) must be true, then we combine them using the AND operator. This is referred to as "ALL \(A_i\)".
If at least one of the \(A_i\) must be true, then we combine them using the OR operator. This is referred to as "SOME \(A_i\)".
If n=1, then we just have \(A\). In that case, "ALL \(A_i\)" and "SOME \(A_i\)" are equivalent.
As discussed in Part 1, we're interested in logical implications in either of the forms:
- \(A \implies B\), which says that \(A\) implies \(B\). The statement can be interpreted as "If \(A\), then \(B\)", meaning that \(B\) must be true if \(A\) is true; but \(B\) could be true if \(A\) is false.
- \(A \iff B\), which says that \(A\) implies \(B\) and \(B\) implies \(A\). The statement can be interpreted as "If and only if \(A\), then \(B\)", meaning that either both statements are true or both are false.
Like for \(A_i, i=1..n\), if \(B\) contains more than one proposition, then we denote it as \(B_j, j=1..m\).
Given the left-hand side (LHS) \(A_i\), and the right-hand side (RHS) \(B_j\), we have three rules for converting logic implications into constraints:
- Decomposition Rule D1. If the LHS is SOME \(A_i\), then break up the statement into \(n\) statements, one for each \(A_i\). The RHS remains unchanged.
- Decomposition Rule D2. If the RHS is ALL \(B_j\), then break up the statement into \(m\) statements, one for each \(B_j\). The LHS remains unchanged.
- Translation Rule T. Translate the implication ALL \(A_i \implies\) SOME \(B_j\) into a constraint \(\sum A_i \le \sum B_j+n-1\).
Rules D1, D2, and T are sufficient to represent any pure form implication as a set of linear constraints using binary variables. Note that sometimes we may need to apply more than one Transition rule.
There are three possible values on the LHS of an implication: \(A\), SOME \(A_i\), and ALL \(A_i\). Similarly, there are three possible values on the RHS of an implication: \(B\), SOME \(B_j\), and ALL \(B_j\). Therefore, in total, there are nine possibly combinations of implications, as listed in Figure 1. The figure replicates Table 1 in the paper, with the addition of labels for the combinations, which we'll refer to in the examples below to indicate which instance of the transition rule we're applying.
Examples
Overview of examples
The following examples are from the paper. Each example states a situation that we need to model as a constraint (or set of constraints).
We first replicate each example using the D&T technique. Then we repeat each example using the CNF technique, following the rules and steps described in Part 1. We also check that our CNF derivation is correct using Wolfram|Alpha.
Our main objective is to demonstrate that the D&T and CNF techniques produce the same constraints. We also want to see if the D&T technique is easier to apply.
Example 1 using D&T
Situation: If either of the products A or B (or both) are manufactured, then at least one of the products C, D, or E must also be manufactured.
Notation: LHS products A and B; RHS products C, D, and E.
Implication: SOME \((A\), \(B)\) \(\implies\) SOME \((C\), \(D\), \(E)\)
Apply Rule D1:
- \(A \implies\) SOME \((C\), \(D\), \(E)\)
- \(B \implies\) SOME \((C\), \(D\), \(E)\)
Apply Rule T (Combination 2):
- \(A \le C+D+E\)
- \(B \le C+D+E\)
Example 1 using CNF
Implication: \(A \lor B \implies C \lor D \lor E\)
Express in CNF (using the rules from Part 1):
Apply Rule 7: \(\lnot (A \lor B) \lor (C \lor D \lor E)\)
Apply Rule 2: \((\lnot A \land \lnot B) \lor (C \lor D \lor E)\)
Apply Rule 5 gives CNF: \((\lnot A \lor C \lor D \lor E) \land (\lnot B \lor C \lor D \lor E)\)
Using the Wolfram|Alpha input A or B implies C or D or E confirms that the CNF is correct.
Convert to constraint(s):
- \((1-A)+C+D+E \ge 1\)
- \((1-B)+C+D+E \ge 1\)
Which can be simplified to:
- \(A \le C+D+E\)
- \(B \le C+D+E\)
This is the same as for the D&T technique.
Example 2 using D&T
Situation: If all three projects are to go forward, either Assembly Line 1 or Assembly Line 2 (or both) must be assigned to them.
Notation: LHS projects P1, P2, and P3; RHS assembly line L1 and L2.
Implication: ALL \((P1\), \(P2\), \(P3)\) \(\implies\) SOME \((L1\), \(L2)\)
Apply Rule T (Combination 8, with \(n\)=3 projects):
\(P1+P2+P3 \le L1+L2+3-1\)
Which can be simplified to:
\(P1+P2+P3 \le L1+L2+2\)
Example 2 using CNF
Implication: \(P1 \land P2 \land P3 \implies L1 \lor L2\)
Express in CNF:
Apply Rule 7: \(\lnot (P1 \land P2 \land P3) \lor (L1 \lor L2)\)
Apply Rule 3: \((\lnot P1 \lor \lnot P2 \lor \lnot P3) \lor (L1 \lor L2)\)
Simplify to CNF: \(\lnot P1 \lor \lnot P2 \lor \lnot P3 \lor L1 \lor L2\)
Using the Wolfram|Alpha input P1 and P2 and P3 implies L1 or L2 confirms that the CNF is correct.
Since the CNF does not include any AND operators, we convert it to just one constraint:
\((1-P1)+(1-P2)+(1-P3)+L1+L2 \ge 1\)
Which can be simplified to:
\(P1+P2+P3 \le L1+L2 + 2\)
This is the same as for the D&T technique.
Example 3 using D&T
Situation: If Job 1 and Job 2 are both started on time, then both must be finished on time.
Notation: LHS start on time S1 and S2; RHS finish on time F1 and F2.
Implication: ALL \((S1\), \(S2)\) \(\implies\) ALL \((F1\), \(F2)\)
Apply Rule D2:
- ALL \((S1\), \(S2)\) \(\implies\) \(F1\)
- ALL \((S1\), \(S2)\) \(\implies\) \(F2\)
Apply Rule T (Combination 8, with \(n=2\)):
- \(S1+S2 \le F1+1\)
- \(S1+S2 \le F2+1\)
Example 3 using CNF
Implication: \(S1 \land S2 \implies F1 \land F2\)
Express in CNF:
Apply Rule 7: \(\lnot (S1 \land S2) \lor (F1 \land F2)\)
Apply Rule 3: \((\lnot S1 \lor \lnot S2) \lor (F1 \land F2)\)
Apply Rule 5 gives CNF: \((\lnot S1 \lor \lnot S2 \lor F1) \land (\lnot S1 \lor \lnot S2 \lor F2)\)
Using the Wolfram|Alpha input S1 and S2 implies F1 and F2 confirms that the CNF is correct.
Convert to constraint(s):
- \((1-S1)+(1-S2)+F1 \ge 1\)
- \((1-S1)+(1-S2)+F2 \ge 1\)
Which can be simplified to:
- \(S1+S2 \le F1+1\)
- \(S1+S2 \le F2+1\)
This is the same as for the D&T technique.
Example 4 using D&T
Situation: If warehouses are built at any of locations P1, P2, P3, or P4, then no warehouses can be built at locations Q1, Q2, Q3, Q4, or Q5.
Notation: LHS warehouse at locations \(P_i\) for \(i=1..n\); RHS warehouse at locations \(Q_j\) for \(j=1..m\).
Implication: SOME \((P_i)\) \(\implies\) None of \(Q_j)\), which means SOME \((P_i)\) \(\implies\) ALL \((1-Q_j)\)
Apply Rule D1:
\(P_i \implies\) ALL \((1-Q_j)\) \(\forall\) \(i=1..n\)
Apply Rule T (Combination 3):
\(P_i \implies\) \((1-Q_j)\) \(\forall\) \(i=1..n\) and \(j=1..m\)
This gives us 20 implications (since n=4 and m=5), each of which has a single \(P_i\) term on the LHS and a single \(Q_j\) term on the RHS. Now we can apply Rule T again (with Combinations 7, 8, and 9 all being equivalent in this case) to form constraints:
\(P_i \le (1-Q_j)+n-1\) where \(n=1\) for each of the 20 implications.
Which can be simplified to 20 constraints of the form:
\(P_i \le 1-Q_j\) \(\forall\) \(i=1..n\) and \(j=1..m\)
Example 4 using CNF
Implication: \(P1 \lor P2 \lor P3 \lor P4 \implies \lnot Q1 \land \lnot Q2 \land \lnot Q3 \land \lnot Q4 \land \lnot Q5\)
Express in CNF:
Apply Rule 7: \(\lnot (P1 \lor P2 \lor P3 \lor P4) \lor (\lnot Q1 \land \lnot Q2 \land \lnot Q3 \land \lnot Q4 \land \lnot Q5)\)
Apply Rule 2: \((\lnot P1 \land \lnot P2 \land \lnot P3 \land \lnot P4) \lor (\lnot Q1 \land \lnot Q2 \land \lnot Q3 \land \lnot Q4 \land \lnot Q5)\)
If we let \(x=(\lnot P1 \land \lnot P2 \land \lnot P3 \land \lnot P4)\), then we get:
Apply Rule 5: \((x \lor \lnot Q_1) \land (x \lor \lnot Q_2) \land (x \lor \lnot Q_3) \land (x \lor \lnot Q_4) \land (x \lor \lnot Q_5)\)
Substitute \(x\) into the above, and apply Rule 5 again, to give a CNF with 20 groups:
Using the Wolfram|Alpha input (P1 or P2 or P3 or P4) implies (not Q1 and not Q2 and not Q3 and not Q4 and not Q5) confirms that the CNF is correct.
Convert to 20 constraints of the form:
\((1-P_i)+(1-Q_j) \ge 1\) \(\forall\) \(i=1..n\) and \(j=1..m\)
Which can be simplified to 20 constraints of the form:
\(P_i \le 1-Q_j\) \(\forall\) \(i=1..n\) and \(j=1..m\)
This is the same as for the D&T technique.
Example 5 using D&T
Situation: Z3 can be produced if and only if a machine Z1 and a worker Z2 are available.
Notation: LHS product Z3; RHS machine Z1 and worker Z2.
The "if and only if" produces a two-way implication:
\(Z3 \iff\) ALL \((Z1\), \(Z2)\)
The two-way implication can be split into two one-way implications:
- \(Z3 \implies\) ALL \((Z1\), \(Z2)\)
- ALL \((Z1\), \(Z2)\) \(\implies\) \(Z3\)
For the first implication, apply Rule D2:
- \(Z3 \implies\) \(Z1\)
- \(Z3 \implies\) \(Z2\)
Apply Rule T (Combination 1):
- \(Z3 \le Z1\)
- \(Z3 \le Z2\)
For the second implication, apply Rule T (Combination 7, \(n=2\)):
\(Z1+Z2 \le Z3+1\)
Example 5 using CNF
Implication: \(Z3 \iff Z1 \land Z2\)
The two-way implication can be split, using Rule 8, into two one-way implications:
- \(Z3 \implies Z1 \land Z2\)
- \(Z1 \land Z2 \implies Z3\)
Express first implication in CNF:
Apply Rule 7: \(\lnot Z3 \lor (Z1 \land Z2)\)
Apply Rule 5 to give CNF: \((Z1 \lor \lnot Z3) \land (Z2 \lor \lnot Z3)\)
Using the Wolfram|Alpha input Z3 implies Z1 and Z2 confirms that the CNF is correct.
Convert to constraint(s):
- \(Z1 + (1-Z3) \ge 1\)
- \(Z2 + (1-Z3) \ge 1\)
Which can be simplified to:
- \(Z3 \le Z1\)
- \(Z3 \le Z2\)
This is the same as for the D&T technique.
Express second implication in CNF:
Apply Rule 7: \(\lnot (Z1 \land Z2) \lor Z3\)
Apply Rule 3 to give CNF: \(\lnot Z1 \lor \lnot Z2 \lor Z3\)
Using the Wolfram|Alpha input Z1 and Z2 implies Z3 confirms that the CNF is correct.
Convert to constraint(s):
- \((1-Z1) + (1-Z2) + Z3 \ge 1\)
Which can be simplified to:
- \(Z1 + Z2 \le Z3 + 1\)
This is the same as for the D&T technique.
Example 6 using D&T
Situation: Project Z3 can be funded if and only if project Z1 or project Z2, or both projects are funded.
Notation: LHS project Z3; RHS projects Z1 and Z2.
The "if and only if" produces a two-way implication:
\(Z3 \iff\) SOME \((Z1\), \(Z2)\)
The two-way implication can be split into two one-way implications:
- \(Z3 \implies\) SOME \((Z1\), \(Z2)\)
- SOME \((Z1\), \(Z2)\) \(\implies\) \(Z3\)
For the first implication, apply Rule T (Combination 2):
- \(Z3 \le Z1 + Z2\)
For the second implication, apply Rule D1:
- \(Z1 \implies Z3\)
- \(Z2 \implies Z3\)
Convert to constraint(s):
- \(Z1 \le Z3\)
- \(Z2 \le Z3\)
Example 6 using CNF
Implication: \(Z3 \iff Z1 \lor Z2\)
The two-way implication can be split, using Rule 8, into two one-way implications:
- \(Z3 \implies Z1 \lor Z2\)
- \(Z1 \lor Z2 \implies Z3\)
Express first implication in CNF:
Apply Rule 7 to give CNF: \(Z1 \lor Z2 \lor \lnot Z3\)
Using the Wolfram|Alpha input Z3 implies Z1 or Z2 confirms that the CNF is correct.
Convert to constraint(s):
- \(Z1 + Z2 + (1-Z3) \ge 1\)
Which can be simplified to:
- \(Z3 \le Z1 + Z2\)
This is the same as for the D&T technique.
Express second implication in CNF:
Apply Rule 7: \(\lnot (Z1 \lor Z2) \lor Z3\)
Apply Rule 2: \((\lnot Z1 \land \lnot Z2) \lor Z3\)
Apply Rule 5 to give CNF: \((\lnot Z1 \lor Z3) \land (\lnot Z2 \lor Z3)\)
Using the Wolfram|Alpha input Z1 or Z2 implies Z3 confirms that the CNF is correct.
Convert to constraint(s):
- \((1-Z1) + Z3 \ge 1\)
- \((1-Z2) + Z3 \ge 1\)
Which can be simplified to:
- \(Z1 \le Z3\)
- \(Z2 \le Z3\)
This is the same as for the D&T technique.
Summary of examples
For each of the examples we derived identical constraints using the D&T and CNF techniques, as shown in Figure 2.
We found that the D&T technique is generally easier to apply, and requires fewer steps, compared with the CNF technique. This is because the decomposition and translation rules already encapsulate some of the steps that are necessary when applying the CNF technique.
Our experience with the D&T technique is consistent with research reported in the source paper. The authors conducted experiments with students to assess their performance in formulating logic conditions as constraints. Overall, student performance improved after being taught the D&T technique.
Conclusion
In this article, we describe the Decomposition and Translation (D&T) technique for formulating logical conditions as constraints. We illustrate the technique using a set of examples, and we repeat the examples using the CNF technique described in Logic conditions as constraints - Part 1. In general, we found that the D&T technique is quicker and easier to apply, which is consistent with student experience.
As the paper's authors mention, the D&T technique is applicable to a broad class of logical implication problems, though not all logic conditions problems are amenable to the technique. The same is true for the CNF technique. Nonetheless, both the D&T and CNF techniques are very useful tools to help us formulate optimization models.
If you would like to know more about these formulation techniques, or you want help with your own models, then please contact us.
References
The D&T technique is described in the paper:
Stevens, S.P. & Palocsay, S.W. (2017). "Teaching use of binary variables in integer linear programs: Formulating logical conditions", INFORMS Transactions on Education 18(1):28-36.