This work studies the problem of optimally locating sensors for monitoring chemical processes, formally known as the sensor network design and upgrade problem. This problem is an integer programming problem and has been solved to global optimality only using tree search methods using depth-first strategy. In this article, we exploit certain cost properties of the different nodes in the tree to efficiently prune nonoptimal nodes using a breadth-first/level traversal tree search method to obtain the global optimum. We show that this strategy allows cutting considerably the computational time for problems that the depth-first strategy was inefficient. (C) 2010 American Institute of Chemical Engineers AIChE J, 57: 1302-1309, 2011