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 "paal/local_search/facility_location/facility_location.hpp"
#include "paal/utils/functors.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 };
    typedef paal::utils::array_to_functor<std::vector<int>> Cost;

    // define voronoi and solution
    typedef paal::data_structures::voronoi<decltype(gm)> VorType;
    typedef paal::data_structures::facility_location_solution<Cost, VorType>
        Sol;
    typedef paal::data_structures::voronoi_traits<VorType> VT;
    typedef VT::GeneratorsSet GSet;
    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 },
            paal::utils::make_array_to_functor(fcosts));

    // create facility location local search components
    default_remove_fl_components rem;
    default_add_fl_components add;
    default_swap_fl_components swap;

    // search
    facility_location_first_improving(sol, rem, add, swap);

    // 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

Approximation Ratio equals 3.

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]