{"ID":2838545,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.17128","arxiv_id":"2511.17128","title":"An efficient branch-and-cut algorithm for the multiple probabilistic covering location problem","abstract":"In this paper, we consider the multiple probabilistic covering location problem (MPCLP), which attempts to open a fixed number of facilities to maximize the total covered customer demand under a joint probabilistic coverage setting. We present a new mixed integer nonlinear programming (MINLP) formulation, and develop an efficient linear programming (LP) based branch-and-cut (B\u0026C) algorithm where submodular and outer-approximation inequalities are used to replace the nonlinear constraints and are separated at the nodes of the search tree. One key advantage of the proposed B\u0026C algorithm is that the number of variables in the underlying formulation grows only linearly with the number of customers and facility locations and is one-order of magnitude smaller than that in the underlying formulation of a state-of-the-art B\u0026C algorithm in the literature. Moreover, we propose two new families of strong valid inequalities, called enhanced outer-approximation and lifted subadditive inequalities, to strengthen the LP relaxation and speed up the convergence of the proposed B\u0026C algorithm. In extensive computational experiments on a testbed of 240 benchmark MPCLP instances, we show that, thanks to the small problem size and the strong LP relaxation of the underlying formulation, the proposed B\u0026C algorithm significantly outperforms a state-of-the-art B\u0026C algorithm in terms of running time, number of nodes in the search tree, and number of solved instances. In particular, using the proposed B\u0026C algorithm, we are able to provide optimal solutions for 57 previously unsolved benchmark instances within a time limit of one hour.","short_abstract":"In this paper, we consider the multiple probabilistic covering location problem (MPCLP), which attempts to open a fixed number of facilities to maximize the total covered customer demand under a joint probabilistic coverage setting. We present a new mixed integer nonlinear programming (MINLP) formulation, and develop a...","url_abs":"https://arxiv.org/abs/2511.17128","url_pdf":"https://arxiv.org/pdf/2511.17128v1","authors":"[\"Yan-Ru Wang\",\"Wei-Kun Chen\",\"Ivana Ljubić\"]","published":"2025-11-21T10:44:21Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}