Mathematical Programming Computation, Volume 6, Number 3, September 2014

Font Size:  Small  Medium  Large

An exact cooperative method for the uncapacitated facility location problem

Marius Posta, Jacques A. Ferland, Philippe Michelon

Abstract


In this paper, we present a cooperative primal-dual method to solve the uncapacitated facility location problem exactly. It consists of a primal process, which performs a variation of a knownand effective tabu search procedure, and a dual process, which performs a lagrangian branch-and-bound search. Both processes cooperate by exchanging information which helps them find the optimal solution. Further contributions include new techniques for improving the evaluation of the branch-and-bound nodes: decision-variable bound tightening rules applied at each node, and a subgradient caching strategy to improve the bundle method applied at each node.

Full Text: pdf

mpc footer
© MPS 2008-2017