From my previous questions, I have a variable : $Q$, which is function of a discrete known vector, $P$ and a binary variable $x$ : $Q=f(P,x)$.
- I know, we can linearize the products of (a) two / multiple binary variables (b) binary and a continuous variable as described in this question
- I'm also aware that its difficult to formulate a linear way of separating 2 continuous variables as described in this question
But in my case, the variable $Q$ is made up of a known parameter and a discrete variable. Thus, how to linearize the system?
From the previous answer: For a directed acyclic graph with nodes $N=\{0,1,\dots,n+1\}$ and arcs $(i,j)$ for $0 \le i < j \le n+1$. A binary decision variable $x_{i,j}$ is declared, which shows whether $y_i=y_j=1$ and $y_{i+1}=\dots=y_{j-1}=0$. It uses the upper and lower limits : $L_i$ and $U_i$ on $Q_i$. Following linear equations were to be imposed: \begin{align} y_i &= 1 &&\text{for $i\in\{0,n+1\}$} \tag1 \\ \sum_{j=i+1}^{n+1} x_{i,j} &= y_i &&\text{for $i\in\{0,\dots,n\}$} \tag2 \\ \sum_{j=0}^{i-1} x_{j,i} &= y_i &&\text{for $i\in\{1,\dots,n+1\}$} \tag3 \\ L_i(1-y_i) \le Q_i &\le U_i(1-y_i) &&\text{for $i\in \{1,\dots,n\}$} \tag4 \\ Q_k &= \sum_{(i,j): i < k < j} P_{k-i} x_{i,j} &&\text{for $k\in \{1,\dots,n\}$} \tag5 \end{align}
Now, let us have a continuous variable $T_k$ for $k \in \ {1,\dots, n } $. This variable is multiplied to the variable used previously as : $Q_k.T_k$.
I tried linearizing this with the following approach. However, my problem is integer infeasible.
First, let me put the full equations as per above mentioned equations $(1) to (5)$ from previous answer:
Based on this, following is the different set of equations (which are changed due to multiplied $T_k$ to $Q_k$):
\begin{equation} 0 \le Q_{1}.T_{1} \le 8.T_{1}.(1-y_{1}) \\ 0 \le Q_{2}.T_{2} \le 8.T_{2}.(1-y_{2}) \\ 0 \le Q_{3}.T_{3} \le 8.T_{3}.(1-y_{3}) \\ 0 \le Q_{4}.T_{4} \le 8.T_{4}.(1-y_{4}) \\ 0 \le Q_{5}.T_{5} \le 8.T_{5}.(1-y_{5}) \\ 0 \le Q_{6}.T_{6} \le 8.T_{6}.(1-y_{6}) \\ Q_{1}.T_{1} = T_{1}.[8x_{0,2} + 8x_{0,3} + 8x_{0,4} + 8x_{0,5} + 8x_{0,6} + 8x_{0,7}] \\ Q_{2}.T_{2} = T_{2}[5x_{0,3} + 5x_{0,4} + 5x_{0,5} + 5x_{0,6} + 5x_{0,7} + 8x_{1,3} + 8x_{1,4} + 8x_{1,5} + 8x_{1,6} + 8x_{1,7}] \\ Q_{3}.T_{3} = T_{3}[6x_{0,4} + 6x_{0,5} + 6x_{0,6} + 6x_{0,7} + 5x_{1,4} + 5x_{1,5} + 5x_{1,6} + 5x_{1,7} + 8x_{2,4} + 8x_{2,5} + 8x_{2,6} + 8x_{2,7}] \\ Q_{4}.T_{4} = T_{4}[x_{0,5} + x_{0,6} + x_{0,7} + 6x_{1,5} + 6x_{1,6} + 6x_{1,7} + 5x_{2,5} + 5x_{2,6} + 5x_{2,7} + 8x_{3,5} + 8x_{3,6} + 8x_{3,7}] \\ Q_{5}.T_{5} = T_{5}[2x_{0,6} + 2x_{0,7} + x_{1,6} + x_{1,7} + 6x_{2,6} + 6x_{2,7} + 5x_{3,6} + 5x_{3,7} + 8x_{4,6} + 8x_{4,7}] \\ Q_{6}.T_{6} = T_{6}[3x_{0,7} + 2x_{1,7} + x_{2,7} + 6x_{3,7} + 5x_{4,7} + 8x_{5,7}] \end{equation}
In above equations, we can see that $T_k.y_k$ and $T_k.x_{i,j}$ are present. Since, these are pairs of continuous and binary variables, These are linearized as follows:
From $1^{st}$ to $6^{th}$ equations:
\begin{equation} 0 \le Q_{k}.T_{k} \le 8.T_{k}.(1-y_{k}) \end{equation} Above is written as follows:
\begin{equation} 0 \le Z_{k} \le 8.T_{k} - 8TY_{k} \\ T_{k} - UL(T)(1-y_k) \le TY_{k} \le T_{k}-LL(T)(1-y_k) \\ LL(T)y_k \le UL(T)y_k\\ \end{equation}
where , $Z_{k} = T_{K}.Q_{K}$ , $TY_{k}$ is an assumed new variable for product of $T_{k}$ and $y_K$. $LL(T)$ and $UL(T)$ are lower and upper limits (which are known) on $T_k$.
Next, the remained equations ($7^{th}$ to $12^{th}$) are as follows:
\begin{equation} Z_{1} = T_{1}8\sum_{i=2}^{7}x_{0,i}\\ Z_{2} = T_{2} (5\sum_{i=3}^{7}x_{0,i} + 8\sum_{i=3}^{7}x_{1,i})\\ Z_{3} = T_{3}(6\sum_{i=4}^{7}x_{0,i} + 5\sum_{i=3}^{7}x_{1,i} + 8\sum_{i=3}^{7}x_{2,i})\\ Z_{4} = T_{4}(\sum_{i=5}^{7}x_{0,i} + 6\sum_{i=5}^{7}x_{1,i} + 5\sum_{i=5}^{7}x_{2,i} + 8\sum_{i=5}^{7}x_{3,i})\\ Z_{5} = T_{5}(2\sum_{i=6}^{7}x_{0,i} + 1\sum_{i=6}^{7}x_{1,i} + 6\sum_{i=6}^{7}x_{2,i} + 5\sum_{i=6}^{7}x_{3,i} + 8\sum_{i=6}^{7}x_{4,i})\\ Z_{6} = T_{6}(3\sum_{i=7}^{7}x_{0,i} + 2\sum_{i=7}^{7}x_{1,i} + 1\sum_{i=7}^{7}x_{2,i} + 6\sum_{i=7}^{7}x_{3,i} + 5\sum_{i=7}^{7}x_{4,i}+ 8\sum_{i=7}^{7}x_{5,i}) \end{equation}
In each equation above, for every $Z_k$, the pairs of $T_k$ and corresponding $x_{i,j}$ is linearized by assuming them as another new variable as ZZ(k,i,j).
Despite the procedure followed above, I get an error of 'the equations are not feasible'.
Can you please let me know, where is the problem? I cannot find it.
Following strategy works fine :
Define a directed acyclic graph with nodes $N=\{0,1,\dots,n+1\}$ and arcs $(i,j)$ for $0 \le i < j \le n+1$. Let binary decision variable $x_{i,j}$ indicate whether $y_i=y_j=1$ and $y_{i+1}=\dots=y_{j-1}=0$. Let $L_i$ and $U_i$ be constant lower and upper bounds on $Q_i$.Impose linear constraints \begin{align} y_i &= 1 &&\text{for $i\in\{0,n+1\}$} \tag1 \\ \sum_{j=i+1}^{n+1} x_{i,j} &= y_i &&\text{for $i\in\{0,\dots,n\}$} \tag2 \\ \sum_{j=0}^{i-1} x_{j,i} &= y_i &&\text{for $i\in\{1,\dots,n+1\}$} \tag3 \\ \end{align}
Now , if $T_k$ comes into picture, add following :
\begin{align} LL(T) x_{i,j} &\le z_{i,j,k} \le UL(T) x_{i,j} &&\text{for all $i,j$ and $k\in\{1,2,...,n\}$} \tag4 \\ (0 - UL(T))(1 - x_{i,j}) &\le z_{i,j,k} - T_k \le (0 - LL(T))(1 - x_{i,j}) &&\text{for all $i,j$ and $k\in\{1,2,...,n\}$} \tag5 \\ zz_{i,j,k} &= \sum_{(i,j):i<k<j}P_{k-i}z_{i,j,k} \tag6 \end{align}
(The above answer is extension of solution provided by @RobPratt . The Link is : Previous answer)