2020 journal article

Representative subsets of non-dominated points in the bi-criteria p-median p-dispersion problem

COMPUTERS & INDUSTRIAL ENGINEERING, 146.

By: G. Tutunchi* & Y. Fathi n‚ÄČ

author keywords: Bi-criteria optimization; Representative subset; Location theory; Max-min diversity; p-median partitioning
TL;DR: A new criterion (index) is introduced to evaluate the effectiveness of a representative subset of non-dominated points in the context of the Bi-criteria p-Median p-Dispersion problem (BpMD) and provides an upper bound on the relative gap between the representing NDP and any NDP that it represents. (via Semantic Scholar)
Source: Web Of Science
Added: August 3, 2020

One way to reduce the computational burden of solving a bi-criteria optimization problem would be to obtain only a subset of its non-dominated points (NDPs) as representative for the entire collection. We introduce a new criterion (index) to evaluate the effectiveness of a representative subset of non-dominated points in the context of the Bi-criteria p-Median p-Dispersion problem (BpMD). A key difference between our proposed index and those previously introduced in the open literature is that in those indexes the distance between an arbitrary NDP and its nearest NDP in the representative subset is determined along the direction of both objective functions, while in our proposed index this distance is determined only along the objective function for which the representing NDP is worst than the represented NDP. Along this direction, the proposed index provides an upper bound on the relative gap between the representing NDP and any NDP that it represents. We then employ this index to design an algorithm to find a representative subset of NDPs for the problem BpMD and demonstrate its effectiveness through a computational experiment. Although we develop this index in the context of the problem BpMD, it is potentially applicable in the context of other bi-criteria optimization problems as well.