How can linearize the product of decision variables in ILP?

1.3k Views Asked by At

Here, we have something like this:

$$R + (1-R)T + (1-R)(1-T)S + (1-R)(1-T)(1-S)Q = 1$$

where $R$, $T$, $S$, $Q$ are binary decision variable

How can I convert this nonlinear summation of products to linear equation in much more simple way? I mean to have less constraints to have after linearization.

1

There are 1 best solutions below

1
On BEST ANSWER

You essentially want to do circuit minimization for boolean functions, at least to begin with.

Your function can be minimized to $R + T + S + Q = 1$. I used this on-line minimizer (although it easily can be seen by inspection in this case)

Edit: Your function in the comments, which is index to first nonzero element of a binary vector $x\in\{0,1\}^n$, assuming there is a non-zero element, can be described by introducing a new binary vector $s\in\{0,1\}^n$ (picking the position of first non-zero), and the constraints $\sum_{i = 1}^{k}s_i \leq \sum_{i = 1}^{k}x_i$, $k\sum_{i=1}^k s_i \geq \sum_{i=1}^k x_i$ and $\sum_{i=1}^n s_i = 1$, for all $1\leq k\leq n$. The index is then given by $\sum_{i=1}^n is_i$.