This is the fifteenth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Today we are going to use comparisons to implement few basic set operations. Let’s go.

Table of Contents

In set, Not in set

We start with In set operation. For set $x = \{x_1, x_2, \ldots, x_n \}$ and value $v$ we want to ask whether $v$ is in set $x$ . This is very easy because all we need to do is compare $v$ with all values from set and calculate the sum:

$\begin{gather*} \displaystyle\mathop{\forall}_{i=1}^{n} b_i = x_i \stackrel{?}{=} v \\ b = \sum_{i=1}^{n} b_i \stackrel{?}{\ge} 1 \end{gather*}$

For every value we calculate variable $b_i$ which is true when $x_i$ is equal to $v$ . Next, we sum all values and check whether the sum is positive. If it is true then $b$ is true which means that $v$ is in set $x$ .
For operation Not in set we do almost the same. The only difference is in comparing the sum with $0$ .

Different values count

Very similar operation is a Different values count. For multiset (e.g., set with repetitions) $x = \{x_1, x_2, \ldots, x_n \}$ we want to ask how many different values does it contain. The formula is as follows:

$\begin{gather*} \displaystyle\mathop{\forall}_{i=1}^{n} d_i = \displaystyle\mathop{\wedge} _{j=i+1}^{n} x_i \stackrel{?}{\neq} x_j \\ d = \sum_{i=1}^{n} d_i \end{gather*}$

For every variable $x_i$ we check whether all variables with indexes greater than $i$ are different than $x_i$ . Basically, we traverse multiset $x$ in some arbitrary order and for $i$ -th value we check whether all remaining values are different.

All different

We can use previous formula to make sure that all values in mulitset are different (so the multiset is in fact set). To achieve that we need to calculate different values count $d$ and add constraint $d = n$ where $n$ is a number of variables in a multiset.

Summary

Today we implemented useful set operations. Next time we are going to utilize all ILP knowledge to solve real problem — we will be solving a simple cube riddle.