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

Hi. Today we are going to implement lexicographical comparisons using ILP. Let’s begin!

Introduction

Let’s assume that we want to solve the following:

So we have two vectors of integer variables and we want to answer the question whether is less than . We define “less than” here in usual way, e.g., whether there exists for which and .

Naive implementation

We could implement this naively, e.g., perform all necessary comparisons and come up with the solution using conditions:

This is slow and inefficient. For elements in vector we have clauses and each clause contains up to conditions which sums up to conditions. We can do better.

Better implementation using hashing

We can perform faster comparison using hashes. First, let’s assume that we can operate on numbers up to and that for now . We can do the following:

OK, some black magic. Let’s untangle it.

We compare each pair of vectors’ elements. For every pair we ask whether element from vector is greater or equal than element in vector and subtract flag whether it is less or equal. This results in extended binary solution (minus one or zero or one). Next, we multiply this binary flag by some constant power of two. We want to do it in a way which allows us to come out with final solution just by checking the sign of the sum.

Let’s see a simple example for the following data:

The idea here is: for every element we want to have positive positive term when element in vector is greater than element in vector , zero term when they are equal, and negative term when element in vector is less than element in vector . We achieve this by performing two comparisons: is greater or equal, and is less or equal. In the first case (element in is greater than element in ), we get . In second case we get , in third case we get .

Next, we want to get just one number representing the whole vector comparison. Since we compare numbers from left to right (see the definition of lexicographical “less than”), we multiply numbers by consecutive powers of two starting from the greatest one so the preceding terms are not “neutralized” by the next ones. Takie this example:

Even though only first one element is lower and all the others are greater in vector than in vector , the total value is still negative, thanks to powers of two.

How do we perform other comparisons? It is pretty simple:

Longer vectors

We know how to compare vectors up to elements but how to compare longer ones? Well, the trick is: let’s do the same again.

Imagine that we have vectors with hundreds of elements. We take first elements and compare them lexicographically. We get one number which is negative, positive, or zero. The number represents relation of first elements of compared lexicographically with first elements of . We can now take next elements and compare them in the same way. Moving forward we finally get the following vector:

This is another vector representing packages of elements of compared to . We can now compare with vector of the same length.

Why does it work? Well, if first elements of are lexicographically lower than elements of , will be negative so next comparison will still work well since . If first elements are equal, so next batch of elements will have a chance to change the comparison result. If first elements are greater then which will determine the result.

We can recursively compare smaller and smaller vectors and finally end with just one number representing the solution. Finally, by comparing its sign we will be able to determine the final result.

Summary

As we can see, we are able to compare vectors much faster with hashing approach than by using naive one.

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.

In set, Not in set

We start with In set operation. For set and value we want to ask whether is in set . This is very easy because all we need to do is compare with all values from set and calculate the sum:

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

Different values count

Very similar operation is a Different values count. For multiset (e.g., set with repetitions) we want to ask how many different values does it contain. The formula is as follows:

For every variable we check whether all variables with indexes greater than are different than . Basically, we traverse multiset in some arbitrary order and for -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 and add constraint where 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.

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

We already know how to compare integer values and today we are going to extend this method to be able to compare real numbers.

Introduction

Comparing real numbers is a bit tricky. We need to remember that computers usually implement non-integer values using IEEE floating point representation. This means that they are not able to store any real number in a specified range but only some of them. What’s more, most popular format for interchanging ILP problems — MPS — allows to use only 12 digits for a value. This means that we cannot store numbers with arbitrary precision because we would not be able to solve our problems. By the way, did you know that decimal to floating-point conversion needs arbitrary precision? Working with real values is really difficult. We also need to remember that there is always a risk of having round-off error. There are solvers able to perform calculations using exact operations — for instance SCIP — but this increases the calculation cost. In fact we should work with integer numbers only to avoid problems.

Existing formula

To implement greater than we used the following formula:

Look at the right side of this inequality. We use “less or equal” operator because this is what ILP requires. We also subtract one from because this is the scale of our numbers. Imagine now that we allow and to have non-integer values, e.g., and . We get the following:

(1)  

Since is a negative number, should be true. However, in that case we get:

This means that our formula cannot be satisfied.

Solution 1

Once again we need to make an assumption about values of our variables. We already assumed that they cannot be greater than and we silently assumed that the difference of two different values can be at least one. This doesn’t hold for real values so we need to verify our assumptions.
Let’s say that we want to perform exact calculations up to five digits after the decimal point. This means that the scale of our variables is equal to . In order to compare values we need to modify formula in the following way:

Let’s now consider the situation and . We get:

(2)  

Now everything works because for we get . All other comparisons goes exactly the same way.

Solution 2

We can solve the problem using another approach. Assuming that we can multiply every variable by and perform all calculations using only formulas for integer values. When retrieving the final results we need to divide every variable by and then we get the actual value. However, this approach is a bit more difficult because we need to remember which values were multiplied and which weren’t — we don’t want to multiply binary variables because our formulas are not adjusted for that situation.

Warning

Both formulas are very dangerous. They assume we’ll never try comparing numbers which are not equal and are closer than epsilon. Otherwise we break the model.

Let’s consider this example. Set meaning that our precision is one fourth. Now let’s compare and . What we get is

(3)  

If is zero then we get which is false. However, if is one then we get .
By adding comparison (which we would like to never affect the model) we effectively break the system and solver should indicate infeasibility.

Summary

We are now able to perform calculations using real values. As stated in summary, we should avoid this as much as possible because of rounding errors, efficiency problems, and MPS file precision. However, it is possible.

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

We have already seen how to define Boolean algebra. We also know how to multiply variables or calculate division, remainder, powers, and roots. Today we are going to compare variables.

Idea

Let’s assume that we have two integer variables: and . We want to know whether is greater than and we want to store this information in variable . We do not want to enforce this constraint, we only want to know the result of the comparison.
As we will see in later parts of this series, such a knowledge will allow us to calculate more sophisticated mathematical functions, like maximum or absolute value. But today we need to start with basics.

Basics

First lets define variables:

We have two integer variables, both of them not greater than arbitrary defined number named . Since we will probably solve our models using computers, we assume that is close to some power of two. We also define constant , which we will use later. Finally, we define binary variable , which will hold the result of the comparison.

Greater than comparison

Now we are going to implement greater than operator. We want to define the following:

which means that is equal to one if and only if is greater than , otherwise is equal to zero. We can achieve this using the following constraints:

When is greater than , then is negative and must be equal to one. Otherwise we would receive which cannot happen because of the left inequality. However, when is not greater than , their difference is non-negative and has to be zero.
We use value greather than because for case when and , their difference . In that case we obtain:

Now imagine that . We get:

On the other hand, , so inequality has no solutions.

Other operators

We have define only one relational operator, but now we are able to use it to define others. That is:

Summary

We defined relational operators and now we are able to compare variables. In the next part we will see how to utilize this knowledge to calculate absolute value, maximum, and minimum. These trivial functions are in fact really powerful and we will use them many times in other operators.