Effective methods for solving the Bi-criteria p-Center and p-Dispersion problem

摘要

Given a collection of n locations and a symmetric measure of distance (difference) between each pair of locations, we seek to identify (select) a subset of p locations so as to achieve two distinct objectives. The first objective is to minimize the maximum dissimilarity (i.e., distance) between the selected locations and other locations. The second objective is to maximize the minimum distance (diversity) among the selected locations themselves. Based on the relationship between the max-min diversity problem and the node packing problem, we propose an integer programming (IP) model and a corresponding incremental algorithm to find the non-dominated frontier for this bi-criteria optimization problem. Subsequently we use the relationship between this IP model and a corresponding set-covering problem to propose effective methods for solving the former. Finally we employ the relationship between the node packing constraints and the set covering constraints to propose a new family of valid inequalities for the corresponding IP models that are potentially effective when solving large instances of these models. Through computational experiments we demonstrate the effectiveness of our proposed methods for solving relatively large instances of this bi-criteria optimization problem. (C) 2018 Elsevier Ltd. All rights reserved.