RAMP experiments in solving the uncapacitated facility location problem

• Type: Article in International Scientific Journal
• Date: 2023

Authors

Matos, T (Author) FEUP

Journal

The Journal is awaiting validation by the Administrative Services.

Title: ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE

Vol. 92

Pages: 485-504

ISSN: 1012-2443

Indexing

ISI Web of Knowledge - 0 Citations

Scopus - 0 Citations

Other information

Authenticus ID: P-00Z-R0H

DOI: 10.1007/s10472-023-09920-8

Abstract (EN): In this paper, we consider three Relaxation Adaptive Memory Programming (RAMP) approaches for solving the Uncapacitated Facility Location Problem (UFLP), whose objective is to locate a set of facilities and allocate these facilities to all clients at minimum cost. Different levels of sophistication were implemented to measure the performance of the RAMP approach. In the simpler level, (Dual-) RAMP explores more intensively the dual side of the problem, incorporating a Lagrangean Relaxation and Subgradient Optimization with a simple Improvement Method on the primal side. In the most sophisticated level, RAMP combines a Dual-Ascent procedure on the dual side with a Scatter Search (SS) procedure on primal side, forming the Primal-Dual RAMP (PD-RAMP). The Dual-RAMP algorithm starts with (dual side) the dualization of the initial problem, and then a projection method projects the dual solutions into the primal solutions space. Next, (primal side) the projected solutions are improved through an improvement method. In the PD-RAMP algorithm, the SS procedure is incorporated in the primal side to carry out a more intensive exploration. The algorithm alternates between the dual and the primal side until a fixed number of iterations is achieved. Computational experiments on a standard testbed for the UFLP were conducted to assess the performance of all the RAMP algorithms.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 20