Facility location

A facility location problem (FL) is an optimization problem in which it is a question of selecting a subset of a number of locations as supply locations so that these are optimally placed under the given conditions. Finding such subsets exactly is considered algorithmically difficult and is generally NP-difficult .

introduction

Applications of the facility location are very diverse. Optimal locations of hospitals for health care can be determined, for example the question of the location of factories arises for companies, but also in the course of the constantly advancing expansion of the Internet the question of the clever positioning of servers arises.

In general, an FL can be formulated as follows: From the given quantities of consumers and providers and given costs, a subset should be found from the set of providers so that each consumer is supplied by exactly one provider and the costs are minimized. Another variant of an FL arises when it is required that every consumer is supplied by at least one provider.

The costs are made up of the paired connection costs between consumers and providers and the costs for opening and / or operating a provider.

Image 1: The branches of a supermarket chain Image 2: The possible locations of the central warehouse (red) Image 3: One possibility of assignment Image 4: Another possibility of assignment

example

The branches of a supermarket chain are to be assigned central warehouses in which the products are stored and then delivered to the individual branches. The delivery routes should be minimized. The connection costs are therefore calculated directly from the distance between the branch and the location . The costs of opening a location can consist of the construction costs, the land costs and the maintenance costs. With the maintenance costs, location advantages and disadvantages such as local wage costs etc. would also be taken into account.

{\ displaystyle c_ {ij}}

{\ displaystyle i}

{\ displaystyle j}

Depending on the level of the costs of the various locations, it can be cheaper to open just one location and thus to bear higher transport costs until then to open each of the possible locations.

For this example there are more than 10 quadrillion possible combinations ( combinatorial explosion ). A modern computer would need more than 300 years for direct calculation.

Modeling

A FL is usually modeled as a complete bipartite graph , where the bipartion is the union of the two disjoint sets of the providers (facilities) and the consumers (customers). In addition, two positive figures (connection costs) and (opening / operating costs) are defined. If an extended triangle inequality applies to the cost function , one speaks of the metric facility location problem: ${\ displaystyle G = (V, E)}$ ${\ displaystyle V}$ ${\ displaystyle F}$ ${\ displaystyle C}$ ${\ displaystyle c \ colon F \ times C \ to \ mathbb {R} _ {0} ^ {+}}$ ${\ displaystyle f \ colon F \ to \ mathbb {R} _ {0} ^ {+}}$ ${\ displaystyle c}$

{\ displaystyle c (i, j): = c_ {ij} \ leq c_ {ij '} + c_ {i'j} + c_ {i'j'} \ \ forall i, i '\ in F, j, j '\ in C}

.

We are looking for a subset and an assignment that ${\ displaystyle F '\ subseteq F}$ ${\ displaystyle \ phi \ colon C \ to F '}$

{\ displaystyle \ sum _ {i \ in F '} f_ {i} + \ sum _ {j \ in C} c _ {\ phi (j) j}}

minimized.

Solvability

Since facility location is an NP-difficult problem, approximation algorithms are used for the solution . In contrast to the metric facility location problem, which can be approximated with constant quality, the general facility location problem (in which the triangle inequality does not have to apply) cannot be better than approximated. The following are some approximation algorithms that approximate the metric facility location problem with constant quality: ${\ displaystyle {\ mathcal {O}} (\ log n)}$

Jain-Vazirani algorithm

In 2001 Kamal Jain and Vijay Vazirani presented an algorithm based on a primal-dual variant of a linear program . They were able to prove that the result is a 3-approximation, i.e. at most three times worse than the optimum. The running time of the algorithm is , with . ${\ displaystyle {\ mathcal {O}} (m \ log m)}$ ${\ displaystyle m = \ left | E (G) \ right |}$

Mahdian-Ye-Zhang algorithm

Mohammad Mahdian, Yinyu Ye and Yiawei Zhang published a variant of a greedy algorithm in 2002 , which approximates a solution to an FL problem with the quality . The much better factor by which the solution differs from the optimum must, however, be paid for with a higher runtime ( , with ) than that of the Jain-Vazirani algorithm. ${\ displaystyle 1 {,} 52}$ ${\ displaystyle {\ mathcal {O}} (n ^ {3})}$ ${\ displaystyle n = \ left | V (G) \ right |}$

literature

Vašek Chvátal: Linear Programming. WH Freeman and Company, New York, 1983, ISBN 0-7167-1587-2

Individual evidence

[1] Kamal Jain, Vijay V. Vazirani: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. Journal of the ACM. 48 (2001). Pp. 274-296.

[2] Mohammad Mahdian, Yinyu Ye, Yiawei Zhang: Improved Approximation Algorithms for Metric Facility Location Problems. 2002