Constraint programming based robust sensor network Design

The optimal placement of sensors based on different criteria, namely, precision, reliability, cost, fault unobservability has received considerable attention in literature. Most of the sensor location problems proposed in the literature have been solved either using graph theoretic approaches or the geometry based mathematical programming techniques. However, these techniques have not been able to satisfactorily address the issues of determination of global optima and the determination of all multiple globally optimal solutions despite using a large number of additional discrete variables. In this article, we show the suitability of Constraint Programming (CP), an intelligent enumeration based technique, to solve such combinatorial sensor network problems. The power of CP to efficiently model a problem with fewer variables and the ease of determination of all multiple global optima makes it highly suitable for sensor location problems. To demonstrate the expressive modeling power of CP, we have presented an efficient reformulation of the minimum unobservability problem along with the robustness criteria of Bhushan et al. [Comput. Chem. Eng. 2007, DOI:10.1016/j.compchemeng.2007.06.020]. Also, we exploit the capability of CP to solve feasibility problems for the determination of (i) multiple optima and (ii) the evaluation of tradeoffs between conflicting objectives. All these ideas have been demonstrated on the benchmark Tennessee Eastman problem using the ILOG CP solver.