inicioir al DIIbuscar
dual-based local search for the robust connected facility location problem

The connected facility location (ConFL) problem arises in a number of applications that relate to the design of telecommunication networks as well as data distribution and management problems on networks. It combines features of the uncapacitated facility location problem with the Steiner tree problem and is known to be NP-complete. In this setting, we wish to install a set of facilities on a communication network and assign customers to the installed facilities. In addition, the set of selected facilities needs to be connected by a Steiner tree.

In this presentation, we describe our dual-based local search (DLS) heuristic that combines dual ascent and local search, which together yield strong lower and upper bounds to the optimal solution. We briefly discuss some of our computational experiments that indicate that our heuristic is a very effective procedure that finds high-quality solutions very rapidly for deterministic problems.

Lastly, in real world applications it is often costly to estimate the current and future location of customers and their demand. Consequently, we introduce uncertainty in customer assignment costs and investigate the effects of uncertainty on the optimal solution. We present a robust optimization formulation for the ConFL problem and show how a variant of the DLS heuristic can be effectively used to solve its robust counterpart. We present computational results that demonstrate that the DLS heuristic also reaches very rapidly high-quality solutions for the robust problem.