2019 journal article

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

COMPUTERS & OPERATIONS RESEARCH, 101, 43–54.

By: G. Tutunchi* & Y. Fathi n

author keywords: Location; Max-min diversity; p-center partitioning; Integer programming; Valid inequalities
TL;DR: An integer programming (IP) model is proposed and a corresponding incremental algorithm is proposed to find the non-dominated frontier for this bi-criteria optimization problem and a new family of valid inequalities for the corresponding IP models that are potentially effective when solving large instances of these models are proposed. (via Semantic Scholar)
Source: Web Of Science
Added: November 26, 2018

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.