Capacitated Facility Location

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:

- sum of the demand assigned to one facility is no greater than facility's capacity
- 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*}

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).

#include "test/test_utils/sample_graph.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

decltype(gm), decltype(facilityCapacity), decltype(clientDemand)>

VorType;

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

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

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

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.

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

Generated on Tue Jan 31 2017 00:30:51 by 1.8.5