An Integer Programming Approach for Angular Coverage under Uncertainty

This paper investigates angular coverage under uncertainty (ACU). A compact integer programming (IP) formulation is developed to model the angular field-of-view (FoV) of sensors and probabilistic coverage under uncertainty. The IP formulation minimizes the weighted non-coverage probability over the target set as well as considering the practical colocation and budget constraints. Recognizing the non-linearity, non-convexity, and non-separability of ACU, we first introduce the reformulation-linearisation technique (RLT) to obtain a tractable mixed-integer linear programming model which provides a tight lower bound for the original problem. Further, we exploit the structure of the mathematical model and customize a branch-and-cut (B&C) algorithm to solve the derived problem exactly. We show that the solution for the derived problem can also solve the original problem based on the bounding scheme. Computational experiments on a series of problem instances ranging from moderate to large size scaling up to 4,000 dimensional decision variables reveal the effectiveness and efficiency of the proposed exact approach.