Efficient Vertex p-Center Problem Solution

Efficient Vertex p-Center Problem Solution

Daoqin Tong, University of Arizona (daoqin@email.arizona.edu); Hu Wei, Ohio State University; Alan Murray, Ohio State University (atmurray@asu.edu)

55th Annual North American Meetings of the Regional Science Association International, 2008
63. Location Modeling IV
Session on Friday, November 21, 8:30 AM—10:10 AM

This paper explores a simple but effective approach for solving
vertex p-center problems. By introducing a neighborhood facility set,
the p-center problem can be reformulated such that many variables and
constraints are removed, yet problems characteristics, including
optimality, are preserved. The resulting problem size can be
substantially smaller than the original form, enabling the use of
general-purpose optimization software to efficiently solve medium to
large vertex p-center problem instances. Application results are
provided along with associated discussion.