key: cord-0450128-agd9k3uk
authors: Niazi, Muhammad Umar B.; Kibangou, Alain; Canudas-de-Wit, Carlos; Nikitin, Denis; Tumash, Liudmila; Bliman, Pierre-Alexandre
title: Effective Testing Policies for Controlling an Epidemic Outbreak
date: 2021-09-26
journal: nan
DOI: nan
sha: f442f92d0f5b3098d5d6437770c42c45ac1894a2
doc_id: 450128
cord_uid: agd9k3uk

Testing is a crucial control mechanism for an epidemic outbreak because it enables the health authority to detect and isolate the infected cases, thereby limiting the disease transmission to susceptible people, when no effective treatment or vaccine is available. In this paper, an epidemic model that incorporates the testing rate as a control input is presented. The proposed model distinguishes between the undetected infected and the detected infected cases with the latter assumed to be isolated from the disease spreading process in the population. Two testing policies, effective during the onset of an epidemic when no treatment or vaccine is available, are devised: (i) best-effort strategy for testing (BEST) and (ii) constant optimal strategy for testing (COST). The BEST is a suppression policy that provides a lower bound on the testing rate to stop the growth of the epidemic. The COST is a mitigation policy that minimizes the peak of the epidemic by providing a constant, optimal allocation of tests in a certain time interval when the total stockpile of tests is limited. Both testing policies are evaluated by their impact on the number of active intensive care unit (ICU) cases and the cumulative number of deaths due to COVID-19 in France.

On March 16, 2020, five days after the World Health Organization (WHO) declared COVID-19 to be a pandemic, the Director-General of WHO, Dr. T. A. Ghebreyesus, ended his media briefing with a simple message to all countries: "Test, test, test". This is because testing is well-known to be a crucial control mechanism for epidemics when no effective treatment or vaccine is available [1] . It limits the spread of disease to the susceptible population by enabling the health authority to detect and isolate the infected people.

Recently, several models and techniques have been developed to study testing policies for epidemic control. Similar to a resource allocation problem in epidemic control [2] , the optimal test allocation problem is posed in [3] as a wellknown sensor selection problem in control theory. A similar problem studied in [4] considers the specificity and sensitivity of tests and solves the optimal test allocation problem as a welfare maximization problem. However, the underlying M.U.B. Niazi, C. Canudas-de-Wit, A. Kibangou, D. Nikitin, and L. Tumash are with Université Grenoble Alpes, Inria, CNRS, Grenoble INP, GIPSA-Lab, 38000 Grenoble, France. Emails in the respective order: muhammad-umar-b.niazi@gipsa-lab.fr, carlos.canudas-de-wit@gipsa-lab.fr, alain.kibangou@univ-grenoble-alpes.fr, denis.nikitin@gipsa-lab.fr, liudmila.tumash@gipsa-lab.fr P.-A. Bliman is with Sorbonne Université, Université Paris-Diderot SPC, Inria, CNRS, Laboratoire Jacques-Louis Lions,équipe Mamba, 75005 Paris, France. Email: pierre-alexandre.bliman@inria.fr This work is partially supported by European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (ERCAdG no. 694209, Scale-FreeBack, website: http://scale-freeback.eu/) and by Inria, France, in the framework of the Inria Mission Covid-19 (Project HealthyMobility). assumption in these papers is the availability of information portfolios of all the people in a society, thus limiting their applicability to larger scales. Another line of research studies testing policies from an economic perspective, for instance, [5] and [6] aim to find an optimal trade-off between the economic activity and epidemic mitigation. In [7] , an optimal trade-off between testing effort and lockdown intervention is computed numerically under the constraint of limited Intensive Care Units (ICU). However, none of these papers provide a control-theoretic perspective of testing, namely how testing can be used to change the dynamics of an epidemic?

In this paper, we study testing policies in terms of testing rate, i.e., number of tests performed per day, with the aim to suppress and/or mitigate an epidemic outbreak. We introduce a new model with the acronym SIDUR-susceptible (S), undetected infected (I), detected infected (D), unidentified recovered (U), and identified removed (R)-that has the testing rate as a control input. The influence of the control input in the SIDUR model is directly linked with the testing specificity, which determines the probability of detecting an infected person by a test. Similar to [8] - [10] , we distinguish the undetected infected from the detected infected population. Only the undetected infected people participate in the disease transmission, and the detected infected are assumed to be either quarantined and/or hospitalized. Moreover, the unidentified recovered people, who were infected and then recovered naturally without getting detected, are distinguished from the identified removed people, who were infected and then recovered or died in a hospital or quarantine after getting detected.

We propose two testing policies for epidemic control: (1) Best-effort strategy for testing (BEST) and (2) Constant optimal strategy for testing (COST). The BEST is a suppression policy for an epidemic that computes the minimum testing rate to immediately stop the growth of the epidemic when applied from a certain day onward. The COST is a mitigation policy for an epidemic that reduces, but not necessarily stops, the growth of the epidemic and is meaningful only when the total stockpile of tests is limited. It provides the constant optimal testing rate that must be utilized until the day when the stockpile of tests finishes. We evaluate both testing policies by predicting their impact on the number of active intensive care unit (ICU) cases and the cumulative number of deaths due to COVID-19 in France. Both testing policies are effective at the beginning of an epidemic outbreak when the treatments or vaccines against the disease are not available. This paper focuses solely on the SIDUR model design and testing policies, and excludes model estimation and validation, which is reported in the detailed version [11] . The paper is organized as follows: Section II presents the SIDUR model, identifies the measured outputs in relation to the model states, and provides a partial solution of the model. Then, in Section III and IV, we propose the BEST and COST policies, and evaluate them for the case of COVID-19 outbreak in France from February to July 2020. Finally, Section V presents the concluding remarks.

We introduce a five-compartment model, SIDUR, with the purpose of devising and evaluating testing policies. We consider the timescale of days and, at time t ∈ R ≥0 , each compartment is characterized by a single state representing its population, where 

(ii) Only the undetected infected x I (t) are responsible for the disease transmission to the susceptible people x S (t). (iii) All the deaths occurring due to the epidemic are known, reported, and included in the identified removed x R (t). (iv) After recovery, people acquire permanent immunity and are not infected again.

Let β ≥ 0 be the infection rate defined as the product of the contact rate by the probability of disease transmission during a contact between a susceptible and an infected persons. The value of β not only depends on the disease biology but is also influenced by the implementation of nonpharmaceutical interventions (NPI) such as social distancing, lockdown, travel restrictions, and preventive measures. Thus, β = β(t) is a time-varying parameter that depends on the extent to which the NPIs are implemented. Depending on the time periods when different NPI policies are implemented, we assume β to be piece-wise constant.

Let x T (t) be the testable population defined as

where θ ∈ [0, 1] is the testing specificity parameter. Note that the infected population 

Thus, if θ = 1, the probability of detection is equal to one, and if θ = 0, the probability of detection is the lowest. Depending on the testing policy, testing specificity, and the level of contact tracing, we consider θ = θ(t) to be time-varying and piecewise constant. Finally, let γ > 0 and ρ > 0 be the recovery rate and removal rate, respectively, which are assumed to be constants that depend on the disease biology. The inverse of the recovery rate 1/γ is defined to be the average recovery time after which a typical undetected infected person naturally recovers, whereas the inverse of the removal rate 1/ρ is defined to be the average removal time after which a typical detected infected person recovers or dies.

The SIDUR model, depicted in Fig. 1 , is given bẏ

where u(t) ≥ 0 is the testing rate. Notice that the model (1) fulfils Assumption 1 for any u(t) ≥ 0.

The testing rate u(t), which is defined to be the number of tests performed per day, is the control input in SIDUR model. In order to diagnose the infected people at time t, the tests are allocated to a proportion of the testable population x T (t). The testing specificity parameter θ allows for the adjustment of the testable population to accommodate for the detection rate of tests.

The data reported by the health authorities are chosen as the measured outputs of the SIDUR model. They are five measurements, related directly to the states as follows:

• Cumulative number of detected people

(2)

• Cumulative number of removed people

• Number of positively tested people per day

Let the number of active ICU patients (or ICU beds occupied) be denoted as B(t) and the cumulative number of deaths (or extinct cases) be denoted E(t). Note that B(t) and E(t) are also measured and reported, and are functions of the number of active infected cases and the cumulative number of infected cases, respectively.

• Number of active ICU cases

where

is the number of active infected cases, ψ −1 is the average time period which a typical infected ICU case takes from getting infected to being admitted to the ICU, and the function g is to be chosen such that y 4 (t) = B(t) fits the data. • Cumulative number of deaths

where

is the cumulative number of infected cases, φ −1 is the average time period which a typical non-surviving case takes from getting infected to death, and the function h is to be chosen such that y 5 (t) = E(t) fits the data.

An important quantity to determine the epidemic potential at the onset of a disease is the basic reproduction number R 0 . In the later stages, however, the effective reproduction number R(t) is more suitable [12] , [13] to predict the spread of the disease. The R(t) for the SIDUR model is defined as the ratio of the number of newly infected people over the number of newly detected and recovered people at time t, i.e.,

If R(t) < 1, then more people are being detected and/or recovering than the people being infected at time t, implying that x I (t) will decrease in the near future. If R(t) > 1, then more people are being infected than the people being detected and recovering at time t, implying that x I (t) will increase in the near future. The basic reproduction number R 0 = R(0) and is given by

This expression of R 0 can also be obtained by following the methodology of [14] .

and

Proposition 1. Consider the infection time ξ, then:

whose solution is given by (9) . Then, from (1d), we obtain dx U dξ = γ whose solution is given by (10) .

The testing specificity parameter θ can be close to one under different circumstances. For instance, if the testing is assisted with efficient contact tracing, then θ ≈ 1. However, if the tests are performed only on people with apparent symptoms of the disease, then θ ≈ 1 also. If we assume a scenario unlike those mentioned above, then θ ≪ 1. In addition, if we assume that x S (t) + x U (t) ≈ N , then we can obtain an approximate solution of x I (ξ) by assuming 

where x 0 I = x I (0). Proof. From (1b) and (9), we have

where we assumed x T = (1 − θ)N . Integrating both sides from 0 to ξ gives (11).

Suppose that the tests can be produced and supplied easily, and there is no upper bound on the total stockpile of tests. Moreover, we say that, at any time t, the epidemic is spreading if x I (t) is increasing, i.e., R(t) > 1. On the other hand, we say that the epidemic is non-spreading if x I (t) is not increasing, i.e., R(t) ≤ 1. Then, the best effort strategy for testing (BEST) at any given time t * is the minimum number of tests to be performed per day from time t * onward such that the epidemic switches from spreading to nonspreading at t * . In other words, the BEST policy provides the smallest lower bound on the testing rate that is sufficient to change, at a given time t * , the course of the epidemic from spreading to non-spreading. We remark that the BEST policy is meaningful only when the epidemic is spreading.

Define a function

where, by definition, for any scalar z, |z| + = z if z > 0 and |z| + = 0 otherwise.

[t * , t 1 ), for some t * < t 1 . Then, the BEST policy at time t * is given by

Proof. In order to prove that c * (t * ) for t ∈ [t * , t 1 ) is the BEST at t * , we show the following: (i) If u(t) > c * (t) (resp., u(t) ≥ c * (t)) for any t ∈ [t * , t 1 ), then x I is decreasing (resp., non-increasing) on [t * , t 1 ). (ii) If u(t) > c * (t * ) (resp., u(t) ≥ c * (t * )) for any t ∈ [t * , t 1 ), then x I is decreasing (resp., non-increasing) on [t * , t 1 ). Assume that u(t) > c * (t) on [t * , t 1 ). Then, Φ(t) := β(t) xS(t) N − u(t) xT(t) − γ < 0 which implies that x I is decreasing becauseẋ I (t) = Φ(t)x I (t) almost everywhere. If only the weaker assumption u(t) ≥ c * (t) on [t * , t 1 ) is fulfilled, then, by using the continuity of the solutions of ODE with respect to perturbations of the right-hand side, one gets that x I is non-increasing.

Assume now that u(t) > c * (t * ) on [t * , t 1 ), where c * (t * ) is constant. Then, by continuity, u(t) > c * (t) on a certain interval [t * , t 2 ), for some t 2 ∈ (t * , t 1 ]. As a consequence of the result (i) shown previously, x I decreases on [t * , t 2 ). Moreover, assume that t 2 is the maximal point in (t * , t 1 ] having this property. In order to show that t 2 = t 1 , it is sufficient to show that u(t 2 ) > c * (t 2 ), otherwise one may consider a larger value for t 2 which will lead to a contradiction with the fact that it is maximal. Since x I decreases on [t * , t 2 ) and θ is non decreasing, we can conclude that x T also decreases on this interval. On the other hand, since x S is always decreasing and β is non increasing, one can conclude that c * (t) also decreases on [t * , t 2 ). This is obtained by upper bounding c * (t). Thus, one has c * (t * ) > c * (t), which implies that that u(t 2 ) > c * (t 2 ). Therefore, as t 2 = t 1 , we have established that x I decreases on the whole interval [t * , t 1 ).

For the case where u(t) ≥ c * (t * ), we can use the same argument of continuity of the trajectories. From the previous results, one deduces that the BEST policy is given by c * (t * ) and the testing rate

, then one can show that the epidemic goes on spreading in the interval [t * , t 1 ). Hence, u(t) = c * (t * ) is the BEST policy at t * .

Remark 1. Requiring that β must not increase and θ must not decrease in the interval [t * , t 1 ) for some t 1 > t * is necessary for the BEST policy. It is thus important to keep the external conditions that determine the values of β and θ either constant or such that β decreases (e.g., through the implementation of lockdown) and/or θ increases (e.g., through efficient contact tracing). On the other hand, the case where β decreases and/or θ increases at some time t 1 > t * has the effect of speeding up the suppression of the epidemic under BEST policy.

Given the COVID-19 data of France, we first estimate the parameters of the SIDUR model by fitting the model outputs (2), (3), and (4) with the corresponding data (see [11] for details). Then, we compute c * (t * ) for different values of t * from January 24 to March 15. Figure 2 shows the testing rate u(t * ) required by the BEST policy if it is implemented from day k = ⌊t * ⌋, where ⌊·⌋ denotes the floor function, and the corresponding value of the peak of undetected infected x I (t). It can be seen that the required testing rate increases exponentially if the BEST policy is not implemented early on in the epidemic phase. This is because the number of undetected infected x I (t) becomes very large, which increases the difficulty of controlling the epidemic.

Let us now consider a scenario where BEST is implemented on March 01, 2020. Then, Figure 3 depicts the evolution of undetected infected x I (t) when u(t) is given by the data on the number of tests per day in France and when u(t) is given by BEST policy. To evaluate BEST, we use u(t) as given by the data until February 29 and then by the BEST policy from March 01 onward. In the actual COVID-19 case of France, our model predicted the peak of the undetected infected x I (t) to be about 6 million. However, if the BEST policy was implemented, the peak of x I (t) could have been reduced to 363, 169 with the testing rate c * ≈ 147, 000, which is quite feasible. The impact of the BEST policy on the number of active ICU cases B(t) and the cumulative number of deaths E(t) is evaluated after fitting the model outputs (5) and (6) with the data in the actual testing scenario. The results are illustrated in Figure 4 and 5. From the figures, we observe that the peak of the number of active ICU patients could have been reduced by 34.71% and the number of deaths could have been reduced by 74.45% if the BEST policy was implemented.

Suppose that the total stockpile of tests is limited and given by r max ∈ N, where N denotes the set of natural numbers. Then, the problem is to find the optimal testing rate that minimizes the epidemic peak, i.e., the peak value of the undetected infected population x I (t). We seek an optimal trade-off because if the testing rate is chosen high, then the stockpile finishes early and leaves us with no tests at hand, which could result in a second wave of the epidemic more intense than the first wave. On the other hand, if the testing rate is chosen low, then it is impossible to limit the epidemic spread (or 'flatten the curve'), which could challenge the available medical facilities of the country.

In this section, we determine a constant optimal daily allocation of a limited stockpile of tests r max minimizing the epidemic peak. Such an allocation is called the constant optimal strategy for testing (COST). Given the total stockpile of tests r max , the constant testing rate is given by

where the time period T := r max /C represent the duration of the testing policy once C is determined. Therefore, the approximate solution (11) of undetected infected population is given by

where Ξ denotes the moment in the infection time coordinate when the stockpile of tests finishes. This Ξ is given by an implicit formula

which is derived from (8) as

where T := r max /C and x I (ξ) is given by (11) and (13) .

The epidemic spread can be controlled through a suitable testing rate u(t) = C, for t ∈ [0, T ]. However, when the limited stockpile of tests finishes, the disease may start spreading again, resulting in a second wave of the epidemic. Let the testing phase be the time interval when the tests are being performed, i.e., t ∈ [0, T ], and let the non-testing phase be the time after the stockpile finishes, i.e., t > T . Thus, it is reasonable to suppose that there can be two epidemic peaks -one that arrives during the testing phase and the other that arrives during the non-testing phase.

Let ξ p1 and ξ p2 be the moments in infection time coordinate when the two epidemic peaks occur. We will prove that 0 < ξ p1 ≤ Ξ ≤ ξ p2 in the following:. If the two epidemic peaks exist, then

where the peak times are given as

with the reproduction numbers

Therefore, we have 0 < ξ p1 < ξ p2 . Further, notice that the first peak occurs only if ξ p1 < Ξ, otherwise it is ill-defined. Similarly, ξ p2 > Ξ.

The values of two epidemic peaks are

) and x p2 I = x I (ξ p2 ). It is obvious that x p1 I decreases as C increases, because x p1 I represents the first epidemic peak during the testing phase. Further, it is possible to prove that CΞ decreases as C increases for every sufficiently large C, where Ξ = Ξ(C) is given by the solution of (14) . From (14) , we obtain

Since d(CΞ)/dC = Ξ + CdΞ/dC, therefore

where Ξ is rewritten according to (7) sufficiently large C such that T is not too large, x p1 I decreases and x p2 I increases. This property can be used to minimize the maximum between two epidemic peaks. Indeed, the maximum between a decreasing and an increasing function is minimized when they are equal to each other. Thus, we equate two epidemic peaks in (15) and solve with respect to Ξ in order to obtain the optimality condition

which, along with (14), constitutes a complete system to determine the optimal C. Proposition 4. Consider the testing rate u(t) defined by (12) and assume that x T ≈ (1 − θ)N . Then, the COST policy C is obtained by solving the system of equations (14) and (16) with T := r max /C. This policy is unique provided that R 1 > 1.

The proof of this proposition follows from the prior discussion. The solution C for (14) and (16) can be obtained numerically [11] .

Similar to the BEST policy, we evaluate the COST policy through its impact on the number of active ICU cases B(t) and the cumulative number of deaths E(t) after fitting the model outputs (5) and (6) with the data in the actual testing scenario. However, we fit these equations to the data by using different value of θ than obtained in the case of BEST policy. For the COST policy, the value of θ is obtained through model validation with the COVID-19 data of France [11] under the assumption that x T (t) ≈ (1 − θ)N .

We consider that the total stockpile of tests r max = 2, 038, 037, which is the total number of tests performed from January 24 to July 01, 2020, in France. Then, we obtain the optimal testing rate C = 17, 144 with the terminal time T = 118 (i.e., May 20) from Proposition 4. The actual testing rate of France and the testing rate required by the COST policy are illustrated in Figure 6 . Notice that most of the tests in the actual testing are consumed after May 13, whereas all the tests in COST are allocated equally in the time interval from January 24 to May 20. The number of tests performed per day in the actual testing exceeds 50, 000 per day after May 13, which is about three times more than what is required by COST, i.e., 17, 144. Thus, COST is optimal in a sense that it is practical, it decreases the burden on medical facilities, and it reduces the number of deaths significantly. The impact of COST policy on the number of active ICU cases B(t) and the cumulative number of deaths is illustrated in Figure 7 and Figure 8 , respectively. From the figures, we observe that the COST policy reduces the peak of B(t) by 11.12% and the total number of cumulative deaths E(t) by 37.52%.

We proposed a SIDUR model for demonstrating the impact of testing rate in the suppression and/or mitigation of an epidemic. The tests enable the health authority to diagnose and isolate the infected people, which limits the spread of disease to the susceptible population. Two testing policies have been proposed: 1) best-effort strategy for testing (BEST) and 2) constant optimal strategy for testing (COST). The BEST policy is a suppression policy that provides the minimum testing rate to be implemented from a certain day onward to stop the growth of undetected infected cases immediately. On the other hand, the COST policy is a mitigation policy that considers a limited stockpile of tests and optimally allocates the tests in a time interval so that the peak of the epidemic is minimized. Although both BEST and COST policies are easy to compute and implement, they propose constant testing rates, which may limit the influence of testing if the epidemic parameters change due to external conditions. In the future, therefore, it will be interesting to devise a testing policy with a dynamic testing rate that minimizes the epidemic peak and/or the cumulative number of infected cases.

SARS outbreaks in Ontario, Hong Kong and Singapore: The role of diagnosis and isolation as a control mechanism

Optimal resource allocation for control of networked epidemic models

Smart testing and selective quarantine for the control of epidemics

Optimal test allocation

Optimal COVID-19 quarantine and testing policies

An SEIR infectious disease model with testing and conditional quarantine

COVID-19 pandemic control: Balancing detection policy and lockdown intervention under ICU sustainability

Modelling the COVID-19 epidemic and implementation of population-wide interventions in Italy

Understanding unreported cases in the COVID-19 epidemic outbreak in Wuhan, China, and the importance of major public health interventions

Identifying the number of unreported cases in SIR epidemic models

Modeling and control of COVID-19 epidemic through testing policies

The mathematics of infectious diseases

Modern epidemiology

Further notes on the basic reproduction number