## 3 Sensor Scheduling
### Multiple Sensors Scheduling Using Percentile Type Constraints  
[PERSON] _et al_ have proposed to reformulate problem (4) -(11) for the case of \(m\) sensors [28].  
\[\min\max_{i,t}\{a_{i}+b_{i,t}(t-y_{i,t})\}\] (17) s.t. \[\sum_{i=1}^{n}x_{i,t}\leq m,\;\forall t=1,\ldots,T, \tag{18}\] \[0\leq y_{i,t}-y_{i,t-1}\leq tx_{i,t},\;\forall i=1,\ldots,n,\; \forall t=1,\ldots,T,\] (19) \[tx_{i,t}\leq y_{i,t}\leq t,\;\forall i=1,\ldots,n,\;\forall t=1,\ldots,T,\] (20) \[y_{i,0}=0,\;\forall i=1,\ldots,n,\] (21) \[x_{i,t}\in\{0,1\},\;\forall i=1,\ldots,n,\;\forall t=1,\ldots,T,\] (22) \[y_{i,t}\in\textit{I\!R},\forall i=1,\ldots,n,\;\forall t=0, \ldots,T. \tag{23}\]  
For every site \(i\) and every time point \(t\) we can calculate penalty associated with the last time a sensor visited this site \(a_{i}+b_{i,t}(t-y_{i,t})\). Let us pick \((1-\alpha)\) % of worst cases among these \(n\times T\) penalty values. Then, instead of minimizing maximum loss we can minimize the the average taken over this \((1-\alpha)\) % percent of worst penalty values. Despite the fact that this formulation is deterministic it is equivalent to computing \((1-\alpha)\) Conditional Value-at Risk (CVaR) for a set of random outcomes having equal probabilities \(p_{i,t}=\frac{1}{nT}\).  
CVaR [29, 30] is closely related to a well-known quantitative risk measure referred to as Value-at-Risk (VaR). By definition with respect to a specified probability level \((1-\alpha)\) (in many applications the value of \((1-\alpha)\) is set rather high, e.g. 95%), the \(\alpha\)-VaR is the lowest amount \(\zeta\) such that with probability \((1-\alpha)\), the loss will not exceed \(\zeta\), whereas for continuous distributin the \(\alpha\)-CVaR is the conditional expectation of losses _above_ that amount \(\zeta\). As it can be seen, CVaR is a more conservative risk measure than VaR, which means that minimizing or restricting CVaR in optimization problems provides more robust solutions with respect to the risk of high losses (see figure 3).  
The reader can find the formal definition of CVaR for various distribution cases in [29, 30]. [PERSON] and [PERSON] [31, 32] showed that minimizing CVaR-type objective function of linear argument can be reduced to LP. In the sensors scheduling problem the loss function is introduced as  
\[L(x,y,i,t)=a_{i}+b_{i,t}(t-y_{i,t}). \tag{24}\]  
Thus the initial multiple sensors scheduling problem can be considered as the CVaR-based formulation  
\[\min_{x,y}\mathrm{CVaR}_{\alpha}\left[L(x,y,i,t)\right)]\] (25) s.t. constraints (18)-(23), \[\zeta\in I\!\!R. \tag{26}\]  
Even though the parameters \(i\) and \(t\) of the loss function (24) are deterministic by nature, the stochastic framework was applied to this model in order to compute a percentile-type measure.  
The parameters that quantify fixed and variable information losses are in many cases _uncertain_ by nature. The following mathematical programming formulations allow quantifying and restricting the risks of worst-case losses associated with the aforementioned uncertain parameters. It is made by utilizing quantitative risk measures that allow one to control the robustness of the optimal solutions. Assuming that \(a_{i}\) and \(b_{i,t}\) are random values we can formulate stochastic program utilizing the notion of CVaR.  
\[\min_{x,y,\zeta}\mathrm{CVaR}_{\alpha}a_{i}^{s}(1-x_{i,t})+b_{i,t}^{s}(t-y_{i,t})\] (27) s.t. constraints (18)-(23).  
Figure 3: Graphical representation of VaR and CVaR.  
Here we use \(S\) scenarios (\(a_{i}^{s}\) and \(b_{i,t}^{s}\), \(s=1,\ldots,S\)) sampled from the distribution of penalty coefficients.  
The mixed integer linear formulation was solved by ILOG CPLEX. The problems were also reformulated in terms of cardinality constraints and solved by AOrDa Portfolio Safeguard software package. Both solver find a good quality approximate solutions for large size problems.