780. MILP Models for the Planar p-Median Problem: An Evaluation of Different Linear Approximation Techniques of Euclidean Distances
Invited abstract in session TC-20: Exact algorithms for combinatorial optimization, stream Combinatorial Optimization.
Tuesday, 12:30-14:00Room: Esther Simpson 2.11
Authors (first author is the speaker)
| 1. | Fabian Wilschewski
|
| Mercator School of Management, University of Duisburg-Essen | |
| 2. | Alf Kimms
|
| Mercator School of Management, University of Duisburg-Essen, Campus Duisburg | |
| 3. | Christin Münch
|
| Mercator School of Management, University of Duisburg-Essen |
Abstract
The planar p-median problem consists of locating a given number of facilities in the plane in order to minimize the sum of Euclidean distances from given demand points to its closest facility. As the problem has various applications, it has already received a lot of attention and many variants of the problem have been addressed. A major part of proposed solution methods are iterative approximation algorithms and heuristics. However, these methods are often closely related to a specific problem variant, whereby minor changes to the problem definition or new conditions may render an algorithm completely unusable or require a lot of effort to adapt it appropriately. In contrast, model-based approaches are typically more flexible, so that additional conditions can often be easily implemented. In order to utilize this advantage, we present different approximation techniques that enable the use of MILP model formulations.
Moreover, we evaluate the performance of the proposed techniques in terms of solve time and approximation accuracy within the framework of MILP model formulations for the planar p-median problem. The results may also be valuable for related problems or other applications including Euclidean distances.
Keywords
- Location
- Programming, Mixed-Integer
Status: accepted
Back to the list of papers