The edge-based contiguous p-median problem: exact formulations and strengthening inequalities

Abstract:This paper introduces the edge-based contiguous p-median (ECpM) problem, which partitions the roads in a network into a given number of compact and contiguous territories. We develop two binary programming formulations that minimize the total network distance from each road to its assigned center node. The first uses an exponential number of cut-set contiguity (CSC) constraints and is solved with a branch-and-cut (B&C) algorithm that checks incumbent solutions for contiguity and adds violated CSC constraints as needed. The second is a compact formulation that imposes a stronger form of contiguity through shortest-path contiguity (SPC) constraints. These constraints are added up front, and the formulation is solved directly with an off-the-shelf solver. Despite this stronger requirement, we show that SPC-based ECpM has the same optimal objective value as ECpM with general contiguity and even the relaxed edge-based p-median (EpM). As a result, the SPC constraints preserve at least one optimal EpM solution and can therefore strengthen the EpM formulation. We also establish three structural properties of ECpM solutions and use them to derive three families of inequalities that further strengthen these formulations. Computational experiments on 84 instances from 14 real-world road networks show that adding the SPC constraints to EpM enables all instances to be solved to optimality and reduces solution times. In contrast, EpM without these constraints and CSC-based ECpM reach the time limit on six and eight instances, respectively. The proposed inequalities reduce both counts to one and further reduce solution times.

Artificial Intelligence (cs.AI); Discrete Mathematics (cs.DM)

arXiv:2608.11230 [cs.AI]

(or arXiv:2608.11230v2 [cs.AI] for this version)

https://doi.org/10.48550/arXiv.2608.11230 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.