Facility Location

Problem definition.

In the facility location problem we have a set of possible facilities locations and set of clients. Each facility j has a specific facilityCost(j), additionally for each client i and facility j, there is a cost of assigning i to j, m(i,j) (the transportation cost). The goal is to determine the set of open facilities and assign each client to some set of open facilities to minimize the sum of the cost of the open facilities (production cost) and the cost of assigning clients (the transportation cost).

More formally, let $$x_{ij}$$ indicates if client i is assigned to facility j and $$y_i$$ indicates if the facility is open, we want to minimize

\begin{eqnarray*}&\sum_{x_{ij}}x_{ij} * m(i,j) + \sum_{y_i}y_i * facilityCost(i) \\ where:&\\ &\forall_{i}\sum_j{x_{ij}} = 1\\ &\forall_{i,j}x_{ij} \le y_j\\ &x_{ij} \in \{0,1\}\\ &y_j \in \{0,1\}\\ \end{eqnarray*}

Solution

Facility Location (FL) problem is solved by local search. For given solution we consider some set of moves. For each move we check if the move can our solution, if yes we apply the move. The set of chosen moves is adding facility to the current solution, removing facility to the current solution and swapping facility form solution with some currently closed facility (see paal::local_search::facility_location::FacilityLocationLocalSearchStep for more details). Current solution to the assignement problem (assign clients to chosen facilities) is kept in the class which models Voronoi conecpt, where generators are facilities and vertices are clients.

Example

#include "test/test_utils/sample_graph.hpp"
#include <boost/range/algorithm/copy.hpp>
#include <iostream>
using namespace paal::local_search;
int main() {
// sample data
typedef sample_graphs_metrics SGM;
auto gm = SGM::get_graph_metric_small();
std::vector<int> fcosts{ 7, 8 };
// define voronoi and solution
Sol;
typedef VT::VerticesSet VSet;
typedef Sol::UnchosenFacilitiesSet USet;
// create voronoi and solution
VorType voronoi(GSet{}, VSet{ SGM::A, SGM::B, SGM::C, SGM::D, SGM::E }, gm);
Sol sol(std::move(voronoi), USet{ SGM::A, SGM::B },
// create facility location local search components
// search
// print result
boost::copy(sol.get_chosen_facilities(), std::ostream_iterator<int>(std::cout, ","));
std::cout << std::endl;
return true;
}

example file is facility_location_example.cpp

Complexity

The complexity of cheking the gain of the add equals $fO(|Clients|)$f. Although the complexity of checking the gain of the remove operation of algorithm equals to $$O(|Clients| * |Facilities|)$$, the amortized cost of this check for each facility is $$O(|Clients| * |Facilities|)$$. Swap operation is performed by one add and one remove.

References

The algorithm an analises is described in [2]