# Optimization-Based Approaches to Control of Probabilistic Boolean Networks
## 4 Integer Programming Approach
### Problem Formulation  
First, preparations are given. Suppose that for PBN (1), \(\tilde{j}(i,k)\in\{1,2,\ldots,l(i)\}\) is given for fixed \(i\in\{1,2,\ldots,n\}\) and \(k\in\{0,1,\ldots\}\). Then, we define  
\[\pi_{\tilde{j}}(k):=\prod_{i=1}^{n}c_{\tilde{j}(i,k)}^{(i)}.\]  
The parameter \(\pi_{\tilde{j}}(k)\) implies the probability that the Boolean functions \(f_{\tilde{j}(1,k)}^{(1)}\), \(f_{\tilde{j}(2,k)}^{(2)},\ldots,f_{\tilde{j}(n,k)}^{(n)}\) are selected at time \(k\). Furthermore, we define  
\[\pi_{\tilde{j}}(k_{1},k_{2}):=\prod_{q=k_{1}}^{k_{2}}\pi_{\tilde{j}}(q).\]  
The parameter \(\pi_{\tilde{j}}(k_{1},k_{2})\) implies the probability that certain Boolean functions are selected in the time interval \([k_{1},k_{2}]\). **Example 4**. : _Consider the PBN in Example 2 again. Suppose \(\tilde{j}(1,0)=1\), \(\tilde{j}(2,0)=1\), and \(\tilde{j}(3,0)=2\). In other words, \(f_{1}^{(1)}\), \(f_{1}^{(2)}\), \(f_{2}^{(3)}\) are given as a Boolean function at time \(0\). Then, we can obtain_  
\[\pi_{\tilde{j}}(0)=c_{1}^{(1)}\cdot c_{1}^{(2)}\cdot c_{2}^{(3)}=0.8\cdot 1 \cdot 0.3=0.24.\]  
_Furthermore, suppose that \(\tilde{j}(1,1)=2\), \(\tilde{j}(2,1)=1\), \(\tilde{j}(3,1)=1\)\(\tilde{j}(1,2)=1\), \(\tilde{j}(2,2)=1\), and \(\tilde{j}(3,2)=1\). Then, we can obtain_  
\[\pi_{\tilde{j}}(1) = 0.2\cdot 1\cdot 0.7=0.14,\] \[\pi_{\tilde{j}}(2) = 0.8\cdot 1\cdot 0.7=0.56,\] \[\pi_{\tilde{j}}(0,2) = \pi_{\tilde{j}}(0)\cdot\pi_{\tilde{j}}(1)\cdot\pi_{\tilde{j}}(2) =0.018816.\]  
Under these preparations, two problems (i.e., the optimal control problem and the performance evaluation problem) are formulated. First, the optimal control problem is formulated as follows. **Problem 2**. : _Suppose that, for PBN (1), the initial state \(x(0)=x_{0}\), \(\rho\) satisfying \(0\leq\rho\leq 1\), the control time \(N\), and the weighting vectors \(Q,Q_{f}\in\mathcal{R}^{1\times n}\), \(R\in\mathcal{R}^{1\times m}\) whose element is a non-negative real number are given. Then, solve the following two problems._  
**Problem 2-A**: _Find a control input sequence \(u(0)\), \(u(1)\),..., \(u(N-1)\) minimizing the lower bound of the cost function_  
\[J=\sum_{k=0}^{N-1}\left\{Qx(k)+Ru(k)\right\}+Q_{f}x(N) \tag{6}\]  
_satisfying the following constraint_  
\[\pi_{j}(0,N-1)\geq\rho. \tag{7}\]  
**Problem 2-B**: _Apply the control input sequence obtained in Problem 2-A to the PBN. Then, find an upper bound of the cost function (6)._  
Let \(\overline{J}_{s}\) and \(\underline{J}_{s}\) denote the obtained upper and lower bounds, respectively. In a similar way to Problem 1, a linear function with respect to \(x\) and \(u\) is considered as a cost function. Using the target value of the state (the offset vector) \(x_{d}\in\{0,1\}^{n}\), \(x(i)\) may be replaced to \(\hat{x}(i):=x(i)-x_{d}\). Then, the cost function (6) must be changed to \(J=\sum_{i=0}^{N-1}\left\{|Qx(i)|+Ru(i)\right\}+|Q_{f}\hat{x}(N)|\). Furthermore, by the inequality constraint (7), combinations of Boolean functions selected with the low probability can be excluded. Each element of the control input sequence obtained solving Problem 2 is in general different. In gene regulatory networks, it is difficult to implement such control input sequence. In this case, we must impose constraints for control input sequences. For example, one of the simple methods is that the control input is given by always 1 (active) or 0 (inactive). That is, Problem 2-A is modified as follows: find \(u_{0}(=u(0)=u(1)=\cdots=u(N-1))\) minimizing the lower bound of the cost function (6) under the constraint (7). We present a simple example. **Example 5**: _Consider the PBN with a single control input. Boolean functions and probabilities are given by_  
\[f^{(1)} = \left\{ \begin{array}{l}f^{(1)}_{1}=x_{3}(k)\wedge\
eg u(k),\ \ c^{(1)}_{1}=0.8,\\ f^{(1)}_{2}=\
eg x_{3}(k)\wedge\
eg u(k),\ \ c^{(1)}_{2}=0.2,\end{array} \right.\] \[f^{(2)} = f^{(2)}_{1}=x_{1}(k)\wedge\
eg x_{3}(k),\ \ c^{(2)}_{1}=1.0,\] \[f^{(3)} = \left\{