The adv en t of aordable computing, lo w-cost sensor hardw are, and high- sp eed and reliable comm unications ha v e spurred ubiquitous installation of sensors in complex engineered systems. Ho w ev er, ensuring reliable data qual- it y remains a c hallenge. Exploitation of redundancy among sensor signals can help impro ving the precision of measured v ariables, detecting the presence of gross errors, and iden tifying fault y sensors. The cost of sensor o wnership, main tenance eorts in particular, can still b e cost-prohibitiv e ho w ev er. Max- imizing the abilit y to assess and con trol data qualit y while minimizing the cost of o wnership th us requires a careful sensor placemen t. T o solv e this c hal- lenge, w e dev elop a generally applicable metho d to solv e the m ulti-ob jectiv e sensor placemen t problem in systems go v erned b y linear and bilinear balance Corresp onding author, Email kris.vil lez@e awag.ch Pr eprint submitte d to Computers and Chemic al Engine ering July 8, 2020 equations. Imp ortan tly , the metho d computes all P areto-optimal sensor la y- outs with con v en tional computational resources and requires no information ab out the exp ected sensor qualit y . Keywor ds: bilinear balance equations, fault detection, m ulti-ob jectiv e optimization, optimal exp erimen tal design, redundancy, sensor placemen t 1. In tro duction In recen t y ears, the adv en t of large-scale cost-eectiv e computing and lo w-cost sensor hardw are has stim ulated great in terest in the deplo ymen t of large-scale sensor net w orks. By com bining large-dimensional data sets with computationally e cien t y et exible and predictiv e mo dels, it is said, one can obtain system designs and pro cess op erations that are m uc h more e cien t than those that are ro oted in domain exp ertise, heuristics, and mec hanis- tic mo dels (Corominas et al., 2018; In ternational W ater Asso ciation, 2019; V enk atasubramanian, 2019). Executing this kind of vision is ho w ev er ham- p ered b y the fact sensors often pro duce signals of questionable qualit y due to exp osure to a harsh en vironmen t (e.g., Ohm ura et al., 2019). In turn, this leads to high sensor main tenance cost, to the p oin t that this cost ma y sub due an y b ene t of ubiquitous sensor net w orks. P o or data qualit y is kno wn to c hallenge the use of b oth mac hine learn- ing mo dels and mec hanistic pro cess mo dels (Rieger et al., 2005, 2006; Rosén et al., 2008; Hauduc et al., 2009). It is therefore no surprise that sev eral stud- ies pro vide metho ds and insigh ts in to the problem of data qualit y assessmen t and con trol in the w ater sector (Rosén and Olsson, 1998; Thomann et al., 2002; Thomann, 2008; Villez et al., 2008; Corominas et al., 2011; Spindler 2 and V anrolleghem, 2012; Alferes et al., 2013; Spindler, 2014; Newhart et al., 2019). Imp ortan tly , iden ti cation of man y mo dels requires that the a v ailable data pro vide a complete and precise picture of all phenomena that are rel- ev an t for the task at hand. F or this, data sets ough t to b e represen tativ e, v oluminous, and of high qualit y . It is generally v aluable to place redundan t sensors for the purp ose of computer-aided anomaly and fault detection, isolation, and diagnosis. A t the same time, installing large n um b ers of sensors implies an op erational cost of sensor o wnership, asso ciated with sensor cleaning, calibration, v al- idation, and part replacemen ts. W e b eliev e this cost will remain high for the foreseeable future, despite the adv en t of lo w-cost hardw are and tremen- dous adv ances in the robustness of instrumen ts measuring ph ysical prop erties (e.g., o w rate, lev el, pressure, temp erature) or w ater qualit y (e.g., ammonia, nitrite, nitrate, ortho-phosphate, total susp ended solids). Th us, it is k ey to balance the costs of sensors against information-ric hness and redundancy . Optimal sensor placemen t is a complex problem due to the presence of nonlinear relationships b et w een the v ariables of in terest and the net w ork ed nature of man y systems. Moreo v er, to place sensors that measure extensiv e v ariables, lik e o w rates, as w ell as in tensiv e v ariables, lik e concen trations and temp eratures, sp ecial care m ust b e tak en to accoun t for bilinear mass balance equations describing the eect of reactions, storage phenomena, and o w splitters. Sev eral authors ha v e addressed this optimization problem. E.g., Ali and Narasimhan (1996) pro vide an iterativ e approac h to obtain an optimal sensor la y out in terms of observ abilit y , follo w ed b y a second searc h for additional sensors to increase the n um b er of redundan t sensors (see b elo w 3 for de nitions). In a similar spirit, Le et al. (2018) searc h for P areto opti- mal sensor la y outs that trade o the n um b er of sensors against the relativ e impro v emen t in precision, i.e. the ratio b y whic h the standard deviation of the estimation errors is reduced, thanks to installation of redundan t sensors. In the pro cess, the searc h is limited to the set of sensor la y outs that mak e a prede ned set of v ariables of in terest observ able. The relativ e impro v emen t of precision is one w a y among man y to ev aluate practical observ abilit y (e.g., W aldra et al., 1998; Chmielewski et al., 2002; Chang et al., 2012; Serpas et al., 2013; Mukherjee et al., 2017; Rico-Ramirez et al., 2007; Joshi and Bo yd, 2008; Soldevila et al., 2018; de Win ter et al., 2019; Nahar et al., 2019). The approac h of Le et al. (2018) is based on the analysis of systems of linear equations, meaning that measuring a concen tration in a single stream implies measuremen t of the o w rate in the same stream. Because this is based on estimation precision, prior kno wledge regarding the measuremen t error stan- dard deviation of the candidate sensors is required. The rst author of this study argues in Le (2019) that a b etter approac h consists of placing individ- ual o w rate and concen tration sensors. This ho w ev er implies that bilinear constrain t equations m ust b e dealt with carefully during the ev aluation of observ abilit y . Le (2019) ev aluates his o wn sym b olic implemen tation of the metho d for iden ti cation of redundan t relationships describ ed in Spindler (2014) to b e v ery time-consuming. Villez et al. (2016) is a rare study where cost, information ric hness, and re- dundancy are considered as indep enden t ob jectiv es for optimization. T o this end, the ob jectiv e for information-ric hness quan ti es the n um b er of v ariables that are structurally observ able (de nition b elo w). Similarly , the redun- 4 dancy ob jectiv e is based on structural redundancy of the installed sensors. This means that no prior information regarding the precision of an y sensor candidate is required. Unfortunately , this w ork is limited to the placemen t of o w rate sensors only , mainly to a v oid accoun ting of bilinear equations during sensor la y out optimization. W e address this in this w ork b y adopting the GENOBS and GENRED pro cedures of Kretso v alis and Mah (1988b) for ev aluation of structural observ abilit y and structural redundancy in systems with arbitrary placemen t of sensors measuring o w rates, concen trations, and temp erature sensors. W e apply this to t w o t ypical w astew ater treatmen t plan t (WWTP) con gurations for whic h information ab out h ydraulic o w rates, concen trations and mass o ws of w astew ater con taminan ts is crucial for plan t op eration. As a result, and for the rst time, it is p ossible to com- pute the complete set of P areto optimal sensor la y outs in engineered systems describ ed b y linear and bilinear balance equations. Sp ecial care has b een tak en to obtain fast implemen tations of the GENOBS and GENRED pro ce- dures as w ell as the optimization metho d itself. As a result, the dev elop ed metho d is b oth e cien t and generally applicable to an y system describ ed b y linear and bilinear balance equations. 2. Materials and metho ds 2.1. Studie d systems Sensor placemen t results are sho wn for t w o WWTP con gurations: (i) a simple organics remo ving WWTP (T c hobanoglous et al., 2013) (WWTP1, Fig. 1a) and (ii) a WWTP for nitrogen remo v al (WWTP2, the so-called mo di ed Ludzac k Ettinger pro cess, MLE, Fig. 1e). Both con gurations con- 5 sist of a set of tanks, including reactors and a settler, whic h are connected b y closed pip es. All pip es carry w astew ater, including a m ultitude of con tami- nan ts, further referred to as the comp onen ts.The most imp ortan t con v ersion pro cesses are (i) gro wth and deca y of biomass, whic h aects the concen- tration of particulate matter (solids), (ii) o xidation of organic matter, (iii) o xidation of ammonia (in to nitrite and nitrate), (iv) and o xidation of nitrite (in to nitrate). W e consider the plan ts to ha v e aerobic reactors only so that the concen tration of ortho-phosphate is unaected b y an y con v ersion pro cess, i.e. ortho-phosphate can b e treated as a comp onen t that is b oth conserv ed and soluble. 2.2. Sensor plac ement as a multi-obje ctive optimization pr oblem The sensor placemen t problem consists of nding sensor la y outs that are optimal in terms of cost, observ abilit y , and redundancy for a system of ma- terial o ws describ ed b y linear h ydraulic balances (total mass o ws), bilinear comp onen t balances (e.g., solids mass o w), and splitter constrain ts (i.e., to express that concen trations in fron t and at the bac k of a splitter b o x are equal). W e apply the de nitions of structur al observability and structur al r e dundancy as in prior w ork (Villez et al., 2016). A v ariable is structurally observ able when (i) a measuremen t of this v ariable is a v ailable or (ii) a unique v alue for the v ariable can b e computed b y means of a set of equations and other measuremen ts. A sensor is considered structurally redundan t if the measured v ariable remains observ able when the considered sensor is remo v ed. The total n um b er of comp onen ts is giv en as C and the total n um b er of ph ysical streams, i.e. pip es, is giv en as S . TheS streams are indexed with an in tegers (s= 1;:::;S ). W e consider v e t yp es of v ariables asso ciated with 6 ev ery stream: the (total mass) o w rate (unit: [m3=d] ), concen trations of C comp onen ts (unit: [g=m3] ),C comp onen t mass o w rates corresp onding to the concen trations (unit: [mol=d ] ), temp erature (unit: [K] ), and heat o w (unit: [J=d] ). Within eac h stream w e index the considered v ariables with v , wherev= 0 is the index of the (total mass) o w rate, v= 1;2;:::;C are the indices of the concen trations of the C comp onen ts (unit: [mol=m3] ), v=C+ 1 is the index of temp erature, v=C+ 2;C+ 3;:::; 2C+ 1 index the comp onen t mass o w rates (in the same order as the concen tration v ariables), and v= 2C+ 2 refers to the heat o w (unit: [J=d] ). By default, w e consider that a sensor can b e placed for an y the considered v ariables in an y ph ysical stream. F or optimization purp oses, a sensor la y out is describ ed b y means of bi- nary de cision variables ,Xs;v , whic h represen t the absence ( 0 ) or presence (1 ) of a sensor for v ariable v in streams . The matrix X is anSV - dimensional matrix ( V= 3 + 2C ) con taining the v alues for all decision v ariables (Xs;v=X(s;v) ). Giv en suc h a matrix, one can compute whic h v ariables are observ able and whic h of the placed sensors are redundan t. The matrix Y is anSV -dimensional matrix with elemen ts Ys;v=Y(s;v) , whereYs;v indicates whether v ariable v in streams is structurally observ able (1 ) or not ( 0 ). Similarly , the SV -dimensional matrix Z con tains elemen ts Zs;v=Z(s;v) indicating whether stream s is equipp ed with a structurally redundan t sensor for v ariable v (1 ) or not ( 0 ). The complete set of feasible sensor la y outs consists of all feasible matrices X and is named the ro ot set. All remaining sym b ols are describ ed in T able 1. F or the purp ose of optimization, the cost, observ abilit y , and redundancy 7 ob jectiv es are: fC(X) =SX sVX vWC s;vXs;v (1) fO(Y) =SX sVX vWO s;v(1Ys;v) (2) fR(Z) =SX sVX vWR s;v(1Zs;v) (3) withWC s;v ,WO s;v , andWR s;v w eigh ts. These w eigh ts are t ypically non-negativ e. Ho w ev er, negativ e w eigh ts can b e used in principle, e.g. to express that re- mo ving an existing sensor comes with a non-negligible cost. The optimization problem consists of nding matrices X whic h minimize fC,fO, andfR. 2.3. L ab eling observable variables and r e dundant sensors A c c ounting for physic al str e ams. T o ev aluate Y andZ , the graph-based la- b eling pro cedures GENOBS and GENRED pro vided b y Kretso v alis and Mah (1988b) are adopted to pro duce the matrices Y andZ giv en an y plan t graph and an y sensor la y out X . The graphs (Deo, 2004) for the studied WWTPs are giv en in Fig. 1b/c/d/f/g/h. These graphs con tain at most t w o t yp es of edges. The edges of the rst t yp e are sho wn as full lines and corresp ond to the ph ysical streams of the studied system. These are the S streams men tioned ab o v e. Ev ery no de in the graph represen ts a total mass o w balance with the in- and outgoing edges represen ting in- and outgoing mass o ws. F or example, no de a in Fig. 1b, corresp onds to the follo wing h ydraulic balance: 0 =q1+q6q2 (4) 8 whereq1 ,q2 , andq6 the mass o w rates in stream 1, 2, and 6. The cor- resp onding edges of the graph are called a cutset, as their remo v al cuts the graph in separate graphs. This means one can en umerate all p ossible h y- draulic balances b y en umerating the cutsets of the graph. F or this, e cien t algorithms exist (Deo, 2004). The maximal n um b er of indep enden t h ydraulic balances among these balances is alw a ys one less than the n um b er of no des. One p ossible set of indep enden t h ydraulic balances can b e found b y comput- ing the fundamen tal cutsets of the graph. An adv an tage is that this pro vides a precise de nition for the concept of o v erlapping balances, whic h has only b een de ned lo osely so far (see e.g., Rieger et al., 2010; Spindler, 2014; Le et al., 2018), namely: an y t w o cutsets with a shared edge represen t a pair of o v erlapping balances. A c c ounting for r e actions. Edges of the second t yp e are optional, are sho wn with dashed lines, and corresp ond to imaginary streams in the studied sys- tem. Eac h dashed line in Fig. 1c represen ts an edge b et w een a ph ysical no de (no de b and c ) and the en vironmen t (no de e ). As discussed in Kretso v alis and Mah (1988a), this enables accoun ting for de cits in individual comp o- nen t balances due to the eect of reactions (Kretso v alis and Mah, 1988a,b). Stream 8 is directed from the en vironmen tal no de e to the reactor no de b . This pro vides a graphical represen tation of the fact that the balance equation for thej th comp onen t around no de b is written as: 0 =q2c2;jq3c3;j+8v8;j (5) withq2 andq3 the mass o w rates in stream 2 and 3, c2;j andc3;j the 9 corresp onding concen trations, 8 the reaction rate (unit: mol=m3:d ), and v8;j the stoic hiometric co e cien t for the considered comp onen t (unit: [] ). The same holds for stream 9, whic h represen ts eects of reactions in the settler. W e assume, as in Kretso v alis and Mah (1988b), that all stoic hiometric co e cien ts are kno wn. A c c ounting for tr ansp ort phenomena. A mo di ed approac h is tak en in the graph Fig. 1d. In this case, an imaginary stream is added from no de b to c . This particular mo di cation allo ws to accoun t for de cits in the balances around the reactor basin and the settler due to temp orary storage of the considered comp onen t (e.g., solids) in the reactor or settler. In this case, reactions in the reactor or the settler are not accoun ted for. As an example, the balance equation around no de b no w has the follo wing structure: 0 =q2c2;jq3c3;jM8;j=q2c2;jq3c3;j8u8;j (6) whereq2 ,q3 ,c2 ,c3 ha v e the same meaning as ab o v e and r8;j represen ts the net transp ort rate of comp onen t j (unit: [mol=d ] ). T o matc h the balance equation structure ab o v e, w e de ne M8:=8u8;j withu8;j a constan t. u8;j indicates whether the comp onen t participates in the transp ort phenomenon. It is equal to one if the comp onen t is sub ject to the considered storage phe- nomenon (e.g., comp onen t j is a solid) and zero otherwise (e.g., comp onen t j is soluble). W e refer to 8 as the transp ort rate. In the presen t case, a p ositiv e (negativ e) transp ort rate means the considered comp onen t is accum ulating in the reactor (settler). This is represen ted b y the min us sign in the term M8 and as an edge going out from no de b in the graph. More terms of the same 10 form can b e added when m ultiple comp onen ts are stored and released with distinct rates, th us leading to the addition of m ultiple imaginary edges to the graph. This approac h is dieren t compared to existing w ork (Kretso v alis and Mah, 1988a,b) in the sense that the added imaginary streams connect no des that represen t ph ysical lo cations, in con trast to edges represen ting re- actions. Imp ortan tly , this mo di ed metho d implies that the total mass of ev ery comp onen t in the system remains constan t, i.e. w e assume that there are no plan t-wide comp onen t balance de cits. As a result, Fig. 1b represen ts the situation for a conserv ed comp onen t (e.g., ortho-phosphate), Fig. 1c represen ts the situation for a reactiv e com- p onen t (e.g., ammonia, nitrite, nitrate), and Fig. 1d represen ts the case of a comp onen t whose total mass in the plan t is conserv ed (e.g., total solids). Sim- ilar graphs for WWTP2 (MLE) are sho wn in the same order in Fig. 1f/g/h. The total n um b er of imaginary edges is giv en as S. The edges are indexed so that the rst S edges among the complete list of S:=S+Sedges cor- resp ond to the ph ysical streams. Similar to the cutsets discussed ab o v e, one can compute the cutsets of the complete graph, co v ering b oth ph ysical and imaginary streams. By doing so, one can en umerate all p ossible comp onen t o w balances for an y single comp onen t, regardless of whether the comp o- nen t is conserv ed, sub ject to con v ersions, or sub ject to storage phenomena. As b efore, pairs of cutsets with shared edges represen t pairs of o v erlapping balances. Implementation. While the original Structural Observ abilit y And Redun- dancy (SO AR) to olb o x (Villez et al., 2016) could in principle b e used for this w ork also, initial results indicated that its computational e ciency w as 11 insu cien t to solv e the m ulti-ob jectiv e sensor la y out optimization problems within acceptable time windo ws (da ys to w eeks). F or this reason, a new v ersion of the SO AR to olb o x (v2.0) has b een created. The most imp ortan t c hange is that the sets of (a) all cycles of the complete graph, (b) all cutsets of the complete graph, and (c) all cutsets of the graph without imaginary edges are computed in adv ance and used as inputs to the GENOBS and GENRED pro cedures. This enables an e cien t searc h for the P areto fron t. The exact implemen tation is describ ed in detail in Villez (2019). All co de necessary to repro duce our results is added in the Supplementary Information . 2.4. Optimization 2.4.1. Conc ept of surplus r e dundancy In an y system equipp ed with a giv en sensor la y out, one can add redundan t sensors b y installing sensors for v ariables that are already observ able. In man y cases, suc h an additional sensor will only increase the cost b y one and increase the n um b er of redundan t sensors b y one. When this is the case, w e consider the resulting sensor la y out to ha v e surplus redundancy , i.e. one could remo v e at least one sensor without c hanging the n um b er of observ able v ariables or the n um b er of non-redundan t sensors. Surplus redundancy can bring a m ultitude of b ene ts. E.g., additional redundan t sensors can impro v e the precision of reconciled measuremen ts (e.g., Cro w e, 1989; Le et al., 2018) or impro v e the abilit y to isolate sensor faults (e.g., Gertler and Singer, 1990). In the presen t study , w e exploit surplus redundancy to obtain a more e cien t m ulti-ob jectiv e optimization strategy , as explained b elo w. 12 2.4.2. Using surplus r e dundancy during multi-obje ctive optimization The complete P areto fron t is computed with a t w o-step metho d. In step A, w e solv e a mo di ed v ersion of the m ulti-ob jectiv e optimiza- tion problem b y replacing the redundancy ob jectiv e function with fN, whic h computes the fraction of the ob jectiv e fRthat is asso ciated with only the non-redundan t sensors among the installed sensors. fN(X;Z) =fR(XZ) (7) This new ob jectiv e function computes a p enalt y for installing non-redundan t sensors. The mo di ed optimization problem then trades this p enalt y o against the cost and observ abilit y ob jectiv es. This problem is solv ed with the deterministic m ulti-ob jectiv e branc h-and-b ound optimization metho d (Nemhauser and W olsey, 1988; Ehrgott and Gandibleux, 2002; Villez et al., 2016). In step B, w e consider the original ob jectiv e functions fC,fO,fR. The complete P areto fron t, no w including sensor la y outs with surplus redundancy , is obtained b y executing the follo wing steps for eac h la y out on the existing P areto fron t: 1. T ak e the computed matrices for the considered la y out and name these X0 ,Y0 , andZ0 . Compute the ob jectiv e functions fC,fO,fRand add this solution to the list of solutions. 2. List the K additional candidate sensors that ha v e not b een placed but for whic h the corresp onding v ariable is already observ able. An y of these additional sensors, when placed, will b e redundan t automatically . 3. CreateN= 2K1 additional sensor la y outs b y placemen t of ev ery non-empt y subset of the additional candidate sensors. Call the n um b er of added sensors P . 13 4. F or eac h of the N la y outs: (a) Chec k if the considered la y out is already in the P areto fron t. If not, con tin ue. (b) Compute X1 b y c hanging ev ery 0 in X0 in the lo cation of the added sensors P to 1 to re ect the added sensor placemen t. Z1 is computed in the same fashion starting with Z0 . (c) Set Y1=Y0 . Indeed, no v ariables b ecomes observ able b ecause sensors are only placed for v ariables that are already observ able. (d) Compute the ob jectiv e functions fC,fO,fRand add the obtained solution to the list of solutions. 5. Prune an y solution that is not P areto optimal in the original ob jectiv e functionsfC,fO,fRfrom the list of solutions. W e pro v e that this t w o-step metho d eectiv ely computes the P areto fron t for the ob jectiv es fC,fO,fR. T o this end, w e refer to the P areto fron t obtained b y direct optimization of fC,fO, andfRas PF0. The P areto fron t obtained in step A describ ed ab o v e consists of all solutions that exhibit P areto optimalit y for fC,fO, andfNand is named PF1. No w consider an y P areto optimal la y out in PF0 and call it la y out L0. If this la y out has no surplus redundancy (Case 1), it means that one cannot remo v e an y sensor from this la y out without decreasing the v alue of fOor increasing the v alue of fN. This la y out is therefore also part of PF1 and is added to the nal set of sensor la y outs in Step B.1 ab o v e. If this la y out has surplus redundancy (Case 2), it is p ossible to remo v e a redundan t sensor from this la y out in suc h a w a y that the sensor la y out is guaran teed to b elong also to PF0. Indeed, one can remo v e a sensor among the redundan t sensors for whic h the prop ortion of the 14 increase of fRto the decrease of fCis minimal. In addition, remo ving an y redundan t sensor cannot c hange the v alue of fO, giv en that all v ariables that w ere observ able remain observ able. One can con tin ue this pro cess of sensor remo v al to pro duce sensor la y outs that are guaran teed to b e in PF0 un til one has reac hed a sensor la y out without surplus redundancy . A t this p oin t, one has obtained a sensor la y out in PF0 that is necessarily part of PF1 also. Call this la y out L1. Con v ersely , this means that la y out L0 can b e pro duced b y adding sensors to la y out L1 for v ariables that observ able already . Since Step B.2 un til B.3 en umerate ev ery p ossible sensor la y out L0 b y adding sensors to ev ery la y out L1 in PF1, it follo ws that the complete P areto fron t PF0 is pro duced b y com bining Step A and B as describ ed ab o v e. 2.5. Il lustr ation of the metho ds 2.5.1. R estrictions The studied metho ds are general and enable placemen t regardless of (a) the n um b er of comp onen ts and (b) the c hosen w eigh t matrices ( WC,WO, WR). Without losing generalit y , w e illustrate the metho ds with the follo wing restrictions:  W e assume there are 3 or more comp onen ts presen t in the system and that these comp onen ts are presen t in ev ery stream ( C3 ).  The cost w eigh ts ( WC s;v ) are 0 (sensor a v ailable at no cost), 1 (sensor a v ailable at a cost), or +1 (sensor not feasible).  Sensors for direct measuremen t of comp onen t mass o w rates and heat o w rates are not a v ailable. 15  W e place sensors for t w o v ariables only: total mass o w rates and con- cen trations of one comp onen t (e.g., ortho-phosphate or total susp ended solids, but not b oth). Practically , all cost w eigh ts are equal to in nit y , except forv= 0 andv= 1 .  Unless men tioned otherwise, w e assume that ev ery stream can b e equipp ed with a o w rate sensor, a concen tration sensor, or b oth: WC s;v=8 >< >:1; if:s2f1;:::;Sg andv2f0;1g +1; otherwise(8)  Unless men tioned otherwise, w e assume a uniform in terest in estimates for all v ariables (all p oten tial estimates are equally v aluable), and as- sume that it is equally desirable for an y sensor to b e redundan t: WO s;v=WR s;v= 1 (9) 2.5.2. Studie d pr oblems W e study a total of nine optimization problems. The rst four optimiza- tion problems are based on the WWTP1 system (Fig. 1a) while the remaining v e are based on the WWTP2 system (Fig. 1e). Among eac h of these sets of optimization problems, the rst problem consists of placemen t of o w rate sensors only (problem 1 and 5). This problem is selected to compare the p erformance of the metho ds prop osed in this w ork with the metho ds used in Villez et al. (2016) and is therefore solv ed with the original to olb o x (SO AR v1.2) and the new est v ersion (SO AR v2.0). Optimization problem 2, 3, and 4 concern placemen t of sensors for o w rates and one comp onen t in WWTP1. These corresp ond to the graphs in Fig. 1b/c/d and th us re ect 16 a case with a conserv ed comp onen t, a reactiv e comp onen t, and a conserv ed solid comp onen t. Optimization problem 6 to 8 are the equiv alen t problems for WWTP2. In this case, the concen tration in stream 9 (carb on dosage stream) is considered kno wn. Optimization problem 9 consists of a mo di - cation of problem 8 b y c hanging the w eigh ts for the observ abilit y ob jectiv e. These w eigh ts are listed in T able 2 and re ect our judgmen t regarding the relev ance of o w rates, concen trations, and comp onen t o w rates for sludge managemen t (solids) in a t ypical WWTP . F or example, only the comp onen t mass o w rates in stream 1 (in uen t), 6 (settler loading), 7 (e uen t), 9 (carb on dosage), 10 (sludge remo v al), 11 (return sludge), and 12 (in ternal recycle) are of in terest. In addition, w e consider the o w rates for stream 9 to 12 to b e kno wn (carb on dosage, in ternal recycle, sludge recycle, sludge w aste). This is based on the fact that these streams are often equipp ed with a pump, so that these mass o w rates or their setp oin ts can b e kno wn in principle. By doing so, w e illustrate the generalit y of our metho d. 2.6. Implementation All computations w ere executed with Matlab 9.6.0.1072779 (R2019a) on a desktop mac hine (System: In tel®Core  i7-4770 CPU 3.40GHz, RAM: 16GB; OS: Microsoft Windo ws 10 Education, 64-bit). The Supplementary In- formation includes all soft w are to repro duce our results, including the SO AR soft w are to olb o x dev elop ed for this purp ose, and is published under the GPL v3 license. 17 3. Results The WWTP1 system mainly serv es a didactic purp ose. F or this reason, w e refer the reader new to sensor placemen t, graph theory , or m ulti-ob jectiv e optimization to Section S.2 of the Supplementary Information , where results with WWTP1 are describ ed in detail. In the next paragraphs, w e discuss on results obtained for WWTP2 (MLE), as the scale of this system matc hes realistic cases. A t the end of the results section, w e discuss computational requiremen ts. Note that all computed P areto fron ts are listed in tabular form in the Supplementary Information . 3.1. WWTP2 (MLE) W e discuss results for optimization problems 6 to 9 to illustrate the ap- plicabilit y of our approac h in div erse systems at realistic scale. In Problem 6 to 8, mass o w rate sensors and comp onen t concen tration measuremen ts can b e placed in ev ery ph ysical stream except stream 9. In stream 9, the comp onen t concen tration is considered kno wn and only a mass o w rate sen- sor can b e placed. This means a total of 23 sensors can b e placed, leading to a total of 8,388,608 candidate sensor la y outs. Problem 9 is used to stress the generalit y of our metho d b y demonstrating that one can easily mo dify the ob jectiv e functions to accoun t for a reduced set of sensor candidates, presence of already installed sensors, and prioritization of certain v ariables of in terest o v er others. 3.1.1. Pr oblem 6: WWTP2 (MLE) with c onserve d c omp onent In problem 6, the comp onen t of in terest is a conserv ed comp onen t, e.g. ortho-phosphate, so that the corresp onding graph (Fig. 1f ) do es not con tain 18 an y imaginary edge. Fig. 2 sho ws the obtained P areto fron t. One can see 32 distinct bubbles describing the complete P areto fron t. These con tain a total of 1,565,072 sensor la y outs (19% of all candidate la y outs). Within this P areto fron t, there are 1,531,864 sensor la y outs with surplus redundancy (15 red bubbles, 18% of all candidate la y outs) and 33,208 la y outs without surplus redundancy (17 bubbles, 0.40% of all candidate la y outs). In this second category , one can recognize (a) the trivial la y out without an y sensor (blac k), (b) 7,437 la y outs with some but not all v ariables observ able and one to six non-redundan t sensors (white), (c) 24,690 la y outs with all v ariables observ able and sev en non-redundan t sensors (blue), (d) 400 la y outs with all v ariables observ able and eigh t sensors, all of whic h are redundan t (y ello w), and (e) 680 la y outs with some but not all v ariables observ able and t w o to sev en sensors, some or all of whic h are redundan t (green). T o understand the P areto solutions b etter, Fig. 3 pro vides another lo ok in to the set of optimal sensor la y outs. Rather than sho wing the n um b er of redundan t sensors on the v ertical axis, it sho ws the fraction of concen tration sensors among all installed sensors. This results in dividing most of the bub- bles sho wn in Fig. 2 in to m ultiple bubbles. F or example, the blue bubble in Fig. 2, represen ting 24,690 sensor la y outs with sev en sensors making all v ari- ables observ able is no w split in to four bubbles in Fig. 3. F rom b ottom to top, these are (a) a bubble of 8,880 la y outs with v e mass o w rate sensors (71% mass o w rate sensors), (b) a bubble of 11,369 la y outs with four mass o w rate sensors (57% mass o w rate sensors), (c) a bubble of 4,051 la y outs with three mass o w rate sensors (43% mass o w rate sensors), and (d) a bubble of 390 la y outs with t w o mass o w rate sensors (29% mass o w rate sensors). 19 It is particularly striking that the linear pro le of bubbles represen ting la y- outs with surplus redundancy in Fig. 2 has no w b een transformed in to a set of bubbles app earing lik e scales on a sh, rst with increasing spread (as if from mouth to b o dy) and then with decreasing spread (as if from b o dy to tail). This is a result of t w o comp eting eects. First, as the n um b er of sensors is increased, this also increases the exibilit y in c hoice of sensor t yp e for these additional sensors. Second, increasing the n um b er of sensors b e- y ond 14 sensors starts to limit the n um b er of additional sensor options that remain a v ailable. This con tin ues un til all (14) candidate sensors are selected and no exibilit y remains at all. The same phenomenon o ccurs for ev ery problem in v olving b oth o w rate sensors and concen tration sensors (Prob- lem 13 and 69, not sho wn). By setting the cost w eigh ts for o w sensors and concen trations equal to eac h other one obtains sensor la y outs ac hieving the same lev els of structural observ abilit y and redundancy while exploiting a v arying n um b er of sensors for eac h v ariable. This abilit y to ac hiev e the same sensor la y out p erformance (observ abilit y and redundancy) with la y outs with v arying distributions of mass o w rate and concen tration sensors is a result of giving equal w eigh t to all sensors in the cost and redundancy ob jectiv es and to all v ariables in the observ abilit y ob jectiv e. A simple mo di cation, e.g. increasing the relativ e cost of concen tration sensors, w ould reduce the n um b er of solutions dramatically . W e return to this observ ed exibilit y in the discussion. 3.1.2. Pr oblem 7: WWTP2 (MLE) with r e active c omp onent Problem 7 concerns the case of a reactiv e comp onen t, lik e an y nitrogen- con taining comp onen t (e.g. ammonia, nitrite, nitrate, total nitrogen). This is 20 re ected in Fig. 1g. Fig. 4 sho ws the resulting P areto fron t. In this case, there are 48 bubbles represen ting 981,242 la y outs (12% of all candidate la y outs). The ma jorit y of these (909,132 la y outs, 11% of all la y outs) ha v e surplus redundancy and are spread o v er 26 bubbles (red bubbles). These bubbles are split in to 2 subsets of equal size (eac h 13 bubbles, eac h 454,566 la y outs). One subset consists of la y outs with all 42 v ariables observ able and all sensors redundan t except one. The other subset consists of P areto optimal la y outs that mak e only 37 out of 42 v ariables observ able but exhibit redundancy for all sensors. A minorit y of the P areto optimal la y outs (72,110 la y outs, 0.86% of all la y outs) do not exhibit surplus redundancy and are spread o v er 22 bubbles. This includes (a) the trivial la y out without an y sensor (blac k). This trivial la y out pro duces one observ able v ariable, namely the concen tration in stream 9, b ecause it is assumed kno wn. One also recognizes (b) 38,629 la y outs with some but not all v ariables observ able and one to eigh t non-redundan t sensors (white), (c) 30,214 la y outs with all v ariables observ able and nine non-redundan t sensors (blue), (d) 972 la y outs with all v ariables observ able and ten sensors, nine of whic h are redundan t (y ello w), and (e) 2,294 la y outs with some but not all v ariables observ able and t w o to nine sensors, some or all of whic h are redundan t (green). Note that reac hing complete observ abilit y without redundancy in Prob- lem 7 requires t w o more sensors compared to Problem 6. This is not so surprising, considering that the reactiv e case includes t w o additional rate v ariables (the t w o reaction rates). F or example, the a v ailable balances around the reactor and settler (no des d ande , comp onen t mass o w balances) en- 21 able estimation of the unmeasured reaction rates (stream 13 and 14) when the mass o w rates and comp onen t concen trations in stream 4, 5, 6, 7, and 8 are measured. This is b ecause the stoic hiometric co e cien ts for stream 13 and 14 are kno wn, so that the t w o comp onen t mass o w balances en- able estimation of the reaction rates. This requires 10 sensors. Note that similar eects can b e observ ed for WWTP1 (Problem 2 and Problem 3, see Supplementary Information for details). A curious diagonal pattern can b e seen at the top-left of the gure. One can see t w o series of bubbles represen ting la y outs with surplus redundancy . The rst series starts with a bubble represen ting 8,001 la y outs with 11 sen- sors that mak e all (42) v ariables observ able and 10 of the 11 installed sensors redundan t. The second series starts with a bubble of the same size (8,001 la y outs) with 10 sensors that mak e all but v e v ariables (37 total) observ able and all (10) sensors redundan t. The remaining bubbles in eac h series can b e traced b y increasing the n um b er of sensors incremen tally while sim ultane- ously increasing the n um b er of redundan t sensors with the n um b er of sensors added. Imp ortan tly , for eac h increase of the n um b er of installed sensors, the n um b er of la y outs in the corresp onding bubbles in b oth series remains the same. The in teresting rep eated pattern observ ed in the previous graph can b e explained as follo ws. The most imp ortan t prop ert y of Problem 7 is that it is imp ossible to place a redundan t concen tration measuremen t in stream 7. More sp eci cally , it is imp ossible to write a balance equation in v olving the concen tration in stream 7 whic h do es not in v olv e the reaction rate for stream 13, whic h is alw a ys an unkno wn v ariable that needs to b e estimated. T o see 22 this, consider ev aluating redundancy for the concen tration sensor in stream 7, i.e. remo v e this sensor and c hec k if this v ariable is still observ able. When doing so,13 andc7 are t w o unkno wns participating in a single indep enden t balance equation only , meaning that these unkno wns cannot b e estimated, in turn indicating that the remo v ed sensor is not redundan t. The equiv alen t graph theoretical observ ation is that there is not a single cutset in the graph (Fig. 1f/g/h) including edge 7 but not including edge 13. More sp eci cally , one cannot split the graph in to t w o graphs so that the no des connected b y edge 7 are disconnected without remo ving edge 13. F or this reason w e con- sider this a structural iden ti abilit y issue. Imp ortan tly , this means it can only b e resolv ed b y mo difying the de nition of Problem 7. F or example, one could consider (a) sim ultaneous consideration of balances for m ultiple com- p onen ts, th us requiring concen tration sensors for more than one comp onen t, (b) b y measuring all mass fractions in stream 7 (whic h is practically imp os- sible for the w ater mass fraction), (c) allo wing for installation of redundan t sensors in the same stream (hardw are redundancy), or (d) assuming that no reaction in v olving the comp onen t of in terest o ccurs in the settler (th us remo ving stream 13 from the graph). 3.1.3. Pr oblem 8: WWTP2 (MLE) with c onserve d solid c omp onent Problem 8 concerns the case of a conserv ed solid comp onen t (e.g., total susp ended solids), as re ected in Fig. 1h. The corresp onding P areto fron t is sho wn in Fig. 5. There are 33 bubbles represen ting 1,563,126 la y outs (19% of all candidate la y outs). The ma jorit y of these la y outs (1,478,757 la y outs, 18% of all la y outs) ha v e surplus redundancy and are spread o v er 14 bubbles (red bubbles). The remaining la y outs (84,369 la y outs; 1.0% of all 23 candidate la y outs) do not exhibit surplus redundancy and are spread o v er 19 bubbles. These bubbles include (a) the trivial la y out without an y sensor (blac k), (b) 23,454 la y outs with some but not all v ariables observ able and one to sev en non-redundan t sensors (white), (c) 58,026 la y outs with all v ariables observ able and eigh t non-redundan t sensors (blue), (d) 1,500 la y outs with all v ariables observ able and nine sensors, all of whic h are redundan t (y ello w), and (e) 1,388 la y outs with some but not all v ariables observ able and t w o to nine sensors, some or all of whic h are redundan t (green). In this case, reac hing complete observ abilit y without redundancy requires one more sensor compared to Problem 6 and one less compared to Problem 7. This is explained as the consequence of adding the transp ort rate v ari- able, whic h is in tro duced to accoun t for comp onen t im balances in the reactor and the settler and cannot b e measured directly . The unmeasured rate par- ticipates as a single rate in t w o indep enden t balance equations: for no de d (stream 4, 5, and 13) and no de f (stream 6, 7, 8, and 13). Consider measur- ing mass o w rates and concen trations in all ph ysical streams. This mak es all v ariables of in terest observ able. It also mak es all sensors redundan t as eac h mass o w rate and comp onen t concen tration participates in at least one balance equation that excludes the unkno wn transp ort rate. Indeed, b y considering the balances around no des a ,b ,c ,e , andg one obtains 10 inde- p enden t equations (5 o w balances and 5 comp onen t balances) in v olving 24 measuremen ts. Remo ving an y single measuremen t, means that one obtains 10 equations with one unkno wn, so that an y single measuremen t clearly is re- dundan t. F ollo wing this path of reasoning, the P areto fron t has to include at least one sensor la y out for whic h all sensors are redundan t while all v ariables 24 of in terest are observ able. 3.1.4. Pr oblem 9: WWTP2 with c onserve d solid c omp onent, customize d ob- je ctives Problem 9 is a mo di cation of Problem 8 b y assuming dieren t w eigh ts for the observ abilit y ob jectiv e and kno wledge ab out the o w rates in four streams. These streams are t ypically equipp ed with pumps. Suc h pumps often come with an asso ciated o w rate measuremen t. Alternativ ely , the pumps' o w rate setp oin ts, or signals describing p o w er consumption, heat loss, and pressure loss could act as a pro xy for the o w rate. Consequen tly , there are no w only 19 sensor lo cations a v ailable, resulting in 524,288 candi- date sensor la y outs. One can easily v erify that the mass o w rate for stream 8 is observ able without an y additional sensor. Fig. 6 sho ws the resulting P areto fron t. This no w includes 25 bubbles with 258,268 la y outs (49% of all candidate la y outs). The ma jorit y of these la y outs ha v e surplus redundancy (16 red bubbles, 256,957 la y outs, 49% of all candidate la y outs). The remaining 1,311 la y outs (0.25% of all candidate la y outs) are distributed o v er 9 bubbles. These bubbles include (a) the trivial la y out without an y sensor (blac k), (b) 181 la y outs with some but not all v ariables observ able and one to three non-redundan t sensors (white), (c) 709 la y outs with all v ariables observ able and four non-redundan t sensors (blue), (d) 162 la y outs with all v ariables observ able and v e sensors, all of whic h are redundan t (y ello w), and (e) 258 la y outs with some but not all v ariables observ able and t w o to nine sensors, some or all of whic h are redundan t (green). 25 3.1.5. Overview of al l r esults T able 3 giv es an o v erview of the results obtained through solving all nine sensor la y out optimization problems. The o w rate sensor placemen t problems (Problem 1 and 5) are solv ed with v1.2 and v2.0 of the SO AR to olb o x. F or b oth WWTP1 and WWTP2 the resulting P areto fron t is the same regardless of the c hosen soft w are v er- sion, as exp ected. The ma jor dierence lies in the computational require- men ts. F or WWTP1, the P areto fron t is computed in less than 5 seconds with v1.2 and less than 3 seconds with v2.0. F or WWTP2, the impro v emen t is more impressiv e: a factor 10 impro v emen t from 250s to less than 25s. Im- pro v emen ts are partially due to the implemen tation c hanges in the GENOBS and GENRED. These are small for GENOBS (reduction of less than 3s for WWTP2) y et substan tial for GENRED (reduction of 40s for WWTP2). It is notew orth y that the a v erage use of GENRED for ev aluation of a single la y out for WWTP2 tak es only 0.05ms with v2.0 while the same task requires 12ms on a v erage with v1.2, th us pro viding a factor 200 impro v emen t. Despite this impressiv e relativ e impro v emen t, the c hanges in GENOBS and GENRED are resp onsible for a reduction of the total computational load b y 2s only . The remaining reduction of 220s for WWTP2 is therefore attributed to (a) an impro v ed implemen tation of the m ulti-ob jectiv e branc h-and-b ound searc h metho d, (b) deplo ymen t of the t w o-step searc h strategy discussed ab o v e. Most imp ortan tly , the computationally exp ensiv e GENOBS and GENRED pro cedures are only required in step A. The sev en sensor placemen t problems in v olving b oth o w rate and con- cen tration sensors (Problem 24 and 69) are solv ed with v2.0 only . In this 26 case, the computational eort is substan tially larger, e.g. up to 51 h for Prob- lem 8. Note ho w ev er that m ulti-ob jectiv e sensor placemen t problems of this complexit y and scale could not b e solv ed b efore (e.g., with v1.2). One can also see that the sensor la y outs without surplus redundancy that are P areto optimal represen t a small fraction of the total set of feasible sensor la y outs. F or the WWTP2 con gurations, this fraction is at most 1%. This has a t w o distinct adv an tages. The rst adv an tage is that the computationally ex- p ensiv e GENOBS and GENRED pro cedures are only required to compute a small subset of the complete P areto fron t (Step A). The second adv an tage is that structural criteria (for cost, observ abilit y , and redundancy) app ear su cien t to reduce the n um b er of candidate sensor la y outs signi can tly . One general phenomenon is that adding v ariables that cannot b e mea- sured directly (e.g., reaction rates, storage) decreases the n um b er of la y outs on the P areto fron t. Th us, adding additional degrees of freedom to the data reconciliation problem reduces the n um b er of P areto-optimal solutions. The table also sho ws that computing the sensor la y outs with surplus redundancy on the basis of the sensor la y outs without surplus redundancy can b e exe- cuted fairly e cien tly . T aking Problem 8 as an example, one can see that step 2 of the searc h strategy requires just under 15% of the total computa- tional time while this step is resp onsible to ev aluate ab out 25% of the n um b er of the ev aluated sensor la y outs. 27 4. Discussion 4.1. Optimal plac ement of ow r ate and c onc entr ation sensors b ase d on struc- tur al information In this study , w e searc h for P areto optimal sensor la y outs b y nding sensor la y outs whic h optimally trade o cost of sensor o wnership, informativ eness, and redundancy . This is ac hiev ed b y expressing all optimization ob jectiv es as exible functions that are monotonic in binary v ariables describing whether a sensor is installed, whether a v ariable is structurally observ able, and whether an installed sensor is structurally redundan t. The ma jor b ene ts of this approac h are demonstrated for the rst time at a realistic scale and lev el of complexit y through this study:  The metho d is generally applicable and enables computation of the complete P areto fron t within reasonable time windo ws.  The P areto fron t solutions are en umerated completely . This is ac hiev ed b y deterministic optimization, whic h means the set of P areto solutions is pro v ably optimal and complete.  Flo w rate and concen tration sensor la y out optimization (i) can b e exe- cuted for existing plan ts with sensors (bro wn- eld, retro tting) as w ell as for new plan ts prior to construction (green- eld), (ii) do es not rely on information of t ypical sensor signal qualit y , and (iii) do es not re- quire an y measuremen ts. In turn, suc h placemen t will impact the utilit y of real-w orld data b y enabling eectiv e data reconciliation at minimal cost, in turn transforming unc hec k ed data pro duced in complex sys- 28 tems, suc h as WWTPs, in to a v aluable resource for mac hine learning, mo del iden ti cation, and monitoring of daily op erations.  In ternal storage and release of comp onen ts that are conserv ed at a plan t-wide lev el are accoun ted for in a systematic manner, thanks to mo di cation of the observ abilit y and redundancy lab eling pro cedures of Kretso v alis and Mah (1988a,b). This mo di cation is imp ortan t as it leads to a P areto fron t that is suitable for the total solids in w astew ater plan ts. More sp eci cally , it allo ws to accoun t for temp orary im balances of the solids in individual subsystems of the plan t (e.g., reactor, settler), e.g. due to rain ev en ts, while assuming that the solids con ten t of the plan t as a whole remains in tact under normal op erational conditions.  Ev ery P areto fron t is found within 2.5 da ys of computing time on a single mac hine. This is in part due to the mo di ed GENOBS and GENRED pro cedures for observ abilit y and redundancy lab eling, whic h w ere implemen ted e cien tly b y en umerating all cycles and cutsets of the graphs a priori. Automated screening of candidate sensor la y outs is therefore p ossible with con v en tional computing infrastructures. 4.2. Ee cts of obje ctive functions, available sensor typ es and lo c ations, and system top olo gy on the r esulting Par eto fr ont The relationship b et w een the problem sp eci cation, i.e. the ob jectiv e functions, the a v ailable sensor t yp es and lo cations, and the structure of the system graph and its solution, i.e. the resulting P areto fron t, is a highly non- linear. Moreo v er, small c hanges in the problem sp eci cation can lead to large c hanges in its solution. Consequen tly , statemen ts ab out this relationship that 29 are true in general will ha v e limited use in sp eci c instances of the sensor placemen t problem. This is exactly wh y the abilit y to e cien tly compute the P areto fron t for general plan t con guration is so v aluable. Nev ertheless, w e men tion a few general lessons that can b e learned, either through graph theoretic considerations or from the results discussed ab o v e:  Increasing the n um b er of streams without increasing the n um b er of cy- cles in the graph  e.g., b y represen ting a single pip e with t w o separate pip e sections - will lead to the same P areto fron t as long as the n um- b er of sensor candidate sensors remains the same. This is b ecause the added v ariables can b e remo v ed from an y data reconciliation problem b y simple application of the equalit y constrain ts describing the balances o v er the no de connecting the t w o pip e sections. If instead additional sensor candidates are added for ev ery added v ariable, then one should exp ect the P areto fron t to b e in the same lo cation, while man y p oin ts on the P areto fron t will con tain more sensor la y outs (larger bubbles).  Increasing the n um b er of cycles without c hanging the n um b er of streams, tends to mo v e the P areto fron t to solutions that require more measured o w rates and concen trations to ac hiev e the same lev el of observ abil- it y and redundancy . This follo ws from the idea that making a o w (comp onen t o w rate) for a particular stream observ able requires that ev ery cycle including this stream m ust ha v e at least one stream with a measured o w rate (comp onen t o w rate) or an indep enden t estimate thereof.  A dding a sensor to the set of candidate sensors for a v ariable that can b e 30 made observ able already without this sensor will increase the n um b er of la y outs in the p oin ts on the P areto fron t. Quite p ossibly , a b etter P areto fron t ma y b e obtained, e.g. if a concen tration sensor is added for a concen tration v ariable that otherwise requires a com bination of o w sensors and concen tration sensors to b ecome observ able.  As observ ed in the results section, setting w eigh ts for distinct sensor t yp es and lo cation equal to eac h other, th us indicating equal preference for an y candidate sensor leads to a large n um b er of sensor la y outs on the P areto fron t. The solicitation of stronger p