Страница публикации

An aggregation heuristic for large scale p-median problem

Авторы: Avella P., Boccia M., Salerno S., Vasilyev I.

Журнал: Computers & Operations Research

Том: 39

Номер: 7

Год: 2012

Отчётный год: 2012

Издательство:

Местоположение издательства:

URL:

Проекты:

DOI: 10.1016/j.cor.2011.09.016

Аннотация: The p-median problem (PMP) consists of locating p facilities (medians) in order to minimize the sum of distances from each client to the nearest facility. The interest in the large-scale PMP arises from applications in cluster analysis, where a set of patterns has to be partitioned into subsets (clusters) on the base of similarity. In this paper we introduce a new heuristic for large-scale PMP instances, based on Lagrangean relaxation. It consists of three main components: subgradient column generation, combining subgradient optimization with column generation; a "core" heuristic, which computes an upper bound by solving a reduced problem defined by a subset of the original variables chosen on a base of Lagrangean reduced costs; and an aggregation procedure that defines reduced size instances by aggregating together clients with the facilities. Computational results show that the proposed heuristic is able to compute good quality lower and upper bounds for instances up to 90,000 clients and potential facilities.

Индексируется WOS: Q1

Индексируется Scopus: Нет

Индексируется УБС: Нет

Индексируется РИНЦ: Да

Индексируется ВАК: Нет

Индексируется CORE: Нет

Публикация в печати: 0