An effective heuristic for large-scale fault-tolerant k-median problem

Autor: Nadezhda Maltugueva, Anton V. Ushakov, Igor Vasilyev, Antonio Sforza
Rok vydání: 2018
Předmět:
Zdroj: Soft Computing. 23:2959-2967
ISSN: 1433-7479
1432-7643
Popis: We address a general fault-tolerant version of the k-median problem on a network. Unlike the original k-median, the objective is to find k nodes (medians or facilities) of a network, assign each non-median node (customer) to $$r_j$$ distinct medians, and each median nodes to $$r_j-1$$ other medians so as to minimize the overall assignment cost. The problem can be considered in context of the so-called reliable facility location, where facilities once located may be subject to failures. Hedging against possible disruptions, each customer is assigned to multiple distinct facilities. We propose a fast and effective heuristic rested upon consecutive searching for lower and upper bounds for the optimal value. The procedure for finding lower bounds is based on a Lagrangian relaxation and a specialized effective subgradient algorithm for solving the corresponding dual problem. The information on dual variables is then used by a core heuristic in order to determine a set of primal variables to be fixed. The effectiveness and efficiency of our approach are demonstrated in a computational experiment on large-scale problem instances taken from TSPLIB. We show that the proposed algorithm is able to fast find near-optimal solutions to problem instances with almost 625 million decision variables (on networks with up to 24978 vertices).
Databáze: OpenAIRE
Externí odkaz: