Capacitated Facility Location

Problem definition.

In capacitated facility location we have set of possible facilities locations, set of clients. Each client i has specific demand clientDemand(i), each facility j has specific capacity facilityCapacity(j) and facilityCost(j), additionally for each client i and facility j, there is a cost per unit of assigning i to j, m(i,j) (the transportation cost). The goal is to determine the set of open facilities and assign the demand of each client to some set of open facilities in such a way that:

1. sum of the demand assigned to one facility is no greater than facility's capacity
2. minimize the sum of the cost of the open facilities (production cost) and the cost of assigning clients demands (the transportation cost).

More formally, let \(x_{ij}\) denote the demand assigned by client i 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}} = clientDemand(i)\\ &\forall_{j}\sum_{i}x_{ij} \le facilityCapacity(j)\\ &x_{ij} \ge 0\\ &y_j \in \{0,1\}\\ \end{eqnarray*}

Solution

Capacitated Facility Location (CFL) problem is solved in the same way as uncapacitated facility location (see paal::local_search::facility_location::FacilityLocationLocalSearchStep). The only difference is that we use capacitated version of the voronoi (see paal::data_structures::CapacitatedVoronoi).

Example

#include "test/test_utils/sample_graph.hpp"

#include "paal/local_search/facility_location/facility_location.hpp"
#include "paal/data_structures/voronoi/capacitated_voronoi.hpp"
#include "paal/utils/functors.hpp"

using namespace paal::local_search;

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

    std::vector<int> fcostsv{ 7, 8 };
    auto facilityCost = paal::utils::make_array_to_functor(fcostsv);

    std::vector<int> fcapv{ 2, 2 };
    auto facilityCapacity = paal::utils::make_array_to_functor(fcapv);

    std::vector<int> cdemv{ 2, 2, 1, 3, 3 };
    auto clientDemand = paal::utils::make_array_to_functor(cdemv);

    // define voronoi and solution
    typedef paal::data_structures::capacitated_voronoi<
        decltype(gm), decltype(facilityCapacity), decltype(clientDemand)>
        VorType;
    typedef paal::data_structures::facility_location_solution<
        decltype(facilityCost), 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::A },
                    VSet{ SGM::A, SGM::B, SGM::C, SGM::D, SGM::E }, gm,
                    facilityCapacity, clientDemand);
    Sol sol(std::move(voronoi), USet{ SGM::B }, facilityCost);

    // search
    facility_location_first_improving(sol, default_remove_fl_components(),
                                      default_add_fl_components(),
                                      default_swap_fl_components());

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

    return 0;
}

example file is capacitated_facility_location_example.cpp

Approximation Ratio equals 6.

The approximation ratio is proved to be equal 6 when we use all three move types: add, remove and swap.

Complexity

The complexity of cheking the gain of the add and the gain of the remove operation of algorithm equals to the complexity of the min_cost_max_flow on the graph with number of edges equals \(O(|Clients| |Facilities|)\) and number of vertices equals \(O(|Clients| + |Facilities|)\). Currently we use boost::successive_shortest_path_nonnegative_weights (to appear). Swap operation is performed by one add and one remove.

References

The algorithm is described in the [11]. The Approximation ratio analysis is in [6].