(569al) Globally Optimal Sensor Network Design Revisited: Application of the Generalized Bender Decomposition

In a series of papers [1, 2, 3] the problem of optimal sensor selection for linear systems has been shown to be of the Mixed Integer Convex Programming (MICP) class. While the use of such formulations has opened the door to a guarantee of global optimality, the use of a branch and bound search procedure has limited application of this approach to fairly small systems. The particular bottleneck can be attributed to the fact that during each iteration of the branch and bound search a fairly slow Semi-Definite Programming (SDP) problem needed to be solved to it global optimum.

In this work, we illustrate that a simple reformulation of the MICP and subsequent application the Generalized Benders Decomposition (GBD) will result in massive reductions in computational effort. While the resulting algorithm must solve multiple Mixed Integer Linear Programs (MILPs), this increase in computational effort is significantly outweighed by the reduction in the number of SDP problems one must solve. The approach will be illustrated using steady-state type processes (that use data reconciliation based estimation) as well as closed-loop dynamic process (that Kalman filtering based estimation).

[1] Chmielewski D. J., T. Palmer and V. Manousiouthakis, "On the Theory of Optimal Sensor Placement," AIChE J., 48(5), pp 1001-1012, (2002).

[2] Peng, J.K., and D.J. Chmielewski, "Covariance Based Hardware Selection-Part II: Equivalence Results for the Sensor, Actuator and Simultaneous Selection Problems," IEEE Trans. Cont. Sys. Tech., 14(2), pp 362-368, (2006).

[3] Ahmed S.K., J.-K. Peng, and D.J. Chmielewski, "Covariance-Based Hardware Selection-Part III: Distributed Parameters Systems" AIChE J.,58(9), pp 2705-2713, (2012).