K-Median

Problem definition.

In facility location we have set of possible facilities locations, set of clients and the number k. 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 k open facilities and assign each client to some set of open facilities to minimize 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)\\ where:&\\ &\forall_{i}\sum_j{x_{ij}} = 1\\ &\forall_{i,j}x_{ij} \le y_j\\ &\sum_{j}y_j = k\\ &x_{ij} \in \{0,1\}\\ &y_j \in \{0,1\}\\ \end{eqnarray*}

Solution

Facility Location (FL) problem is solved by local search. Given a move which opens one facility and close one facility, we check if the move can our solution, if yes, we apply the move.(see paal::local_search::facility_location::KMedianLocalSearchStep for more details). Current solution to the assignment problem (assign clients to chosen facilities) is kept in the class which models Voronoi concept, where generators are facilities and vertices are clients.

Example

#include "test/test_utils/sample_graph.hpp"

#include "paal/local_search/k_median/k_median.hpp"
#include "paal/data_structures/facility_location/fl_algo.hpp"

#include <iostream>

int main() {
    // sample data
    typedef sample_graphs_metrics SGM;
    auto gm = SGM::get_graph_metric_small();

    // define voronoi and solution
    const int k = 2;
    typedef paal::data_structures::voronoi<decltype(gm)> VorType;
    typedef paal::data_structures::k_median_solution<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{ SGM::B, SGM::D },
                    VSet{ SGM::A, SGM::B, SGM::C, SGM::D, SGM::E }, gm);
    Sol sol(std::move(voronoi), USet{ SGM::A, SGM::C }, k);

    // create facility location local search step
    paal::local_search::default_k_median_components swap;

    // search
    paal::local_search::facility_location_first_improving(
        sol, swap);

    // print result
    auto const &ch = sol.get_chosen_facilities();
    std::cout << "Solution:" << std::endl;
    std::copy(ch.begin(), ch.end(), std::ostream_iterator<int>(std::cout, ","));
    std::cout << std::endl << "Cost " << paal::simple_algo::get_km_cost(gm, sol)
              << std::endl;

    std::cout << std::endl;

    return 0;
}

example file is k_median_example.cpp

Approximation Ratio equals 5.

Complexity

The complexity of the computing the gain for each move equals complexity of the swap for facility location (see Facility Location).

References

The algorithm an analises is described in [2]