Solving the p-Median Problem with a Semi-Lagrangian Relaxation |
| |
Authors: | C Beltran C Tadonki J Ph Vial |
| |
Institution: | (1) Logilab, HEC, University of Geneva, Switzerland;(2) Centre Universitaire Informatique, University of Geneva, Switzerland |
| |
Abstract: | Lagrangian relaxation is commonly used in combinatorial optimization to generate lower bounds for a minimization problem.
We study a modified Lagrangian relaxation which generates an optimal integer solution. We call it semi-Lagrangian relaxation
and illustrate its practical value by solving large-scale instances of the p-median problem.
This work was partially supported by the Fonds National Suisse de la Recherche Scientifique, grant 12-57093.99 and the Spanish
government, MCYT subsidy dpi2002-03330. |
| |
Keywords: | Lagrangian relaxation combinatorial optimization p-median problem |
本文献已被 SpringerLink 等数据库收录! |