(362w) Cover Cut Based Algorithm for Optimal Sensor Network Design

Sensors are vital for fault detection and diagnosis, process monitoring, etc. They aid us in the monitoring and control of crucial process variables whose measurements are often difficult to acquire because of lack of availability of sensors, or technical difficulties in sensor placement. Hence, the optimal placement of sensors is essential to achieve a high degree of precision (or alternatively, reliability) in the estimation of process variables. Sensor placement based on optimization approaches are quite common due to the rigorous mathematical formulations. Some of the sensor network design cost metrics include minimizing the overall estimation error of process variables, minimizing the average operational loss due to measurement errors, or more recently, minimizing the Kullback-Leibler divergence of the estimation errors of a sensor network given the estimation errors when all sensors are placed.

All the above-mentioned sensor network optimization problems are combinatorial problems that are generally hard to solve. For example, in the case of a steam metering network, that has 28 flow streams and 11 sensors to measure them, the total number of network combinations are ²⁸C₁₁ (approximately 2 X 10⁷ combinations), out of which a large number of networks would be observable while the rest are unobservable. Since the number of combinations of sensor networks is large, enumeration of all possible observable sensor networks in such cases is not feasible. Hence, we formulate the sensor placement problem as a Mixed-Integer Programming (MIP) problem. Specifically, following the work of [1], the sensor placement problem is formulated based on the notion of average estimation error as a Mixed-Integer Cone Program (MICP). Also, sensor placement based on average loss has been formulated as a MICP. Since the relaxed problem results in a cone program, which is convex in nature, it can be solved to global optimality efficiently. However, the original MICP with integrality constraints is difficult to solve and therefore, a branch and bound method is often used to find the optimal integer solution. Owing to the large number of combinations for even a moderately sized steam metering network, a typical branch and bound algorithm will pose computational challenges. Therefore, in this work, we adopt a cutting-plane based solution algorithm to solve the optimal sensor placement problem.

The cutting plane algorithm uses the idea of tightening the feasible area of solutions until an optimal solution is reached. It is an iterative algorithm that successively incorporates valid inequalities (also known as cuts) to eliminate the non-integer optimal solution of the relaxed problem, but retains the optimal integer solution of the original problem. There exist multiple ways to generate valid cuts like Gomory cuts, Kelly cuts, cover cuts, disjunctive cuts, etc. However, the choice of cuts will play a major role in the solution progression. In other words, the chosen cut will affect the number of iterations required for convergence, and thus the computational efficiency. Usually, the addition of cuts is done in two steps; first, a list of all valid cuts is generated and then the strongest cuts among them are added to the relaxed cone problem.

The present work utilizes cover cuts in the cutting plane framework for solving the MICP formulation of the sensor network design problem. For formulations that involve binary decision variables, cover cuts are one of the simplest yet effective cutting planes that tighten the polyhedral domain of the MICP problem. We start with the cardinality constraint of the minimum observable sensor network design problem to derive the cover cuts. Different metrics such as depth-of-cut, dimensional face and volume cut-off have been developed to assess the strength of valid inequalities among the generated cover cuts. One of these measures will be used to select the appropriate cover cut such that fewer iterations are required to obtain the optimal sensor network design. We demonstrate the computational efficacy of the proposed cover cut based solution methodology in the optimal design of sensor networks in a benchmark steam metering system, and compare its performance with standard solvers.

Reference(s)