Comparing dual access approaches for exact solution of location problems

Abstract

The paper deals with exact solution of two uncapacitated location problems. The location problem consists in placing some facilities of unrestricted capacity in the formed network. The facility can have various natures. It could be aservice centre, whose location can be done at anode of the network, or it can be adirect train, which can be placed into a transport plan. In comparison with the former case, this facility has the nature of a graph edge.
The key-stone of the computational success of the often used branch and bound method is the lower bound tightness. This paper, reports numerical experiments with the dual access approach used for the solution of the node location problem in a large network and compares several possible approaches to lower bound enumeration for the edge location problem.