SOS – Random IT Utensils https://blog.adamfurmanek.pl IT, operating systems, maths, and more. Fri, 13 Nov 2020 18:42:58 +0000 en-US hourly 1 https://wordpress.org/?v=6.6.2 ILP Part 34 — Special Ordered Set Type 1 and 2 https://blog.adamfurmanek.pl/2016/12/03/ilp-part-34/ https://blog.adamfurmanek.pl/2016/12/03/ilp-part-34/#comments Sat, 03 Dec 2016 09:00:25 +0000 https://blog.adamfurmanek.pl/?p=1901 Continue reading ILP Part 34 — Special Ordered Set Type 1 and 2]]>

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

In the next part of ILP series we will implement Special ordered sets. These two constraints are pretty simple in their idea, Special ordered set of type 1 (SOS1) is used when we want to constraint that at most one of the variable has non-zero value. Special ordered set of type 2 (SOS2) adds two constraints: at most two variables can be non-zero, and if it is the case, these variables must be consecutive in their ordering. So set [0,0,1,1,0] is SOS2, whereas set [0,1,0,1,0] is not (since non-zero variables do not stand next to each other).

Let’s begin with SOS1.

Special ordered set of type 1

We have the following variables:

    \begin{gather*} a_0, a_1, \ldots, a_n \in \mathbb{R} \\ A = \{a_0, \ldots, a_n\} \end{gather*}

For each index we create another binary variable:

    \begin{gather*} b_0, b_1, \ldots, b_n \in \{0, 1 \} \end{gather*}

We demand that at most one binary is non-zero:

    \begin{gather*} \displaystyle\mathop{\sum}_{0 \le i \le n} b_i \le 1 \end{gather*}

And we specify constraint which will allow matching variable to take non-zero value:

    \begin{gather*} \displaystyle\mathop{\forall}_{0 \le i \le n} -b_iK \le a_i \le b_iK \end{gather*}

Where K is maximum integer value which our solver supports.

How does it work? There can be at most one non-zero binary flag, and only for that flag the respective variable is allowed to take non-zero value (because for all the other flags constraint will have zero on both sides). However, non-zero flag does not require matching variable to be non-zero, but this does not break definition of SOS1.

Special ordered set of type 2

Now we want to add constraint that at most two variables are non-zero, and if there are two non-zero variables, they are next to each other. Using the same variables as before:

    \begin{gather*} a_0, a_1, \ldots, a_n \in \mathbb{R} \\ A = \{a_0, \ldots, a_n\} \end{gather*}

We create binary variables in the same way and still require that at most one binary is non-zero:

    \begin{gather*} b_0, b_1, \ldots, b_n \in \{0, 1 \} \\ \displaystyle\mathop{\sum}_{0 \le i \le n} b_i \le 1 \end{gather*}

This time for each variable we take two binary flags into the constraint:

    \begin{gather*} \displaystyle\mathop{\forall}_{0 \le i \le n} -(b_i + b_{i+1}) K \le a_i \le (b_i + b_{i+1})K \end{gather*}

How does it work? Let’s assume that all b_{i} are zeroes, this means that we have lots of constraints of the form -(0+0)K \le a_i \le (0+0)K which makes sure that all a_i are zeroes. However, imagine that b_i is true. This time we have two interesting constraints:

    \begin{gather*} -(b_{i-1} + b_{i}) K \le a_{i-1} \le (b_{i-1} + b_{i})K \\ -K \le a_{i-1} \le K \end{gather*}

and

    \begin{gather*} -(b_i + b_{i+1}) K \le a_i \le (b_i + b_{i+1})K\\ -K \le a_i \le K \end{gather*}

So a_{i-1} and a_i are allowed to be non-zero, so at most two variables can be non-zero.

Summary

Special ordered sets looks easy but they are very useful. In next part we will see how to approximate any 1D or 2D function using SOS2.

]]> https://blog.adamfurmanek.pl/2016/12/03/ilp-part-34/feed/ 1