Rank-Constrained Mixed-Integer Optimization for Heterogeneous Sensor Location in Route Reconstruction

In this paper, we introduce a mixed-integer rank-constrained optimization model for the route reconstruction–oriented heterogeneous sensor location problem. Although rank constraints are generally nonconvex and not mixed-integer convex representable, we demonstrate that this model is equivalent to a mixed-integer linear optimization model by leveraging the structure of the rank constraints. To enhance computational efficiency, we first propose an exact logic–based Benders decomposition algorithm with an enhanced master problem and tailored feasibility cuts. For large-scale instances, we further present a scalable two-step heuristic, where we first develop an upper bound of the mixed-integer optimization model and then eliminate surplus sensors by a greedy approach. Numerical results show that our logic-based Benders decomposition algorithm is up to two orders of magnitude faster than state-of-the-art commercial solvers. In addition, the two-step heuristic approach exhibits superior scalability while maintaining acceptable solution quality compared with exact methods on large-scale instances. It also consistently outperforms benchmark approaches in terms of computation time and solution quality. Overall, our models lead to substantial reductions in investment costs—achieving savings of 5.56%–24.81% in small-scale networks and 8.51%–42.60% and 2.62%–32.75% in medium and large-scale networks, respectively, relative to the classic route differentiation benchmark.

History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods and Analysis.

Funding: The research of C. Fu is supported by the National Natural Science Foundation of China [Grants 72401229, 72310107003, and 72271201]. L. Chen acknowledges support from the Emerging Scholar Research Fellowships, University of Sydney Business School.

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0965) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.0965). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.