##
471504 MINLP Formulation and Global Solution Approach for Sensor Placement with Non-Uniform Failure Probabilities: Application to Gas Detection Systems

In the last decade, a large body of literature has focused on developing stochastic programming (SP) based approaches to solve many real-world sensor placement problems [1, 2, 4-7]. However, most of the previous problem formulations have assumed perfect sensors. In reality, detectors are imperfect and subject to unpredictable failures, which may be caused by poor maintenance, erroneous calibration, or power outage. In many cases, these imperfections can significantly impact the performance of the entire detector system. To design a sensor system with high reliability, therefore, it is necessary to explicitly consider sensor unavailability, i.e., the probability of a false-negative detection. Berry et al. [4] first proposed a SP-based imperfect-sensor model for water contamination warning systems. Inspired by this seminal work, Benavides-Serrano et. al. [1, 3] proposed SP formulations for flammable gas detection and mitigation systems considering sensor unavailabilities. However, the resulting sensor placement problems, formulated as large-scale mixed-integer nonlinear programming (MINLP) problems, are very challenging to solve due to strong nonlinearities and discrete variables. To solve these optimization problems efficiently, thus, there is a need for new problem formulations and solution strategies.

To reduce the inherent nonlinearities in the original MINLP formulation [4], in this work, we present a mathematically equivalent formulation based on log-transformation. Though new variables and constraints are introduced, this alternative formulation is mathematically preferable since all its nonlinearity comes from convex univariate terms. To solve this reformulation to global optimality, we propose a multitree method which depends on iteratively solving a sequence of upper bounding master problems and lower bounding subproblems. The master problem, which is formulated as a mixed-integer linear programming (MILP) problem, is a strict convex relaxation of our alternative formulation. To obtain a relatively tight and computationally efficient master problem, we introduce linear outer approximations and tight, problem specific, upper bounding constraints. The upper bounding problem is obtained by fixing all binary variables, which, in this case, results in a subproblem that can be directly computed with a single forward simulation. Our tailored global solution strategy is tested on a number of real data problems. The encouraging numerical results indicate that our solution framework is promising in solving sensor placement problems.

Bibliography

[1] Benavides-Serrano, A. J., Legg, S. W., Vázquez-Román, R., Mannan, M. S., & Laird, C. D. (2013). A Stochastic Programming Approach for the Optimal Placement of Gas Detectors: Unavailability and Voting Strategies. Industrial & Engineering Chemistry Research, 53(13), 5355-5365.

[2] Benavides-Serrano, A. J., Mannan, M. S., & Laird, C. D. (2015). A quantitative assessment on the placement practices of gas detectors in the process industries. Journal of Loss Prevention in the Process Industries, 35, 339-351.

[3] Benavides‐Serrano, A. J., Mannan, M. S., & Laird, C. D. (2016). Optimal placement of gas detectors: AP‐median formulation considering dynamic nonuniform unavailabilities. AIChE Journal.

[4] Berry, J., Carr, R. D., Hart, W. E., Leung, V. J., Phillips, C. A., & Watson, J. P. (2009). Designing contamination warning systems for municipal water networks using imperfect sensors. Journal of Water Resources Planning and Management, 135(4), 253-263.

[5] Berry, J., Carr, R. D., Hart, W. E., Leung, V. J., Phillips, C. A., & Watson, J. P. (2009). Designing contamination warning systems for municipal water networks using imperfect sensors. Journal of Water Resources Planning and Management, 135(4), 253-263.

[6] Legg, S. W., Wang, C., Benavides-Serrano, A. J., & Laird, C. D. (2013). Optimal gas detector placement under uncertainty considering Conditional-Value-at-Risk. Journal of Loss Prevention in the Process Industries, 26(3), 410-417.

[7] Legg, S. W., Benavides-Serrano, A. J., Siirola, J. D., Watson, J. P., Davis, S. G., Bratteteig, A., & Laird, C. D. (2012). A stochastic programming approach for gas detector placement using CFD-based dispersion simulations. Computers & Chemical Engineering, 47, 194-201.

**Extended Abstract:**File Not Uploaded

See more of this Group/Topical: Computing and Systems Technology Division