Using the power of ideal solutions: simple proofs of some old and new results in location theory
- PDF / 466,263 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 88 Downloads / 139 Views
Using the power of ideal solutions: simple proofs of some old and new results in location theory Frank Plastria1 Received: 7 January 2020 / Revised: 6 August 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract When all objectives have a common minimum the existence of this ideal solution directly yields all efficient solutions of the corresponding multi-objective problem, as well as all minimising solutions of any positively weighted sum of these objectives. Some of the classical results in location theory are easy consequences of this simple property, while the same methodology also leads to some lesser known or new results. Keywords Multiobjective optimisation · Ideal solution · 1-Median · Majority · Median · MAD · Norm Mathematics Subject Classification 90B85 · 90C29 · 90 01
1 Introduction In multiobjective optimisation existence of an ideal solution, optimal for all objectives simultaneously, is generally considered to be a rather rare phenomenon, and therefore not really investigated, see e.g. Ehrgott (2005). However, as indicated in Sect. 2, the exceptional case that some ideal solution exists has almost self-evident but very interesting consequences: the ideal solutions are precisely all efficient solutions of the multiobjective problem; moreover these are also precisely all optimal solutions to any single objective that is a weighted sum of these objectives. Section 3 shows that this phenomenon is perhaps not so rare, in particular in location theory—a mild introduction to this wide and growing field is found in the now classical work Francis et al. (1992) or the book by Love et al. (1988), while Nickel and Puerto (2005) give a much more advanced and detailed technical treatment; for a recent comprehensive collection of survey papers see Laporte et al. (2015). It does appear in minisum facility location problems with a special structure, and so leads to a unified
B 1
Frank Plastria [email protected] Prof.Em. BUTO, Vrije Universiteit Brussel, Pleinlaan 2, 1050 Brussels, Belgium
123
F. Plastria
and simple proof strategy of some historical results, as well as a number of less known ones. In particular we obtain a new look and extensions of a majority theorem of 1964 of Witzgall (1964) valid in any possibly asymmetric metric space, and a result of 1775 of Fagnano on convex 4-point problems in the plane, as well as the least absolute deviation property of the median obtained by Laplace around 1774, both extended to any normed space and more general configurations.
2 Ideal solutions and their eventual impact The concept of ideal solution stems from multiobjective optimisation (here always considered in its allover minimisation form): Let F be a set of functions f : X → R, then x ∈ X is an F-ideal solution if and only if x minimizes each f ∈ F on X . We denote the set of F-ideal solutions by ID(F) := { x ∈ X ∀ f ∈ F, ∀y ∈ X : f (x) ≤ f (y) } Two standard ways of comparing solutions in X based on F are as follows. We say that x strictly F-dominates y (in a minimisation sense) whe
Data Loading...
