# Optimization-Based Approaches to Control of Probabilistic Boolean Networks
## 4 Integer Programming Approach
### Solution Method for Problem 2-A  
In this subsection, a solution method for Problem 2-A is derived. The solution method for Problem 2-B will be explained in the last part of this subsection. As a preparation, we explain one lemma. The product of multiple binary variables such as \(\delta_{1}\delta_{2}\) can be linearized by using the following lemma [49]. **Lemma 2**. : _Suppose that binary variables \(\delta_{j}\in\{0,1\}\), \(j\in\mathcal{J}\) are given, where \(\mathcal{J}\) is some index set. Then, \(z=\prod_{j\in\mathcal{J}}\delta_{j}\) is equivalent to the following linear inequalities_  
\[\sum_{j\in\mathcal{J}}\delta_{j}-z\leq|\mathcal{J}|-1,\ \ -\sum_{j\in \mathcal{J}}\delta_{j}+|\mathcal{J}|z\leq 0,\]  
_where \(|\mathcal{J}|\) is the cardinality of \(\mathcal{J}\)._  
From Lemmas 1 and 2, we see that any Boolean function can be equivalently transformed into a pair of linear functions and linear inequalities. See [48; 49] for further details. Consider transforming Problem 2-A into an ILP problem. Using Lemma 1, \(f_{j}^{(i)}(x(k),u(k))\) in the PBN (1) can be equivalently transformed into a certain polynomial. Let \(\widehat{f}_{j}^{(i)}(x(k),u(k))\) denote the obtained polynomial. Then, consider the following system:  
\[x_{i}(k+1)=\sum_{j=1}^{l(i)}\left\{\delta_{ij}(k)\widehat{f}_{j}^{(i)}(x(k),u(k ))\right\}, \tag{8}\]where \(i=1,2,\ldots,n\) and \(\delta_{i,j}(k)\in\{0,1\}^{1}\). For \(\delta_{i,j}(k)\), we impose the following constraint:  
\[\sum_{j=1}^{l(i)}\delta_{i,j}(k)=1. \tag{9}\]  
Next, using \(c_{j}^{(i)}\) and \(\delta_{i,j}(k)\), we define  
\[L_{i} :=\left[ \begin{array}{cccc}\ln c_{1}^{(i)}&\ln c_{2}^{(i)}&\cdots &\ln c_{l(i)}^{(i)}\end{array} \right],\] \[L :=\left[ \begin{array}{cccc}L_{1}&L_{2}&\cdots&L_{n}\end{array}  \right],\] \[\delta_{i}(k) :=\left[ \begin{array}{cccc}\delta_{i,1}&\delta_{i,2}&\cdots& \delta_{i,l(i)}\end{array} \right]^{\top}\in\{0,1\}^{l(i)},\] \[\delta(k) :=\left[ \begin{array}{cccc}\delta_{1}(k)&\delta_{2}(k)&\cdots& \delta_{n}(k)\end{array} \right]^{\top}\in\{0,1\}^{l},\]  
where \(l:=\sum_{i=1}^{n}l(i)\). Then, the following lemma was obtained in [23]. **Lemma 3**. : _Problem 2-A is equivalent to the following problem._  
**Problem 2-C:**  
\[ \begin{array}{rl}\text{find}&u(k),\delta(k),&k=0,1,\ldots,N-1\\ \text{min}&\text{Cost function }(6)\\ \text{subject to}&\text{System }(8),&x(0)=x_{0},\\ &\text{Inequality constraint}\sum_{k=0}^{N-1}L\delta(k)\geq\ln \rho,\\ &\text{Equality constraint }(9).\end{array} \]  
The outline of the proof is explained as follows. By deciding \(\delta(k)\), Boolean functions at each time are uniquely determined. Then, we can obtain \(\ln\pi_{j}(k)=L\delta(k)\). That is, using the logarithm of the probability, \(\pi_{j}(k)\) can be expressed by a linear form with respect to \(\delta(k)\). Hence, we can obtain  
\[\ln\pi_{j}(0,N-1)=\sum_{k=0}^{N-1}\ln\pi_{j}(k)=\sum_{k=0}^{N-1}L\delta(k).\]  
Thus, Problem 2-A is equivalent to Problem 2-C.  
We consider further rewriting Problem 2-C. Since the system (8) is a polynomial system, the system (8) can be equivalently transformed into a linear system by using Lemma 2. Hence, the system (8) can be transformed into the following system:  
\[\left\{ \begin{array}{l}x(k+1)=Ax(k)+B_{1}u(k)+B_{2}\delta(k)+B_{3}z(k),\\ Cx(k)+D_{1}u(k)+D_{2}\delta(k)+D_{3}z(k)\leq E,\end{array} \right. \tag{10}\]  
where \(z(k)\in\{0,1\}^{p}\) is an auxiliary variable, and the dimension \(p\) can be determined from the number of the product of binary variables. For simplicity of notation, we define \(B:=\left[ \begin{array}{cccc}B_{1}&B_{2}&B_{3}\end{array} \right]\), \(v(k):=\left[ \begin{array}{cccc}u^{\top}(k)&\delta^{\top}(k)&z^{\top}(k)\end{array}  \right]^{\top}\). In addition, under \(x(0)=x_{0}\in\{0,1\}^{n}\) and \(v(k)\in\{0,1\}^{m+l+p}\), \(x(k)\) becomes a binary variable automatically. Hence, we set \(x(k)\in\mathcal{R}^{n}\), \(k\geq 1\). We present a simple example. **Example 6**. : _Consider the PBN in Example 5 again.