Primal-dual variable neighborhood search for the simple plant-location problem. (English) Zbl 1241.90072

Summary: The variable neighborhood search metaheuristic is applied to the primal simple plant-location problem and to a reduced dual obtained by exploiting the complementary slackness conditions. This leads to (i) heuristic resolution of (metric) instances with uniform fixed costs, up to \(n=15,000\) users, and \(m=n\) potential locations for facilities with an error not exceeding \(0.04\%\); (ii) exact solution of such instances with up to \(m=n=7,000\); and (iii) exact solutions of instances with variable fixed costs and up to \(m=n=15,000\).


90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI Link