15.3 Logical Constraints

Logical constraints can also be formalised as integer constraints. For example, let’s say that \(X_1\) is whether I decide to buy a new house, and \(X_2\) is whether I decide to renovate the new house. We restrict both \(X_1\), \(X_2\) to be either \(0\) or \(1\). Obviously, I need to purchase the house before I can renovate it, so \(X_1\) is a pre-requisite for \(X_2\).

Using logic, I can write that:

\[ \text{if I choose } X_2, \text{then I must choose } X_1 \text{ as well.} \]

This logical constraint can be formalised as the following integer-valued constraint:

\[X_1 - X_2 \geq 0\] (In fact, this is not just an integer-valued constraint, but it is even stronger: the two variables are binary-valued).

The intuition is that if \(X_2\) is 1, then this forces \(X_1\) to be 1 too. Let us check:

  • \(X_1 = 0\), \(X_2 = 0\): Constraint: \(0 - 0 = 0 \geq 0\) is satisfied. This is fine since I don’t purchase the house and I don’t renovate the house.
  • \(X_1 = 1\), \(X_2 = 0\): Constraint: \(1 - 0 = 1 \geq 0\) is satisfied. This is fine since I can choose to purchase the house without renovating it.
  • \(X_1 = 1\), \(X_2 = 1\): Constraint: \(1 - 1 = 0 \geq 0\) is satisfied. Again, this is fine since I can choose to both purchase and renovate the house.
  • Most importantly: \(X_1 = 0\), \(X_2 = 1\): Constraint: \(0 - 1 = -1 \not \geq 0\). The constraint is not satisfied. This makes sense, because I cannot not purchase the house (\(X_1=0\)) but still choose to renovate it (\(X_2=1\)).

Thus, we can check and see that this integer constraint correctly captures the intuition behind the logical constraint.

In general, the following table summaries how some logical constraints can be represented using binary decision variables:

Logical Condition Linear Constraint
if \(A\) then \(B\) \(B - A \geq 0\)
if not \(A\) then \(B\) \(B - (1 - A) \geq 0\), or \(A + B \geq 1\)
At most one of \(A\), \(B\) \(A + B \leq 1\)
At least one of \(A\), \(B\) \(A + B \geq 1\)
if (\(A\) or \(C\)) then \(B\) \(B - (A+C) \geq 0\)
if (\(A\) and \(C\)) then \(B\) \(B - (A+C) \geq -1\), or \((A+C) - B \leq 1\)
if \(A\) then (\(B\) or \(C\)) \((B+C) - A \geq 0\)
if \(A\) then (\(B\) and \(C\)) \((B+C) - 2A \geq 0\)

15.3.1 How to specify logical constraints

Earlier we saw that to tell lpSolve that certain decision variables are integer-valued, we used an option int.vec = c(...). If we want to tell lpSolve that instead some decision variables are binary-valued, then we use: binary.vec = c(...). And that’s it! lpSolve does everything else for us.

(In fact, it’s harder to ensure that you have written down the constraints correctly!)

15.3.2 Logical Constraints Example: Planning university courses

Let’s see logical constraints in action in the following example.

Natalie has decided to switch her career to data science, as she feels it has more prospects than her previous industry. She is eyeing a “Pico-masters (TM)” program at her local university, where she has to complete 40 units of courses to satisfy the pico-degree. (“Pico-masters” and “nano-masters” are fictional—at least, for now—but some online education platforms and universities like edX are offering “MicroMasters®” and other similar products.)

The program offers the following courses, in STatistics, ProGramming, and Data Management, along with their associated costs and pre-requisites. The pre-requisites for each course must be fulfilled before students are allowed to take that course. In order to finish the PicoMasters, she needs to finish a specialization in one of the three tracks, which is fulfilled by completing the “Level 3” version of that course. Natalie has also indicated her personal interest in each course, in the following table.

Course Units Pre-requisites Interest
ST1 10 - 8
ST2 10 ST1 4
ST3 10 ST2 6
PG1 10 - 7
PG2a 10 PG1 5
PG2b 10 PG1 6
PG3 10 PG2a or PG2b 3
DM1 10 - 4
DM2 10 DM1 6
DM3 10 DM2 7

Imagine that her goal is to maximize her interest and satisfy the requirements of the degree, while also taking exactly 40 units (in order to keep costs low). Which classes should she take?

First, let’s define our decision variables, by just using \(X_1\) to \(X_{10}\) to correspond to taking each of the ten courses, in the order in the table above. That is,

\(X_1\) = Take ST1, \(X_2\) = Take ST2, \(X_3\) = Take ST3,
\(X_4\) = Take PG1, \(X_5\) = Take PG2a, \(X_6\) = Take PG2b, \(X_7\) = Take PG3,
\(X_8\) = Take DM1, \(X_9\) = Take DM2, \(X_{10}\) = Take DM3

Now let’s tackle the constraints one-by-one.

Consider the following pre-requisite:

Natalie needs to take ST1 before being allowed to take ST2.

We can represent this using the following constraint:

\[ X_1 - X_2 \geq 0 \]

You can easily check if this is correct by ‘testing’ it by subtituting values. If Natalie takes ST2 (i.e., \(X_2 = 1\)), then we have the following inequality: \(X_1 - 1 \geq 0\). In order for this also to be true, we need \(X_1\) to also be 1. This means that Natalie taking ST2 (\(X_2 = 1\)) actually forces her to also have taken ST1 (\(X_1 = 1\)).

Similarly, we can write out the pre-requisite constraints for the rest. Now, let’s consider one more case:

Natalie needs to take either PG2a OR PG2b before being allowed to take PG3.

One easy thing to try is to replace ST2 (\(X_2\)) in the previous inequality with PG3 (\(X_7\)), and replace ST1 (\(X_1\)) with (PG2a or PG2b), or (\((X_5+X_6)\)). So let’s try:

\[ (X_5 + X_6) - X_7 \geq 0 \]

And actually this is the correct inequality! Let’s test this out. If Natalie takes PG3, then \(X_7=1\), and so we are left with: \((X_5 + X_6) - 1 \geq 0\). This inequality will be satisfied if \(X_5\) is 1, or if \(X_6\) is 1, that is, if she takes either PG2a or PG2b. (Note that this will also be satisifed if BOTH \(X_5\) and \(X_6\) is 1 – there is nothing stopping her from taking both PG2a and PG2b!)

And finally let’s consider the constraint that she needs to finish a specialization. That is, she needs to take either ST3 (\(X_3\)) or PG3 (\(X_7\)) or DM3 (\(X_{10}\)). This means that at least one of them needs to be 1. So we can just write:

\[ X_3 + X_7 + X_{10} \geq 0 \]

Please make sure you understand how we got (or how we tested/verified) the above inequalities!

Now, we can finally write out our optimization problem in a large table:

Decision variables
\(X_1\) = Take ST1, \(X_2\) = Take ST2,
\(X_3\) = Take ST3,
\(X_4\) = Take PG1, \(X_5\) = Take PG2a,
\(X_6\) = Take PG2b, \(X_7\) = Take PG3,
\(X_8\) = Take DM1, \(X_9\) = Take DM2,
\(X_{10}\) = Take DM3		 Maximize Interest =
8\(X_1\) + 4\(X_2\) + 6\(X_3\) + 7\(X_4\) + 5\(X_5\) +
6\(X_6\) + 3\(X_7\) + 4\(X_8\) + 6\(X_9\) + 7\(X_{10}\)
Subject to
Minimum Course Requirements (= for cost savings) 10 \(X_1\) + 10 \(X_2\) + 10 \(X_3\) + 10 \(X_4\) + 10 \(X_5\) +
10 \(X_6\) + 10 \(X_7\) + 10 \(X_8\) + 10 \(X_9\) + 10 \(X_{10}\) \(=\) 40
Pre-Requisite for ST2 \(X_1 - X_2 \geq 0\)
or
1 \(X_1\) + (-1) \(X_2\) + 0 \(X_3\) + 0 \(X_4\) + 0 \(X_5\) +
0 \(X_6\) + 0 \(X_7\) + 0 \(X_8\) + 0 \(X_9\) + 0 \(X_{10}\) \(\geq\) 0
Pre-Requisite for ST3 \(X_2 - X_3 \geq 0\)
or
0 \(X_1\) + 1 \(X_2\) + -1 \(X_3\) + 0 \(X_4\) + 0 \(X_5\) +
0 \(X_6\) + 0 \(X_7\) + 0 \(X_8\) + 0 \(X_9\) + 0 \(X_{10}\) \(\geq\) 0
Pre-Requisite for PG2a \(X_4 - X_5 \geq 0\)
or
0 \(X_1\) + 0 \(X_2\) + 0 \(X_3\) + 1 \(X_4\) + -1 \(X_5\) +
0 \(X_6\) + 0 \(X_7\) + 0 \(X_8\) + 0 \(X_9\) + 0 \(X_{10}\) \(\geq\) 0
Pre-Requisite for PG2b \(X_4 - X_6 \geq 0\)
or
0 \(X_1\) + 0 \(X_2\) + 0 \(X_3\) + 1 \(X_4\) + 0 \(X_5\) +
-1 \(X_6\) + 0 \(X_7\) + 0 \(X_8\) + 0 \(X_9\) + 0 \(X_{10}\) \(\geq\) 0
Pre-Requisite for PG3
(PG2a OR PG2b)		 \((X_5 + X_6) - X_7 \geq 0\)
or
0 \(X_1\) + 0 \(X_2\) + 0 \(X_3\) + 0 \(X_4\) + 1 \(X_5\) +
1 \(X_6\) + -1 \(X_7\) + 0 \(X_8\) + 0 \(X_9\) + 0 \(X_{10}\) \(\geq\) 0
Pre-Requisite for DM2 \(X_8 - X_9 \geq 0\)
or
0 \(X_1\) + 0 \(X_2\) + 0 \(X_3\) + 0 \(X_4\) + 0 \(X_5\) +
0 \(X_6\) + 0 \(X_7\) + 1 \(X_8\) + -1 \(X_9\) + 0 \(X_{10}\) \(\geq\) 0
Pre-Requisite for DM3 \(X_9 - X_{10} \geq 0\)
or
0 \(X_1\) + 0 \(X_2\) + 0 \(X_3\) + 0 \(X_4\) + 0 \(X_5\) +
0 \(X_6\) + 0 \(X_7\) + 0 \(X_8\) + 1 \(X_9\) + -1 \(X_{10}\) \(\geq\) 0
Complete Specialization \(X_3 + X_7 + X_{10} \geq 1\)
or
0 \(X_1\) + 0 \(X_2\) + 1 \(X_3\) + 0 \(X_4\) + 0 \(X_5\) +
0 \(X_6\) + 1 \(X_7\) + 0 \(X_8\) + 0 \(X_9\) + 1 \(X_{10}\) \(\geq\) 1
Binary, Integer, Non-Negativity Constraints \(X_1\), to \(X_{10}\) all binary, integers and \(\geq 0\).

Notice that I’ve written out the inequalities into longer forms with explicit “0”s, so

\[X_1 - X_2 \geq 0\] becomes \[X_1 + (-1) X_2 + 0 X_3 + 0 X_4 + 0 X_5 + 0 X_6 + 0 X_7 + 0 X_8 + 0 X_9 + 0 X_{10} \geq 0\]

This makes it much easier to type this into code. This is the hardest part now, transfering this into code without making any mistakes!

#defining parameters
objective.fn <- c(8, 4, 6, 7, 5, 6, 3, 4, 6, 7)
const.mat <- matrix(c(rep(10,10),
                      rep(0,0), 1, -1, rep(0, 8), # ST2
                      rep(0,1), 1, -1, rep(0, 7), # ST3
                      
                      rep(0,3), 1, -1, rep(0, 5), # PG2a
                      rep(0,3), 1, 0, -1, rep(0, 4), # PG2b
                      rep(0,4), 1, 1, -1, rep(0, 3), # PG3
                      
                      rep(0,7), 1, -1, rep(0, 1), # DM2
                      rep(0,8), 1, -1, rep(0, 0), # DM3
                      
                      rep(0,2), 1, rep(0,3), 1, rep(0,2), 1 # complete specialization
                      ) , ncol=10 , byrow=TRUE) 
const.dir <- c("=", rep(">=", 8))
const.rhs <- c(40, rep(0,7), 1)

#solving model
lp.solution <- lp("max", objective.fn, const.mat, const.dir, const.rhs, 
                  binary.vec = c(1:10))
lp.solution$solution #decision variables values 
##  [1] 1 1 1 1 0 0 0 0 0 0
lp.solution
## Success: the objective function is 25

Thus, the final solution is \(X_1\), \(X_2\), \(X_3\), \(X_4\) = 1, with the rest = 0.

In order to maximize her interest while completing the degree, Natalie should choose to specialize in Statistics (taking ST1, ST2, ST3), and then also taking the first course in Programming (PG1).