MULTITHREADED DIMENSION REDUCTION IN LOCATION THEORY

JÖRG FLIEGE^{∗}

Abstract. Due to inevitable nondifferentiabilities, the minisum multifacility location problem is regarded as hard to solve. We propose a new chararacterization of points at which nondifferentiabilities occur. By this chararacterization it is possible to check if several variables can be identified with each other, thereby reducing the dimension of the problem and the number of nondifferentiable terms in the objective function.

Key words. facility location, coincidence conditions, dimension reduction, nondifferentiability detection

AMS subject classifications. 49K10, 90B80, 90B85, 90C35, 90C48

1. Introduction. In multifacility location one has given some fixed facilities and one is looking for the locations of some new facilities. The quality of a choice of locations is measured by an objective function in which the interactions between the different objects are taken into account. Typically, the sum of all interaction costs is considered. Applications for this problem can be found in limit analysis [4], when solving Steiner tree [58] or minimal surface problems, when computing the static of spring systems [40], in location science [46, 47], etc. The complexity of the problem can be seen by the following observation: if a norm is used to determine the distance between two points in IR^{N}, the objective function will not be differentiable, because two objects may have the same location and norms are not differentiable at the origin. But such a coincidence, i. e. two objects sharing the same location in a minimum of the multifacility location problem, is likely to occur rather often. Consequently, after the first formulation of the problem at the end of the fifties in the work of Moses [39], a large number of different numerical methods for solving problems of this type have been proposed (see, e. g., [46, 47] for an overview).

For special cases, special lines of attack lead to success [42, 30, 53, 11]. In a more general case, we may approximate the nondifferentiable objective function by an infinitely often differentiable one (hyperbolic approximation, cp., e. g., [54, 17]). For this approach, convergence results have been derived for popular methods [28]. However, the speed of convergence is usually only linear [27]. Other solution attempts ignore the existence of coincidences and use methods from nondifferentiable optimization [31, 18]. But only linear convergence seems to be achievable here, too [33, 57]. It was in the eighties when Newton-like methods, working with projections onto linear manifolds which correspond exactly to the nondifferentiabilities, and achieving quadratic convergence have been developed [40, 5]. Unfortunately, it is not clear how far the amount of work necessary in each step makes these methods unattractive for large problems. Moreover, some assumptions made in the convergence proofs on the structure of the problem seem to hold for special cases only [12]. Another approach consists of solving a differentiable reformulation of the primal or dual problem [50]. However, this reformulation seems to be possible only for the Euclidean norm case. In recent times, interior point methods have been applied to special cases of the minisum multifacility location problem with Euclidean distances [4, 1] and complexity

∗Fachbereich Mathematik, Universität Dortmund, 44221 Dortmund, Germany. e-mail

fliege@math.uni-dortmund.de

results have been proven [59, 58]. Since some of these algorithms have a polynomial time complexity, the methods seem to be not as sensitive with respect to coincidences than the methods mentioned above. First numerical results seem to confirm this [10, 2, 3, 58]. Moreover, the author has developed polynomial-time algorithms for convex multifacility location problems with mixed nonsymmetric gauges [23]. Unfortunately, up to now no numerical experiences have been gathered. An extension to nonconvex problems seems to be rather questionable.

Only a few authors are concerned with nonsymmetric distances instead of symmetric ones. The actual proposal was already made by Witzgall [55], who viewed symmetry as an artifact of modeling. If the locational space is a real vector space, we arrive in a natural way at the concept of gauges [38] as the nonsymmetric counterpart of norms.

Another generalization of the minisum multifacility location problem is obtained when distances occurring in the objective function are weighted with negative numbers. With this, we extend the purely economical interpretation of these terms, and objects whose interactions with other objects are measured by negative weighted distances can now be interpreted as obnoxious, semi-obnoxious, or repulsive facilities. Consequently, the applications proposed in the literature often consider waste disposal sites, chemical plants, nuclear reactors, etc. (cp., e. g., [16, 46, 15, 47] for overviews of other objective functions used for these problems). The loss of convexity encountered here means, of course, that we lose many of the tools from convex analysis. Consequently, this type of problem has been attacked rather lately. The computation times documented [8, 7, 52] seem to suggest that only special, low-dimensional problem classes can be solved with the methods proposed. In addition to the problems caused by the nondifferentiability mentioned above we have to take care of the nonconvexity also. Therefore, a special treatment of the nondifferentiable points in the locational space seems to be even more urgent than before.

By considering such a special treatment, the question of detecting and characterizing the nondifferentiabilities turns up immediately. In most models, norms are used to measure distances. Therefore, points of nondifferentiability have to be expected whenever two objects share the same location. Sufficient conditions for such a coincidence of facilities in a solution of a multifacility location problem are called coincidence conditions. By using such conditions, we may simultaneously reduce the number of unknowns, i. e. we carry out a dimension reduction. In this way it is possible to drastically reduce the amount of work necessary for an optimization method employed to solve a given problem. Witzgall [55, p. 30] considered such conditions for the single-facility case, while Juel and Love [32] considered the minisum multifacility problem with Euclidean norms. The sensitivity of some special cases of the Euclidean problem has been analyzed by Pesamosca and Mazzarella [41]. Plastria [44] generalized Witzgall’s result to the case of a nonsymmetric distance functions, while Lefebvre, Michelot, and Plastria [36, 37] considered the multifacility case with an arbitrary metric. Finally, problems with mixed gauges have been considered by Fliege [19, 20, 22]. If not only metrical, but also analytical properties of the functions employed are used, we can derive stronger, but not as general results. This is usually done with tools from convex analysis [34, 35, 19, 29, 9]. Metrical and analytical properties can be used even when mixed distance functions are employed [45, 19]. But in none of the works cited above there have been considered negative weights in the form discussed in the last paragraph. After a trivial case was considered [51], Plastria [43] extended the conditions known to the single-facility case with positive and negative weights in pseudometric spaces. These results have been generalized to multifacility location problems with positive and negative weights in weak metric spaces by Fliege [24]. Frenk [26] generalized these conditions to minisum multifacility location problems with concave costfunctions in weak metric spaces. More general conditions, which contain all the conditions cited above as special cases, can be found in this work.

In this paper we will consider minisum multifacility location problems in which the functions used to measure distances fulfill only the triangle inequality or the inverse triangle inequality. With this concept, we may use, e. g., positive or negative weighted weak metrics. Mixed distance functions may be used in one problem simultaneously. All minisum multifacility location problems attacked in the works cited above belong to this category. We will prove new coincidence conditions for this problem class which contain all metric coincidence conditions cited above as special cases (cp. Theorem 4). Because of the wide variety of applications, these conditions can be used in any iterative code for solving minisum multifacility location problems to reduce the problem dimension prior or during the iteration. Furthermore, additional information of the model is gained, which may be important during an economic analysis or an interpretation of the solution set. Moreover, nondifferentiable terms in the objective function can be dropped, which results in a subsequent easier numerical treatment.

The rest of this work is as follows. In § 2, we will present the necessary definitions with respect to distance cost functions and the problem at hand, and we will formulate the location problem as a graph embedding problem. Section 3 contains some auxiliary results needed in § 4. There, the main result of this paper, Theorem 4, is derived and several examples of its application are presented.

Efficient algorithms for checking the conditions proposed here and computational results are presented in a companion paper [25].

2. Notation. In this section, the notation used is introduced and the optimization problem considered is defined.

For a fixed set X ≠ ∅ we define the set Δ by Δ := {(x, x) ∈ X × X | x ∈ X}, the diagonal of X × X. For an arbitrary set Λ and an arbitrary index set I define

Λ^{I} := {(λ_{i})_{i∈I} | ∀ i ∈ I : λ_{i} ∈ Λ},

the set of all families (λ_{i})_{i∈I} with λ_{i} ∈ Λ for all i ∈ I.

2.1. Distance Costs. A function

d : X × X ⟶ IR

is called convex, if for all x, y, z ∈ X the triangle inequality

d(x, y) ≤ d(x, z) + d(z, y)

holds. For example, all metrics on X are convex. The function f ∘d fulfills the triangle inequality, if f : IR ⟶ IR is monotone nondecreasing and subadditive and d fulfills the triangle inequality. A function d : X × X ⟶ IR is called concave if −d is convex. For d : X × X ⟶ IR we define \overline{d} by \overline{d}(x, y) := d(y, x). The function \overline{d} is convex if and only if d is convex. Moreover, \overline{d} is concave if and only if d is concave.

A function d : X × X ⟶ IR is called semi-definite if for all x ∈ X the equation d(x, x) = 0 holds. For a semi-definite function d we define

[d] := \{ \begin{matrix}d & if d is convex, \\ |\overline{d}| & else. \end{matrix}

Note that [ \overline{d}] = \overline{[d]}. A semi-definite function d : X × X ⟶ IR which is either convex or concave is called distance cost function on X. Multiplying a distance cost function with an arbitrary real number again yields a distance cost function. A nonnegative convex distance cost function d is also called a weak metric [49, 55, 56, 24, 48]. For an overview of the different terminologies used in location science we refer to [48].

As an example, define X := IR and d(x, y) := x − y. Then, the function d is semidefinite, convex and therefore a distance cost function. Moreover, it is concave. By definition, we have [d] = d. If d is a convex distance cost function and f : IR ⟶ IR is monotone nondecreasing and subadditive with f(0) = 0, then f ∘ d is a convex distance cost function. This has important applications in several economic models, since transportation costs are often modelled as monotone nondecreasing concave functions of distance [6, 48].

In what follows, we write for given functions c, d : X × X ⟶ IR the inequality c ≤ d, if this inequality holds for all arguments (x, y) ∈ X × X. For semi-definite functions c, d the inequality above is called strict, if it is strict for all arguments (x, y) ∈ (X × X) \ Δ.

2.2. Graphs. Let F ≠ ∅ be an arbitrary set and E ⊆ F × F. Then G := (F, E) is called graph with node set F and edge set E. A 2-tuple (f, g) ∈ F × F will also be denoted by fg. For f ∈ F and U ⊆ F we define the following subsets of F:

F_{G}(f, U) := {g ∈ U | (f, g) ∈ E},
F_{G}(U, f) := {g ∈ U | (g, f) ∈ E},
F_{G}(f, U) = F_{G}(U, f) := F_{G}(f, U) ∪ F_{G}(U, f).

For U_{1}, U_{2} ⊆ F and f ∈ F define E_{G}(U_{1}, U_{2}) := E ∩ (U_{1} × U_{2}),

E_{G}(U_{1}, U_{2}) = E_{G}(U_{2}, U_{1}) := E_{G}(U_{1}, U_{2}) ∪ E_{G}(U_{2}, U_{1})

and E_{G}(f, U) := E_{G}({f}, U), E_{G}(U, f) := E_{G}(U, {f}), as well as

E_{G}(f, U) = E_{G}(U, f) := E_{G}(f, U) ∪ E_{G}(U, f).

If the graph G is fixed or it is clear which given graph is meant, we will omit the index on E_{G}, E_{G}, F_{G} and F_{G}. Now let G′ := (F′, E′) be a subgraph of G, i. e. we have F′ ⊆ F and E′ ⊆ E ∩ (F′ × F′). Then we define F′(f, U) := F_{G′}(f, U) and modify the rest of the notation analogously. The same modifications will be used if a graph is denoted by G_{0} or some other symbols.

2.3. The Problem. In what follows, let G = (F, E) be a directed simple graph with finite node set F. This node set should be partitioned into two nonempty sets A and V, i. e. we have A∪V = F and A∩V = ∅. For all a ∈ A there should be given an x_{a} ∈ X. For all e ∈ E there should be given a distance cost function d_{e} : X×X ⟶ IR. Our goal is to embed the graph G into the space X in such a way that the total cost induced by the interactions between nodes in F and measured by the functions d_{e} is minimized. Since we have already given the locations of the facilities a ∈ A, we are in search for locations for the facilities v ∈ V. Such a location x_{v} ∈ X for a node v ∈ V is called new location of the object v. The locations x_{a} ∈ X (a ∈ A) are the known locations of the optimization problem defined below. Moreover, let there be given a set C ⊆ X^{V} of feasible families of new locations.

If, in addition to the fixed locations x_{a} ∈ X (a ∈ A), a family of new locations (x_{v})_{v∈V} ∈ X^{V} is given, we can define for each (f, g) ∈ F × F the 2-tuple x_{fg} := (x_{f}, x_{g}) ∈ X ×X. If e = (f, g) ∈ E we will write x_{e} := x_{fg}. If, in addition to (x_{v})_{v∈V}, a second family (x̃_{v})_{v∈V} ∈ X^{V} is given, we will use the obvious definition x̃_{a} := x_{a} (a ∈ A) and write x̃_{fg} := (x̃_{f}, x̃_{g}) for (f, g) ∈ F × F and x̃_{e} := x̃_{fg} for e = (f, g) ∈ E. This notation will also be used for additional families (x̂_{v})_{v∈V} , (y_{v})_{v∈V} ∈ X^{V} etc. For example, x̂_{fg} := (x̂_{f}, x̂_{g}), y_{e} := y_{fg} := (y_{f}, y_{g}) if e = (f, g) ∈ E etc.

Definition 1 (Minisum Multifacility Location Problem). The constrained minisum multifacility location problem with mixed distance cost functions is the following optimization problem:

Find a minimum (x̂_{v})_{v∈V} ∈ X^{V} of the function

\begin{matrix}Ψ : X^{V} & ⟶ & IR \\ (x_{v})_{v∈V} & ⟼ & ∑_{e∈E} d_{e}(x_{e}) \end{matrix} (2.1)

subject to the constraint (x̂_{v})_{v∈V} ∈ C.

Since X^{V} has no natural topology, the minimum (x̂_{v})_{v∈V} of the objective function Ψ that we are in search for according to the definition above is a point (x̂_{v})_{v∈V} ∈ C ⊆ X^{V} such that Ψ((x̂_{v})_{v∈V}) ≤ Ψ((x_{v})_{v∈V}) holds for all (x_{v})_{v∈V} ∈ C. Of course, this problem does not need to have a solution. A discussion about the assumptions needed to prove the existence of optimal families can be found in [55, p. 32–33] or [14].

If the graph G contains multiple edges we have a slightly more general problem than the one defined above. However, the results stated in the following sections still hold (cp. [21, Bemerkung 2.1.3,Bemerkung 2.2.5]). For the sake of an easier notation, we will omit this generalization at this point.

In what follows, we may assume without loss of generality that all functions d_{e} (e ∈ E) are unequal to the constant function 0. Moreover, we will not allow the presence of edges between two facilities with known location: (a, b) ∉ E for all a, b ∈ A. Edges of this type only show up as constant terms d_{ab}(x_{a}, x_{b}) in Ψ. On the other hand, we may use on each ”nonexisting” edge (f, g) ∉ E the distance cost function d_{fg} ≡ 0 and add (f, g) to the edge set E. This will be done below as soon as it simplifies the notation.

For other assumptions which can be made without loss of generality, the reader is referred to Plastria [45] and Fliege [19].

2.4. Compatible Partitions. Let two subsets E_{≤} ⊆ E and E_{≥} ⊆ E of E be given with E_{≤} ∩ E_{≥} = ∅. Then, the notation of § 2.2 can be used here immediately. As an example, we set E_{≤}(f, U) := E_{≤} ∩ E(f, U), F_{≥}(U, f) := F_{(F,E_{≥})}(U, f) etc. The obviously arbitrary indices ≤ and ≥ on the sets E_{≤} and E_{≥} will be motivated in § 4. Here, it suffices to say that it will later be meaningful to define E_{≥} as the set of all edges e ∈ E such that d_{e} is concave.

Now let a number n ∈ IN, n ≥ 2, be given and W = {W_{0}, …, W_{n}} be a given partition of F, i. e. we have W_{i} ∩ W_{j} = ∅ for i ≠ j, i, j = 0, …, n, W_{i} ≠ ∅ for i = 0, …, n, and ⋃_{i=0}^{n} W_{i} = F. Then W is called compatible with Ψ, if at most one object with known location is in W_{0} and all W_{i} with 1 ≤ i ≤ n−1 contain only objects with unknown location: |W_{0} ∩A| ≤ 1 and ⋃_{i=1}^{n−1} W_{i} ⊆ V. In this case the set K := W_{0} is called kernel of W and the set S := W_{n} is called shell of W. This naming scheme is motivated by the strategy of dimension reduction described in § 3 and 4. For a given compatible partition we will try to identify the nodes in the sets W_{i} (1 ≤ i ≤ n − 1) with the nodes in the kernel K, while we will leave the nodes in the shell S as they are. For i ≤ n define U_{i} := ⋃_{j=0}^{i} W_{j}. For f ∈ F let W (f) be the (well-defined) set W_{i} ∈ W such that f ∈ W_{i}. Now let f ∈ F \ S and W_{i} = W (f). Then the set pre(f) := U_{i−1} is called the predecessor of f and the set succ(f) := U_{n−1} \ U_{i} is called the successor of f. If a partition W = {W_{0}, …, W_{n}} is given we may without loss of generality assume that E(U_{i}, F \ U_{i}) = E(U_{i}, F \ U_{i}) (0 ≤ i ≤ n − 1) holds. If this is not the case, we turn around each edge e with the wrong direction and replace the distance cost function d_{e} by \overline{d_{e}}.

Now let W = {W_{0}, …, W_{n}} be a partition compatible with Ψ with kernel K and shell S (i. e. K = W_{0} and S = W_{n}). If another set E_{s} ⊆ E(F \ S, F \ S) is given, we define the subgraph G′ = (F, E′) by E′ := E \ E_{s}.

3. A Single Threaded Reduction Theorem. In this section and the following one we will derive new sufficient conditions for coincidences in minisum multifacility location problems. If one of these conditions is fulfilled, we have in at least one minimum (x̂_{v})_{v∈V} of the objective function Ψ an identity of the form x̂_{f} = x̂_{g}. In this case, we may identify the nodes f and g in the graph G. Likewise, the number of unknowns and the number of terms in the objective function which are nondifferentiable in at least one minimum are reduced. In case we have a constrained problem, we can deduce which constraints have to be active at a solution of our problem.

The next theorem contains a sufficient condition for a coincidence between exactly two objects in the node set of the graph given. This condition is formulated as an inequality between the distance cost functions which measure the distance to and from the locations of the two objects. This means that the coincidence condition is strictly local with respect to the topology of the graph that has to be embedded. A more general result characterizing coincidences of several objects is contained in the next section.

Theorem 2. Let f ∈ V, g ∈ F and (x_{v})_{v∈V} ∈ X^{V} be given. Define (x̂_{v})_{v∈V} ∈ X^{V} by x̂_{h} := x_{h} for h ≠ f and x̂_{f} := x_{g}. If

∑_{e∈E(f,F)} [d_{e}] + ∑_{{e∈E(F,f) \atop e≠gf}} [ \overline{d_{e}} ] ≤ d_{gf} (3.1)

holds, it follows that

Ψ((x̂_{v})_{v∈V}) ≤ Ψ((x_{v})_{v∈V}).

If (3.1) is strict and x_{f} ≠ x_{g}, we have that Ψ((x̂_{v})_{v∈V}) < Ψ((x_{v})_{v∈V}).

Proof. The proof is a simple generalization of the proof of the attraction theorem found, e. g., in [24]. It can also be found in [21].

Corollary 3. Let the assumptions of Theorem 2 be fulfilled. From (x_{v})_{v∈V} ∈ C it should always follow that (x̂_{v})_{v∈V} ∈ C. If there exists a solution to problem (2.2), then there exists at least one solution (x̂_{v})_{v∈V} of (2.2) such that x̂_{f} = x̂_{g}. If, additionally, (3.1) is strict, then for each solution (x̃_{v})_{v∈V} of (2.2) we have that x̃_{f} = x̃_{g}.

The relation (3.1) is often called attraction between f and g [20, 36, 37]. Another terminology uses the notion of majority, cp. [43, 44, 48].

Some remarks about further generalizations to Theorem 2 can be found in [21]. Especially, we may associate each edge e ∈ E, e ≠ (g, f), of the graph G with a sum ∑_{i=1}^{m_{e}} d_{e}^{(i)} (m_{e} ∈ IN) of distance cost functions instead of a single function d_{e}. With this, a similar result holds. Moreover, the theorem above still holds if some of the functions d_{e} with e ∉ E(f, F) are neither convex nor concave [21].

Theorem 2 considers an attraction between exactly two objects f and g. But not all coincidences fit into this scheme. We will extend the coincidence condition derived above in the next section.

4. A Multithreaded Reduction Theorem. Let E_{≤} ⊆ E and E_{≥} ⊆ E be two arbitrary fixed edge sets with E_{≤} ∪ E_{≥} = E and E_{≤} ∩ E_{≥} = ∅. For example, we may choose E_{≤} := {e ∈ E | d_{e} convex}.

The next theorem defines a complex attraction structure of the following type: if a subset of all distance cost functions used fulfills certain conditions, we may identify the locations of the nodes connected by the corresponding edges without increasing the objective function value. These sufficient conditions are formulated in terms of the existence of certain distance cost functions. Since the identification process can be carried out for all families of new locations without increasing the objective function value, we can reduce the dimension of the problem, i. e. the number of unknowns. Let a partition W be given which is compatible with Ψ. The idea of the new attraction structure consists of the ”splitting” of all nodes v ∈ W_{i} (i = n − 1, …, 1) into as many nodes as there are edges in E′_{≤}(pre(v), v). Each of these edges (f, v) will then be redefined such that the node f is connected to its corresponding new node. This represents a ”thread”, starting in the set W_{n−1} and ultimately ending in the kernel K. Further, since the node v has been split up, edges of the kind (v, s) ∈ E(v, S) will be split up into several different ones. As a consequence, the corresponding distance cost functions d_{vs} have to be split up, too. But this split into several functions, say d_{s}^{f,v}, has to be consistent with the function d_{vs}, which means that the sum of the new functions d_{s}^{f,v} has to be equal to d_{vs}. This splitting process has to be done for all edges involved. If this is done successively for all nodes v ∈ W_{i} and all W_{i}, i = n − 1, …, 1, we may apply in each step Theorem 2 on the spliced nodes to get attraction along the edges in E′_{≤}(pre(v), v). Because of this attraction, we may identify pairs of nodes connected by those edges. Likewise, we may identify resulting multiple edges. In the last step, we have to use our consistency conditions to compare the constructed sequence of graphs and corresponding embedding problems with the original graph and the original embedding problem.

Theorem 4. Let W = {W_{0}, …, W_{n}} be a partition of F which is compatible with Ψ and which has the kernel K and the shell S. Define U := F \ (K ∪ S). Let E_{s} ⊆ E(F \ S, F \ S) be an edge set such that d_{e} ≥ 0 holds for all e ∈ E_{s} and define E′ := E \ E_{s}. Assume that F′_{≤}(pre(v), v) ≠ ∅ holds for all v ∈ U.

For all v ∈ U, w ∈ W (v) \ {v}, f ∈ F′_{≤}(pre(v), v), g ∈ F′_{≤}(pre(w), w), h ∈ pre(v) \ F′_{≤}(pre(v), v), and s ∈ S there should exist distance cost functions

d_{s}^{f,v}, d_{v,w}^{f,g}, d_{w,v}^{g,f}, d_{h}^{f,v}, and d^{f,v},

such that the following conditions hold:

1. The attraction conditions

(4.1a) ∑_{s∈S} [d_{s}^{f,v}] + ∑_{{w∈W (v)\\{v\} \atop g∈F{′ \atop ≤}(pre(w),w)}} ([d_{v,w}^{f,g}] + [ \overline{d_{w,v}^{g,f}} ]) + ∑_{h∈pre(v)\F′_{≤}(pre(v),v)} [ \overline{d_{h}^{f,v}} ] ≤ d^{f,v}

for all v ∈ U and f ∈ F′_{≤}(pre(v), v), 2. the consistency conditions

(4.1b)  ∑_{f∈F′_{≤}(pre(v),v)} d_{s}^{f,v} = ∑_{vs∈E} d_{vs} + ∑_{u∈F′_{≤}(v,succ(v))} d_{s}^{v,u}

for all v ∈ U and s ∈ S,

(4.1c) ∑_{{f∈F{′ \atop ≤}(pre(v),v) \atop g∈F{′ \atop ≤}(pre(w),w)}} d_{v,w}^{f,g} = ∑_{vw∈E′} d_{vw} + ∑_{u∈F{′ \atop ≤}(w,succ(w)) with vu∉E{′ \atop ≤}} d_{v}^{w,u} + ∑_{t∈F{′ \atop ≤}(v,succ(v)) {u∈F{′ \atop ≤}(w,succ(w)) \atop W (t)=W (u),t≠u}} d_{t,u}^{v,w}

for all v, w ∈ U with w ∈ W (v) \ {v},

(4.1d) ∑_{f∈F′_{≤}(pre(v),v)} d_{h}^{f,v} = ∑_{hv∈E′_{≥}} d_{hv} + ∑_{u∈F{′ \atop ≤}(v,succ(v)) with h∉F{′ \atop ≤}(pre(u),u)} d_{h}^{v,u}

+ ∑_{u∈F{′ \atop ≤}(h,succ(v)) with v∉F{′ \atop ≤}(pre(u),u)} \overline{d_{v}^{h,u}} + ∑_{t∈F{′ \atop ≤}(v,succ(v)) {u∈F{′ \atop ≤}(h,succ(v)) \atop W (t)=W (u),t≠u}} (d_{u,t}^{h,v} + \overline{d_{t,u}^{v,h}})

for all v ∈ U and h ∈ pre(v) \ F′_{≤}(pre(v), v), and

(4.1e)  d^{f,v} = ∑_{fv∈E′} d_{fv} + ∑_{u∈F{′ \atop ≤}(v,succ(v)) with f∉F{′ \atop ≤}(pre(u),u)} d_{f}^{v,u}

+ ∑_{u∈F{′ \atop ≤}(f,succ(v)) with v∉F{′ \atop ≤}(pre(u),u)} \overline{d_{v}^{f,u}} + ∑_{t∈F{′ \atop ≤}(f,succ(v)) {u∈F{′ \atop ≤}(v,succ(v)) \atop W (t)=W (u),t≠u}} (d_{t,u}^{f,v} + \overline{d_{u,t}^{v,f}})

for all v ∈ U and f ∈ F′_{≤}(pre(v), v). Now, let an x ∈ X and a family (x_{v})_{v∈V} ∈ X^{V} be given with x_{k} = x for all k ∈ K. Define (x̂_{v})_{v∈V} ∈ X^{V} by x̂_{v} := x for all v ∈ V \ S and x̂_{s} := x_{s} for all s ∈ V ∩ S. Then, it follows that

Ψ((x̂_{v})_{v∈V}) ≤ Ψ((x_{v})_{v∈V}).

This inequality is strict, if (4.1a) is strict for an edge (f, v) ∈ E′_{≤} with x_{f} ≠ x_{v} or if there exists an edge e ∈ E_{s} such that d_{e}(x_{e}) ≠ 0 holds.

Corollary 5. Let the assumptions of Theorem 4 hold. Define

K := {(x_{v})_{v∈V} ∈ X | x_{j} = x_{k} for all j, k ∈ K}.

From (x_{v})_{v∈V} ∈ C ∩ K it should always follow that (x̂_{v})_{v∈V} ∈ C ∩ K. If there exists a solution (x_{v})_{v∈V} of problem (2.2) with (x_{v})_{v∈V} ∈ K, then there exists at least one solution (x̂_{v})_{v∈V} of (2.2) with x̂_{u} = x̂_{k} for all u ∈ U, k ∈ K. If, additionally, (4.1a) is strict for an edge (f, v) ∈ E′_{≤}, we have for each solution (x̃_{v})_{v∈V} of (2.2) with (x̃_{v})_{v∈V} ∈ K that x̃_{f} = x̃_{v}. Moreover, we have for each solution (x̃_{v})_{v∈V} of (2.2) with (x̃_{v})_{v∈V} ∈ K that d_{e}(x̃_{e}) = 0 holds for all e ∈ E_{s}.

Proof of Theorem 4. To proof the theorem, we define for each index i, i = n − 1, …, 1, a new multifacility location problem in which a graph G′_{i} has to be embedded into the space X by minimizing a function Ψ′_{i}. Fixed nodes in G′_{i} will be the nodes in S ∪ A, free nodes will be the nodes in U_{i−1} ∩ V. Moreover, we will split each node v ∈ W_{i} in as many nodes as there are edges in E′_{≤} connecting v with U_{i−1}.

By using (4.1a), we will then show attraction of the split up nodes into the set U_{i−1}. The structure of the graph G′_{n−1} is given by the embedding of G induced by (x_{v})_{v∈V}. The embedding induced by the coincidence result on G′_{i} will induce the structure of the graph G′_{i−1}. Finally, we will use the consistency conditions (4.1b)–(4.1e) to compare the embedding costs of G′_{1} with Ψ((x̂_{v})_{v∈V}), and we will conclude that these two costs are equal.

In what follows, note that E(U_{i}, F \ U_{i}) = E(U_{i}, F \ U_{i}) for 0 ≤ i ≤ n − 1.

For i = n − 1, …, 1 define

V_{i} := (V \ ⋃_{j=i}^{n−1} W_{j}) ∪· {v_{e} | e ∈ E′_{≤}(U_{i−1}, W_{i})}

and Ṽ_{i} := V_{i} \ V. Here, the nodes v_{e} (e ∈ E′_{≤}(U_{i−1}, W_{i})) should not be contained in V and for edges e_{1}, e_{2} ∈ E′_{≤}(U_{i−1}, W_{i}) with e_{1} ≠ e_{2} we should have v_{e_{1}} ≠ v_{e_{2}}.

Now define F_{i} := A ∪ V_{i} and

E′_{i} := (U_{i−1} × U_{i−1}) \ {(f, f) | f ∈ U_{i−1}}
∪· (Ṽ_{i} × S) ∪· (U_{i−1} × S) ∪· E′(S, S)
∪· {(f, v_{e}) | e = (f, v) ∈ E′_{≤}(U_{i−1}, W_{i})}
∪· {(h, v_{e}) | e = (f, v) ∈ E′_{≤}(U_{i−1}, W_{i}), h ∈ U_{i−1} \ F′_{≤}(pre(v), v)}
∪· {(v_{e_{1}}, v_{e_{2}}) | e_{1} = (f, v) ∈ E′_{≤}(U_{i−1}, W_{i}),
e_{2} = (g, w) ∈ E′_{≤}(U_{i−1}, W_{i}), v ≠ w}

as well as G′_{i} := (F_{i}, E′_{i}). Note that the graph G′_{i} may contain multiple edges, since for nodes f, g ∈ U_{i−1} with f ≠ g we have (f, g) ∈ E′_{i} and (g, f) ∈ E′_{i}. Likewise, for edges e_{1}, e_{2} ∈ E′_{≤}(U_{i−1}, W_{i}), e_{1} = (f, v), e_{2} = (g, w) with v ≠ w we have (v_{e_{1}}, v_{e_{2}}) ∈ E′_{i} and (v_{e_{2}}, v_{e_{1}}) ∈ E′_{i}.

Next, we have to provide the graph G′_{i} with semi-definite functions d_{e}^{(i)}. This is done in the following way:

1. e = (f, g) ∈ U_{i−1} × U_{i−1}, f ≠ g: for i = n − 1 set d_{e}^{(n−1)} := ∑_{e∈E′} d_{e}, for 1 ≤ i < n − 1 set

d_{e}^{(i)} := d_{e}^{(i+1)} + ∑_{u∈F{′ \atop ≤}(f,W_{i+1}) ; {v∈F{′ \atop ≤}(g,W_{i+1}) \atop u≠v}} d_{u,v}^{f,g} + ∑_{{v∈F{′ \atop ≤}(g,W_{i+1}) \atop with f∉F{′ \atop ≤}(pre(v),v)}} d_{f}^{g,v}.

Usually, the functions d_{fg}^{(i)} are neither convex nor concave. However, each such function is a sum of convex or concave semi-definite functions.

2. e = (v\overline{e}, s) ∈ Ṽ_{i} × S with \overline{e} = (f, v) ∈ E′_{≤}(U_{i−1}, W_{i}): d_{e}^{(i)} := d_{s}^{f,v}.

3. e = (f, s) ∈ U_{i−1} × S: set

d_{e}^{(i)} := ∑_{fs∈E′} d_{fs} + ∑_{j=i+1}^{n−1} ∑_{u∈F′_{≤}(f,W_{j})} d_{(v_{fu},s)}^{(j)}. (4.2)

As in the first case, this function is a sum of convex or concave semi-definite functions. 4. e ∈ E′(S, S): d_{e}^{(i)} := d_{e}.

5. e = (f, v\overline{e}) with \overline{e} = (f, v) ∈ E′_{≤}(U_{i−1}, W_{i}): d_{e}^{(i)} := d^{f,v}.

6. e = (h, v\overline{e}) with \overline{e} = (f, v) ∈ E′_{≤}(U_{i−1}, W_{i}), h ∈ U_{i−1} but h ∉ F′_{≤}(pre(v), v): d_{e}^{(i)} := d_{h}^{f,v}.

7. e ∈ (v_{e_{1}}, v_{e_{2}}) with e_{1}, e_{2} ∈ E′_{≤}(U_{i−1}, W_{i}), e_{1} = (f, v), e_{2} = (g, w), v ≠ w: d_{e}^{(i)} := d_{v,w}^{f,g}. Define the families (x_{v}^{(i)})_{v∈V_{i}} ∈ X^{V_{i}} and (x̃_{v}^{(i)})_{v∈V_{i}} ∈ X^{V_{i}} by

x_{v}^{(i)} := x_{v} for v ∈ V ∩ V_{i} = V \ Ṽ_{i} = (U_{i−1} ∪· S) ∩ V,
x_{v_{e}}^{(i)} := x_{v} for e = (f, v) ∈ E′_{≤}(U_{i−1}, W_{u}), i. e. v_{e} ∈ Ṽ_{i},
x̃_{v}^{(i)} := x_{v} for v ∈ V ∩ V_{i}, and
x̃_{v_{e}}^{(i)} := x_{f} for e = (f, v) ∈ E′_{≤}(U_{i−1}, W_{i}), i. e. v_{e} ∈ Ṽ_{i}.

This means that the family (x̃_{v}^{(i)})_{v∈V_{i}} is generated from the family (x_{v}^{(i)})_{v∈V_{i}} by coinciding each node v_{fv} ∈ Ṽ_{i} with the node f ∈ U_{i−1}.

As auxiliary functions, we define

Ψ′_{i}((y_{v})_{v∈V_{i}}) := ∑_{e∈E′_{i}} d_{e}^{(i)}(y_{e}),

where (y_{v})_{v∈V_{i}} ∈ X^{V_{i}}. For an index i ∈ {1, …, n − 1}, let a node v_{e} ∈ Ṽ_{i} with e = (f, v) ∈ E′_{≤}(U_{i−1}, W_{i}) be given. Then we have

E′_{i}(v_{e}, F_{i}) = ({v_{e}} × S) ∪· {(f, v_{e})}
∪· {(h, v_{e}) | h ∈ U_{i−1} \ F′_{≤}(pre(v), v)}
∪· \{(v_{e}, v\overline{e}) | \overline{e} = (g, w) ∈ E′_{≤}(U_{i−1}, W_{i}), v ≠ w\}
∪· \{(v\overline{e}, v_{e}) | \overline{e} = (g, w) ∈ E′_{≤}(U_{i−1}, W_{i}), v ≠ w\},

and the definitions of the d_{e}^{(i)} above show us that

∑_{e∈E′_{i}(v_{e},F_{i})} d_{e}^{(i)} = ∑_{s∈S} d_{s}^{f,v} + ∑_{{gw∈E{′ \atop ≤}(U_{i−1},W_{i}) \atop with w≠v}} d_{v,w}^{f,g}

and

∑_{{e∈E′_{i}(F_{i},ve) \atop with e≠(f,ve)}} d_{e}^{(i)} = ∑_{h∈pre(v)\F′_{≤}(pre(v),v)} d_{h}^{f,v} + ∑_{{gw∈E{′ \atop ≤}(U_{i−1},W_{i}) \atop with w≠v}} d_{w,v}^{g,f}

holds. Moreover, we have d_{(f,v_{e})}^{(i)} = d^{f,v}. Because of (4.1a), the node v_{e} is attracted by f in the graph G′_{i}. Using Theorem 2, we conclude

Ψ′_{i}((x̃_{v}^{(i)})_{v∈V_{i}}) ≤ Ψ′_{i}((x_{v}^{(i)})_{v∈V_{i}}). (4.3)

This inequality is strict, if an edge (f, v) ∈ E′_{≤}(U_{i−1}, W_{i}) with x_{f} ≠ x_{v} exists such that (4.1a) is strict for all arguments (x, y) ∈ (X × X) \ Δ.

With

Ψ′((y_{v})_{v∈V}) := ∑_{e∈E′} d_{e}(y_{e}),

(y_{v})_{v∈V} ∈ X^{V}, it follows that

Ψ′_{n−1}((x_{v}^{(n−1)})_{v∈V_{n−1}}) = ∑_{e∈E′_{n−1}} d_{e}^{(n−1)}(x_{e}^{(n−1)})

= ∑_{e∈E′(U_{n−2},U_{n−2})} d_{e}(x_{e}) + ∑_{(f,v)∈E′_{≤}(U_{n−2},W_{n−1})} ∑_{s∈S} d_{s}^{f,v}(x_{(v_{fv},s)}^{(n−1)})

+ ∑_{(f,v)∈E′_{≤}(U_{n−2},W_{n−1})} d^{f,v}(x_{(f,v_{fv})}^{(n−1)}) + ∑_{{f∈U_{n−2} \atop s∈S}} ∑_{fs∈E′} d_{fs}(x_{fs})

because of (4.2),

+ ∑_{e∈E′(S,S)} d_{e}(x_{e}) + ∑_{(f,v)∈E′_{≤}(U_{n−2},W_{n−1})} ∑_{h∈pre(v)\F′_{≤}(pre(v),v)} d_{h}^{f,v}(x_{(h,v_{fv})}^{(n−1)})

+ ∑_{{fv∈E{′ \atop ≤}(U_{n−2},W_{n−1}) \atop gw∈E{′ \atop ≤}(U_{n−2},W_{n−1})} ; v≠w} d_{v,w}^{f,g}(x_{(v_{fv},v_{gw})}^{(n−1)})

because of the definitions of the d_{e}^{(n−1)} and of E′_{n−1},

= ∑_{{e∈E′(U_{n−2},U_{n−2}) \atop e∈E′(S,S)}} d_{e}(x_{e}) + ∑_{e∈E′(U_{n−2},S)} d_{e}(x_{e})

+ ∑_{v∈W_{n−1}} ∑_{s∈S} d_{vs}(x_{vs}) + ∑_{(f,v)∈E′_{≤}(U_{n−2},W_{n−1})} d_{fv}(x_{fv})

because of (4.1b) and of (4.1e),

∑_{v∈W_{n−1}} ∑_{h∈F′_{≥}(pre(v),v)} d_{hv}(x_{hv}) + ∑_{v∈W_{n−1}} ∑_{vw∈E′(v,W_{n−1})} d_{vw}(x_{vw})

because of (4.1d) and of (4.1c),

= Ψ′((x_{v})_{v∈V}).

(In the penultimate step we have used succ(v) = ∅ for all v ∈ W_{n−1}.) Let 2 ≤ i ≤ n−1. We will now show

Ψ′_{i−1}((x_{v}^{(i−1)})_{v∈V_{i−1}}) = Ψ′_{i}((x̃_{v}^{(i)})_{v∈V_{i}}). (4.4)

We have to examine the distance cost functions corresponding to the edges in E′_{i−1} and E′_{i}, resp. There are seven different cases to consider:

(i) For e ∈ E′_{i}(S, S) = E′_{i−1}(S, S) = E′(S, S) we have x̃_{e}^{(i)} = x_{e}^{(i−1)} = x_{e} and d_{e}^{(i−1)} = d_{e}^{(i)} = d_{e}. It follows that d_{e}^{(i−1)}(x_{e}^{(i−1)}) = d_{e}^{(i)}(x̃_{e}^{(i)}).

(ii) Let s ∈ S be fixed.

1. Let f ∈ U_{i−2}. Then, e = (f, s) ∈ E′_{i−1} ∩ E′_{i} and x_{fs}^{(i−1)} = x̃_{fs}^{(i)}. Using (4.2), it follows that

d_{e}^{(i−1)} = ∑_{fs∈E′} d_{fs} + ∑_{u∈F′_{≤}(f,succ(f))\U_{i−1}} d_{s}^{f,u}

and, analogously,

d_{e}^{(i)} = ∑_{fs∈E′} d_{fs} + ∑_{u∈F′_{≤}(f,succ(f))\U_{i}} d_{s}^{f,u}.

Now let v ∈ W_{i} = U_{i} \ U_{i−1} and v ∈ F′_{≤}(f, succ(f)), i. e. \overline{e} = (f, v) ∈ E′_{≤}. Then there exists exactly one v\overline{e} ∈ Ṽ_{i} with (f, v\overline{e}) ∈ E′_{i}, d_{(v\overline{e},s)}^{(i)} = d_{s}^{f,v}, and x̃_{v\overline{e}}^{(i)} = x_{f}. This means that

d_{fs}^{(i−1)}(x_{fs}^{(i−1)}) = d_{fs}^{(i)}(x̃_{fs}^{(i)}) + ∑_{v∈F′_{≤}(f,W_{i})} d_{(v_{fv},s)}^{(i)}(x̃_{(v_{fv},s)}^{(i)}). (4.5)

2. Let v ∈ W_{i−1}. For each f ∈ U_{i−2} with e = (f, v) ∈ E′_{≤} there exists exactly one v_{e} ∈ Ṽ_{i−1} with x_{v_{e}}^{(i−1)} = x_{v} and (f, v_{e}), (v_{e}, s) ∈ E′_{i−1}. Moreover, (4.1b) leads to

∑_{e=fv∈E′_{≤}(pre(v),v)} d_{(v_{e},s)}^{(i−1)} = ∑_{vs∈E} d_{vs} + ∑_{u∈F′_{≤}(v,succ(v))} d_{s}^{v,u}.

But with (4.2) we have

d_{vs}^{(i)} = ∑_{vs∈E} d_{vs} + ∑_{u∈F′_{≤}(v,succ(v))\U_{i}} d_{s}^{v,u}.

For exactly those u ∈ W_{i} with (v, u) ∈ E′_{≤} there exists a v_{vu} ∈ F′_{i} such that (v, v_{vu}), (v_{vu}, s) ∈ E′_{i}, x̃_{v_{vu}} = x_{v}, and d_{(v_{vu},s)}^{(i)} = d_{s}^{v,u}. By using x_{(v_{e},s)}^{(i−1)} = x̃_{vs}^{(i)} = x̃_{(v_{vu},s)}^{(i)} we arrive at

∑_{e=fv∈E′_{≤}(pre(v),v)} d_{(v_{e},s)}^{(i−1)}(x_{(v_{e},s)}^{(i−1)}) = d_{vs}^{(i)}(x̃_{vs}^{(i)}) + ∑_{u∈F′_{≤}(v,W_{i})} d_{(v_{vu},s)}^{(i)}(x̃_{(v_{vu},s)}^{(i)}). (4.6)

Using (4.5) and (4.6), we see that

∑_{{e∈E{′ \atop i−1}(Ṽ_{i−1},S) \atop e∈E{′ \atop i−1}(U_{i−2},S)}} d_{e}^{(i−1)}(x_{e}^{(i−1)}) = ∑_{{e∈E′_{i}(Ṽ_{i},S) \atop e∈E′_{i}(U_{i−1},S)}} d_{e}^{(i)}(x̃_{e}^{(i)}). (4.7)

(iii) Let e = (v_{e_{1}}, v_{e_{2}}) ∈ E′_{i−1}(Ṽ_{i−1}, Ṽ_{i−1}), which means that we have e_{1} = (f, v) ∈ E′_{≤}(U_{i−2}, W_{i−1}) and e_{2} = (g, w) ∈ E′_{≤}(U_{i−2}, W_{i−1}) for some f, g ∈ U_{i−2} and v, w ∈ W_{i−1}. Moreover, it is v ≠ w. The definition above shows us that d_{e}^{(i−1)} = d_{v,w}^{f,g}. Likewise, the definition of the d_{vw}^{(i)} for i < n − 1 shows us that we have

d_{vw}^{(i)} = d_{vw}^{(i+1)} + ∑_{{t∈F{′ \atop ≤}(v,W_{i+1}) \atop u∈F{′ \atop ≤}(w,W_{i+1})} ; t≠u} d_{t,u}^{v,w} + ∑_{{t∈F{′ \atop ≤}(w,W_{i+1}) \atop with v∉F{′ \atop ≤}(pre(t),t)}} d_{v}^{w,t}

= ∑_{vw∈E′} d_{vw} + ∑_{t∈F{′ \atop ≤}(v,succ(v))\W_{i} u∈F{′ \atop ≤}(w,succ(w))\W_{i} t≠u,W (t)=W (u)} d_{t,u}^{v,w} + ∑_{t∈F{′ \atop ≤}(w,succ(w))\W_{i} with v∉F{′ \atop ≤}(pre(t),t)} d_{v}^{w,t}.

But for i = n − 1 it is d_{vw}^{(i)} = ∑_{vw∈E′} d_{vw}. This means that

(4.8)  d_{vw}^{(i)} = ∑_{vw∈E′} d_{vw} + ∑_{t∈F{′ \atop ≤}(v,succ(v))\W_{i} u∈F{′ \atop ≤}(w,succ(w))\W_{i} t≠u,W (t)=W (u)} d_{t,u}^{v,w} + ∑_{t∈F{′ \atop ≤}(w,succ(w))\W_{i} with v∉F{′ \atop ≤}(pre(t),t)} d_{v}^{w,t}

holds for 2 ≤ i ≤ n − 1, since for i = n − 1 the index sets of the last two sums are empty. Using (4.1c) and (4.8), we see that

∑_{{f∈F{′ \atop ≤}(pre(v),v) \atop g∈F{′ \atop ≤}(pre(w),w)}} d_{v,w}^{f,g} = d_{vw}^{(i)} + ∑_{t∈W_{i}∩F{′ \atop ≤}(v,succ(v)) u∈W_{i}∩F{′ \atop ≤}(w,succ(w)) t≠u} d_{t,u}^{v,w} + ∑_{t∈W_{i}∩F{′ \atop ≤}(w,succ(w)) with v∉F{′ \atop ≤}(pre(t),t)} d_{v}^{w,t}

holds for all nodes v, w ∈ W_{i−1} with v ≠ w. For t ∈ W_{i} ∩ F′_{≤}(v, succ(v)) = F′_{≤}(v, W_{i}) and u ∈ W_{i} ∩ F′_{≤}(w, succ(w)) = F′_{≤}(w, W_{i}) with t ≠ u there exist v_{(v,t)}, v_{(w,u)} ∈ Ṽ_{i} with (v_{(v,t)}, v_{(w,u)}) ∈ E′_{i} and, using the definitions, d_{(v_{vt},v_{wu})}^{(i)} = d_{t,u}^{v,w}. On the other hand, for all edges e = (v_{vt}, v_{wu}) ∈ E′_{i}(Ṽ_{i}, Ṽ_{i}) there exist nodes t, u ∈ W_{i} with t ≠ u and (v, t), (w, u) ∈ E′_{≤}(U_{i−1}, W_{i}). Likewise, for exactly those t ∈ F′_{≤}(w, W_{i}) with v ∉ F′_{≤}(pre(t), t) there exists a node v_{(w,t)} ∈ Ṽ_{i} such that (v, v_{(w,t)}) ∈ E′_{i} and d_{(v,v_{wt})}^{(i)} = d_{v}^{w,t} holds. For e = (v_{vt}, v_{wu}) ∈ E′_{i} or e = (v, v_{wt}) ∈ E′_{i} we have x̃_{e}^{(i)} = x_{vw}.

For e = (v_{e_{1}}, v_{e_{2}}) ∈ E′_{i−1} as above it follows that x_{e}^{(i−1)} = x_{vw}. Therefore, for fixed v, w ∈ W_{i−1} with v ≠ w we have

(4.9)  ∑_{{e=(v_{fv} ,vgw) \atop ∈E{′ \atop i−1}(Ṽ_{i−1},Ṽ_{i−1})}} d_{e}^{(i−1)}(x_{e}^{(i−1)}) = d_{vw}^{(i)}(x̃_{vw}^{(i)}) + ∑_{{e=(v,vwu)∈E′_{i}(v,Ṽ_{i}) \atop with v∉F{′ \atop ≤}(pre(u),u)}} d_{e}^{(i)}(x̃_{e}^{(i)})

+ ∑_{e=(v_{vt},v_{wu})∈E′_{i}(Ṽ_{i},Ṽ_{i})} d_{e}^{(i)}(x̃_{e}^{(i)}).

Here, the sum on the left-hand side is taken over all edges e ∈ E′_{i−1}(Ṽ_{i−1}, Ṽ_{i−1}) which can be written as e = (v_{fv}, v_{gw}) with some f ∈ F′_{≤}(pre(v), v) and g ∈ F′_{≤}(pre(w), w).

(iv) Let e = (f, v\overline{e}) ∈ E′_{i}(U_{i−1}, Ṽ_{i}) with \overline{e} = (f, v) ∈ E′_{≤}(U_{i−1}, W_{i}). Since x̃_{e}^{(i)} = x_{ff} we have

d_{e}^{(i)}(x̃_{e}^{(i)}) = 0.

(v) Let f, g ∈ U_{i−2} with f ≠ g. Using the definition of d_{fg}^{(i−1)} and the same way of reasoning as in case (iii), we arrive at

(4.10)  d_{fg}^{(i−1)}(x_{fg}^{(i−1)}) = d_{fg}^{(i)}(x̃_{fg}^{(i)}) + ∑_{{e=(f,vgv)∈E′_{i}(U_{i−2},Ṽ_{i}) \atop with f∉F{′ \atop ≤}(pre(v),v)} ; gv∈E{′ \atop ≤}} d_{e}^{(i)}(x̃_{e}^{(i)})

+ ∑_{e=(v_{fu},v_{gv})∈E′_{i}(Ṽ_{i},Ṽ_{i})} d_{e}^{(i)}(x̃_{e}^{(i)}).

(vi) Let e = (f, v\overline{e}) ∈ E′_{i−1}(U_{i−2}, Ṽ_{i−1}) with \overline{e} = (f, v) ∈ E′_{≤}(U_{i−2}, W_{i−1}). Using (4.1e) and the ideas that lead to (4.8), we see that

d_{(f,v\overline{e})}^{(i−1)}(x_{(f,v\overline{e})}^{(i−1)}) = d_{fv}^{(i)}(x̃_{fv}^{(i)}) + d_{vf}^{(i)}(x̃_{vf}^{(i)}) + ∑_{{e=(v_{ft},vvu)∈E′_{i}(Ṽ_{i},Ṽ_{i})(t≠u) \atop e=(vvu,v_{ft})∈E′_{i}(Ṽ_{i},Ṽ_{i})(t≠u)}} d_{e}^{(i)}(x̃_{e}^{(i)}) (4.11)

+ ∑_{{e=(f,vvu)∈E′_{i}(f,Ṽ_{i}) \atop with f∉F{′ \atop ≤}(pre(u),u)}} d_{e}^{(i)}(x̃_{e}^{(i)}) + ∑_{{e=(v,v_{fu})∈E′_{i}(v,Ṽ_{i}) \atop with v∉F{′ \atop ≤}(pre(u),u)}} d_{e}^{(i)}(x̃_{e}^{(i)})

14 JÖRG FLIEGE

holds.

(vii) Let (h, v\overline{e}) ∈ E′_{i−1}(U_{i−2}, Ṽ_{i−1}) with \overline{e} = (f, v) ∈ E′_{≤}(U_{i−2}, W_{i−1}), but (h, v) ∉ E′_{≤}(U_{i−2}, W_{i−1}). Using (4.1d) and the ideas leading to (4.8) again, we get

∑_{{\overline{e}=(f,v)∈E{′ \atop ≤}(U_{i−2},W_{i−1}) \atop with h∉F{′ \atop ≤}(pre(v),v)}} d_{(h,v\overline{e})}^{(i−1)}(x_{(h,v\overline{e})}^{(i−1)}) = d_{hv}^{(i)}(x̃_{hv}^{(i)}) + d_{vh}^{(i)}(x̃_{vh}^{(i)})

+ ∑_{{e=(v_{ht},vvu)∈E′_{i}(Ṽ_{i},Ṽ_{i}) \atop e=(vvu,v_{ht})∈E′_{i}(Ṽ_{i},Ṽ_{i})} ; t≠u} d_{e}^{(i)}(x̃_{e}^{(i)}) + ∑_{{e=(h,vvu)∈E′_{i}(h,Ṽ_{i}) \atop with h∉F{′ \atop ≤}(pre(u),u)}} d_{e}^{(i)}(x̃_{e}^{(i)}) (4.12)

+ ∑_{{e=(v,v_{hu})∈E′_{i}(v,Ṽ_{i}) \atop with v∉F{′ \atop ≤}(pre(u),u)}} d_{e}^{(i)}(x̃_{e}^{(i)}).

We have examined all edges necessary for the rest of the proof. We see that

Ψ′_{i−1}((x_{v}^{(i−1)})_{v∈V_{i−1}}) = ∑_{e∈E′_{i−1}} d_{e}^{(i−1)}(x_{e}^{(i−1)})

= ∑_{e∈E′_{i}(S,S)} d_{e}^{(i)}(x̃_{e}^{(i)})

because of the first case of the examination above,

+ ∑_{e∈E′_{i}(U_{i−1},S)} d_{e}^{(i)}(x̃_{e}^{(i)}) + ∑_{e∈E′_{i}(Ṽ_{i},S)} d_{e}^{(i)}(x̃_{e}^{(i)})

because of (4.7),

+ ∑_{e∈E′_{i−1}(F_{i−1}\S,F_{i−1}\S)} d_{e}^{(i−1)}(x_{e}^{(i−1)})

= ∑_{e∈E′_{i}(S,S)} d_{e}^{(i)}(x̃_{e}^{(i)}) + ∑_{e∈E′_{i}(U_{i−1},S)} d_{e}^{(i)}(x̃_{e}^{(i)}) + ∑_{e∈E′_{i}(Ṽ_{i},S)} d_{e}^{(i)}(x̃_{e}^{(i)})

+ ∑_{e∈E′_{i}(W_{i−1},W_{i−1})} d_{e}^{(i)}(x̃_{e}^{(i)}) + ∑_{{e=(v,vwu)∈E′_{i}(W_{i−1},Ṽ_{i}) \atop with v≠w∈W_{i−1},v∉F{′ \atop ≤}(pre(u),u)}} d_{e}^{(i)}(x̃_{e}^{(i)})

+ ∑_{{e=(v_{vt},vwu)∈E′_{i}(Ṽ_{i},Ṽ_{i}) \atop t,u∈W_{i}; v,w∈W_{i−1},v≠w}} d_{e}^{(i)}(x̃_{e}^{(i)})

because of (4.9),

+ ∑_{e∈E′_{i}(U_{i−2},U_{i−2})} d_{e}^{(i)}(x̃_{e}^{(i)}) + ∑_{{e=(f,vgw)∈E′_{i}(U_{i−2},Ṽ_{i}) \atop with f∉F{′ \atop ≤}(U_{i−2},w),g∈U_{i−2}\\{f\}}} d_{e}^{(i)}(x̃_{e}^{(i)})

+ ∑_{{e=(v_{fu},vgw)∈E′_{i}(Ṽ_{i},Ṽ_{i}) \atop with f,g∈U_{i−2}}} d_{e}^{(i)}(x̃_{e}^{(i)})

because of (4.10),

+ ∑_{fv∈E′_{≤}(U_{i−2},W_{i−1})} (d_{fv}^{(i)}(x̃_{fv}^{(i)}) + d_{vf}^{(i)}(x̃_{vf}^{(i)}) + ∑_{{e=(v,v_{fu})∈E′_{i}(v,Ṽ_{i}) \atop with v∉F{′ \atop ≤}(pre(u),u)}} d_{e}^{(i)}(x̃_{e}^{(i)})

+ ∑_{{e=(f,vvu)∈E′_{i}(f,Ṽ_{i}) \atop with f∉F{′ \atop ≤}(pre(u),u)}} d_{e}^{(i)}(x̃_{e}^{(i)}) + ∑_{{e=(v_{ft},vvu)∈E′_{i}(Ṽ_{i},Ṽ_{i})(t≠u) \atop e=(vvu,v_{ft})∈E′_{i}(Ṽ_{i},Ṽ_{i})(t≠u)}} d_{e}^{(i)}(x̃_{e}^{(i)}))

because of (4.11),

+ ∑_{(h,v)∈E′_{i}(U_{i−2},W_{i−1}) with h∉F{′ \atop ≤}(pre(v),v)} (d_{hv}^{(i)}(x̃_{hv}^{(i)}) + d_{vh}^{(i)}(x̃_{vh}^{(i)}) + ∑_{{e=(h,vvu)∈E′_{i}(U_{i−2},Ṽ_{i}) \atop with h∉F{′ \atop ≤}(pre(u),u)}} d_{e}^{(i)}(x̃_{e}^{(i)})

+ ∑_{{e=(v_{ht},vvu)∈E′_{i}(Ṽ_{i},Ṽ_{i}) \atop e=(vvu,v_{ht})∈E′_{i}(Ṽ_{i},Ṽ_{i})} ; t≠u} d_{e}^{(i)}(x̃_{e}^{(i)}) + ∑_{{e=(v,v_{hu})∈E′_{i}(W_{i−1},Ṽ_{i}) \atop with v∉F{′ \atop ≤}(pre(u),u)}} d_{e}^{(i)}(x̃_{e}^{(i)}))

because of (4.12),

= ∑_{e∈E′_{i}(S,S)} d_{e}^{(i)}(x̃_{e}^{(i)}) + ∑_{e∈E′_{i}(U_{i−1},S)} d_{e}^{(i)}(x̃_{e}^{(i)}) + ∑_{e∈E′_{i}(Ṽ_{i},S)} d_{e}^{(i)}(x̃_{e}^{(i)})

+ ∑_{e∈E′_{i}(U_{i−2},U_{i−2})} d_{e}^{(i)}(x̃_{e}^{(i)}) + ∑_{e∈E′_{i}(W_{i−1},W_{i−1})} d_{e}^{(i)}(x̃_{e}^{(i)}) + ∑_{e∈E′_{i}(U_{i−2},W_{i−1})} d_{e}^{(i)}(x̃_{e}^{(i)})

+ ∑_{e∈E′_{i}(W_{i−1},Ṽ_{i})} d_{e}^{(i)}(x̃_{e}^{(i)}) + ∑_{e∈E′_{i}(Ṽ_{i},Ṽ_{i})} d_{e}^{(i)}(x̃_{e}^{(i)}) + ∑_{e∈E′_{i}(U_{i−2},Ṽ_{i})} d_{e}^{(i)}(x̃_{e}^{(i)}),

since d_{e}^{(i)}(x̃_{e}^{(i)}) = 0 for e = (f, v\overline{e}) ∈ E′_{i}(U_{i−1}, Ṽ_{i}) with \overline{e} = (f, v) ∈ E′_{≤}(U_{i−1}, W_{i}). This means that

Ψ′_{i−1}((x_{v}^{(i−1)})_{v∈V_{i−1}}) = Ψ′_{i}((x̃_{v}^{(i)})_{v∈V_{i}}).

The next part of the proof consists of showing

Ψ′((x̂_{v})_{v∈V}) = Ψ′_{1}((x̃_{v}^{(1)})_{v∈V_{1}}). (4.13)

Let s ∈ S be fixed. For i = 1, …, n − 1, we have

∑_{fv∈E′_{≤}(U_{i−1},U_{n−1}\U_{i−1})} d_{s}^{f,v} = ∑_{j=i}^{n−1} ∑_{v∈W_{j}} ∑_{f∈F′_{≤}(U_{i−1},v)} d_{s}^{f,v}

= ∑_{v∈W_{i}} ( ∑_{vs∈E} d_{vs} + ∑_{u∈F′_{≤}(v,succ(v))} d_{s}^{v,u}) + ∑_{j=i+1}^{n−1} ∑_{v∈W_{j}} ∑_{f∈F′_{≤}(U_{i−1},v)} d_{s}^{f,v}

because of (4.1b),

= ∑_{e∈E(W_{i},s)} d_{e} + ∑_{fv∈E′_{≤}(U_{i},U_{n−1}\U_{i})} d_{s}^{f,v}.

Using this, it is possible to show that

∑_{fv∈E′_{≤}(U_{i−1},U_{n−1}\U_{i−1})} d_{s}^{f,v} = ∑_{e∈E′_{≤}(U_{n−1}\U_{i−1},s)} d_{e} (4.14)

holds for 1 ≤ i ≤ n − 1. This can be done by induction starting at i = n − 1 and ending at i = 1 and is omitted here. Because of (4.2), we see that for all k ∈ K we have

d_{ks}^{(1)} = ∑_{ks∈E′} d_{ks} + ∑_{j=2}^{n−1} ∑_{v∈F′_{≤}(k,W_{j})} d_{s}^{k,v}.

For exactly those v ∈ F′_{≤}(k, W_{1}) with e := (k, v) ∈ E′_{≤} there exists a node v_{e} ∈ Ṽ_{1} with (v_{e}, s) ∈ E′_{1}. For this edge (v_{e}, s) we have d_{(v_{e},s)}^{(1)} = d_{s}^{k,v}. This means that

∑_{e∈E′_{1}(K∪Ṽ ,s)} d_{e}^{(1)} = ∑_{k∈K} (d_{ks} + ∑_{j=1}^{n−1} ∑_{v∈F′_{≤}(k,W_{j})} d_{s}^{k,v}).

Taking i = 1 in (4.14), the equation

∑_{e∈E′_{1}(K∪Ṽ ,s)} d_{e}^{(1)} = ∑_{e∈E(K,s)} d_{e} + ∑_{j=1}^{n−1} ∑_{e∈E′(W_{j},s)} d_{e} = ∑_{e∈E(F \S,s)} d_{e}

follows. But we have x̃_{e}^{(1)} = (x, x_{s}) for e ∈ E′_{1}(K, s) or e ∈ E′_{1}(Ṽ_{1}, s) and therefore

∑_{s∈S} ∑_{e∈E′(F \S,s)} d_{e}(x, x_{s}) = ∑_{e∈E′_{1}(K∪Ṽ_{1},S)} d_{e}^{(1)}(x̃_{e}^{(1)}). (4.15)

The edge set E′_{1} can be written as

E′_{1} = (K × K) \ {(k, k) | k ∈ K} ∪· (K × S) ∪· E′(S, S)
∪· (Ṽ_{1} × S) ∪· E′_{1}(K, Ṽ_{1}) ∪· E′_{1}(Ṽ_{1}, Ṽ_{1}).

Because of x̃_{v_{e}}^{(1)} = x_{k} = x for all v_{e} ∈ Ṽ_{1} with e = (k, v) ∈ E′_{≤}(K, W_{1}) and x_{k} = x for all k ∈ K we have that d_{e}^{(1)}(x̃_{e}^{(1)}) = 0 holds for all e ∈ E′_{1}(K, Ṽ_{1}) ∪ E′_{1}(Ṽ_{1}, Ṽ_{1}) ∪ (K × K) \ {(k, k) | k ∈ K}. For e ∈ E′(S, S) it is d_{e}^{(1)} = d_{e} and x̃_{e}^{(1)} = x_{e}. Therefore, (4.15) leads to

Ψ′((x̂_{v})_{v∈V}) = ∑_{e=vs∈E′(F \S,S)} d_{e}(x, x_{s}) + ∑_{e∈E(S,S)} d_{e}(x_{e}).

Since x̂_{v} = x for all v ∈ F \ S, (4.13) follows.

By (4.3) and (4.4) we now have the chain of inequalities

Ψ′((x̂_{v})_{v∈V}) = Ψ′_{1}((x̃_{v}^{(1)})_{v∈V_{1}})
≤ Ψ′_{1}((x_{v}^{(1)})_{v∈V_{1}}) ≤ …
≤ Ψ′_{n−1}((x_{v}^{(n−1)})_{v∈V_{n−1}})
= Ψ′((x_{v})_{v∈V})
≤ Ψ((x_{v})_{v∈V}),

since d_{e}(x_{e}) ≥ 0 for all e ∈ E_{s}. Because of d_{e}(x̂_{e}) = 0 for all e ∈ E_{s} it follows that

Ψ′((x̂_{v})_{v∈V}) = Ψ((x̂_{v})_{v∈V})

holds. Therefore,

Ψ((x̂_{v})_{v∈V}) ≤ Ψ((x_{v})_{v∈V}).

This inequality is strict if there exists a node v ∈ U and a node f ∈ F′_{≤}(pre(v), v) with x_{f} ≠ x_{v} such that (4.1a) is strict for all arguments (x, y) ∈ (X × X) \ Δ. Because of

Ψ((x̂_{v})_{v∈V}) = Ψ′((x̂_{v})_{v∈V})
≤ Ψ′((x_{v})_{v∈V})
≤ Ψ′((x_{v})_{v∈V}) + ∑_{e∈E_{s}} d_{e}(x_{e})
= Ψ((x_{v})_{v∈V}),

it follows that Ψ((x̂_{v})_{v∈V}) < Ψ((x_{v})_{v∈V}) whenever an edge e ∈ E_{s} exists such that d_{e}(x_{e}) ≠ 0 holds.

Some remarks about further generalizations to Theorem 2 can be found in [21]. That F′_{≤}(pre(v), v) ≠ ∅ has to hold for each v ∈ U means that each node not in the shell S is connected with the kernel K by a path of edges in E′_{≤}. This is a rather weak assumption, because we can always add an edge to this edge set and use the function d ≡ 0 on it. It may then be the case that the graph G is not simple any more, but this assumption can be dropped completely. However, this generalization leads to a much more tedious notation and is therefore left out here.

4.1. Some Examples. We will take a look at several rather simple examples to show how the criterion found in the theorem above can be applied to a given multifacility location problem.

Example 1. We use X = IR^{N}, A = {a, b, c}, V = {u, v, w},

E = {(a, u), (a, v), (u, b), (u, w), (v, c), (v, w)},

d_{au}(x, y) = ∥x − y∥_{1}, d_{av}(x, y) = ∥x − y∥_{2}, d_{ub}(x, y) = ω_{ub}∥x − y∥_{2}, and d_{vc}(x, y) = ω_{vc}∥x − y∥_{∞}. Here, let 0 ≤ ω_{ub}, ω_{vc} ≤ 1 and d_{uw} as well as d_{vw} be arbitrary metrics. Define E_{≥} = ∅, n = 2, K = {a}, S = {b, c}, W_{1} = V and E_{s} = {(u, w), (v, w)}. Because of our definition of E_{s}, the metrics d_{uw} and d_{vw} play no role whatsoever. By adding the edge (a, w) to the edge set, we see that we have F′_{≤}(pre(w), w) ≠ ∅. Of course, we use the distance cost function d_{aw}(x, y) = 0 on this edge, which does not change our optimization problem. Because of d_{ub} ≤ d_{au} and d_{vc} ≤ d_{av}, condition (4.1a) holds for u and v. Moreover, this condition is trivially true for w, as it is the case for (4.1b)–(4.1e). (For (4.1c), we simply choose ω_{u,w}^{a,a} = 0 etc.) We conclude that there is an optimal solution (x̂_{v})_{v∈V} with x̂_{u} = x̂_{v} = x̂_{w} = x_{a}. Moreover, in each minimum (x̂_{v})_{v∈V} of Ψ we have x̂_{u} = x̂_{v} = x̂_{w}, and if ω_{ub} < 1 we have x̂_{u} = x_{a} in every solution. Likewise, if ω_{vc} < 1 we have x̂_{v} = x_{a} in every solution. In this way, a sensitivity analysis on the weights is also possible.

Example 2. Let A = {a, b, c, d}, V = {u, v, w},

E = {(u, a), (u, b), (u, w), (v, a), (v, c), (v, w), (w, d)},

ω_{ua} = ω_{va} = 7, ω_{ub} = ω_{vc} = 2, ω_{uw} = ω_{vw} = 6, and ω_{wd} = 8. Furthermore, let Ψ((x_{u}, x_{v}, x_{w})) = ∑_{e∈E} ω_{e}d(x_{e}) with a symmetric weak metric d.

Define E_{≥} = E_{s} = ∅, n = 4, K = {a}, S = {b, c, d}, W_{1} = {u}, W_{2} = {v}, and W_{3} = {w}. Two threads will be used to proof the coincidence of every node in V with the node a. Both of them start at w and end at a, but while one of them passes through u, the node v is used by the other one. Since we are using two threads starting at w, we have to split up this node into two new ones. Because of the symmetry of d we may turn around edges as we wish, and we will do so by using (a, u) and (a, v) instead of (u, a) and (v, a). Since K contains only one element, we have trivially x_{k} = x for all k ∈ K and all families (x_{v})_{v∈V}. As ansatz functions we use

d_{s}^{f,v} = ω_{s}^{f,v}d, d_{v,w}^{f,g} = ω_{v,w}^{f,g}d, d_{h}^{f,v} = ω_{h}^{f,v}d, and d^{f,v} = ω^{f,v}d

for the corresponding nodes v, w, f, g, h, s ∈ F. We are now in search for weights

ω_{s}^{f,v}, ω_{v,w}^{f,g}, ω_{h}^{f,v}, ω^{f,v} ∈ IR

such that (4.1a)–(4.1e) holds. In order to fulfill (4.1b) with a weight ω_{d}^{u,w} and a weight ω_{d}^{v,w}, we have to choose these weights in such a way that the equality

ω_{d}^{u,w} + ω_{d}^{v,w} = ω_{wd} = 8

holds. Likewise, because (4.1a) has to hold, we have to choose them in such a way that additionally

ω_{d}^{u,w} ≤ ω_{uw} = 6

and

ω_{d}^{v,w} ≤ ω_{vw} = 6

holds. We take care of (4.1c) by defining ω_{a}^{u,w} := ω_{a}^{v,w} = 0. (Instead, we may consider (4.1a) for f := a. Because of ω_{aw} = 0 we then have to choose ω_{d}^{a,w} := 0.) As an example, we choose ω_{d}^{u,w} = 4 and ω_{d}^{v,w} = 4. With this and ω_{b}^{u,w} = ω_{c}^{u,w} = ω_{b}^{v,w} = ω_{c}^{v,w} = 0, (4.1a) and (4.1b) hold. If we follow the construction from the proof of Theorem 4, we see that G′_{3} = (F_{3}, E′_{3}) with F_{3} = A ∪ {u, v, v_{uw}, v_{vw}} and

E′_{3} = {(a, u), (u, a), (a, v), (v, a), (u, v), (v, u)} ∪· ({a, v, u} × {v_{vw}, v_{uw}})
∪· ({a, u, v, v_{vw}, v_{uw}} × {b, c, d}).

Of course, we have d_{ab}^{(3)} ≡ 0, d_{au}^{(3)} = ω_{au}d = 7d, d_{ua}^{(3)} ≡ 0, etc. Likewise, it is G′_{2} = (F_{2}, E′_{2}) with F_{2} = A ∪ {u, v_{av}} and

E′_{2} = {(a, u), (u, a), (a, v_{av}), (u, v_{av})} ∪· ({a, u, v_{av}} × {b, c, d}),

and, finally, G′_{1} = (F_{1}, E′_{1}) with F_{1} = A ∪ {v_{au}} and

E′_{1} = {(a, v_{au})} ∪· ({a, v_{au}} × {b, c, d}).

In G′_{2} we have strict attraction from the node v_{av} to the node a. Likewise, in G′_{1} we have strict attraction between the nodes v_{au} and a. This is so because we have chosen ω_{d}^{u,w} = ω_{d}^{v,w} = 4, a choice which leads subsequently to the equations ω_{d}^{a,u} = 4 and ω_{d}^{a,v} = 4. It follows that

Ψ((x̂_{v})_{v∈V}) ≤ Ψ((x_{v})_{v∈V})

for all (x_{v})_{v∈V} ∈ X^{V}. This inequality is strict if x_{w} ≠ x_{u} or x_{w} ≠ x_{v} or x_{v} ≠ x_{a} or x_{u} ≠ x_{a}. An analogous derivation can be achieved by setting n = 3, W_{1} := {u, v} and W_{2} := {w}.

Example 3. We use the location problem defined in Example 2 but add the edge (u, v) with the weight ω_{uv} = −1/2 to the graph G. In this case we have to use E_{≥} := {(u, v)}, ω_{u}^{a,v} = −1/2, and ω^{a,u} = 13/2.

Example 4. Consider the case in which we add not only the edge (u, v) with ω_{uv} = −1/2 to the graph in Example 2, but also the edge (a, w) with the weight ω_{aw} = −1/2. With this, we define E_{≥} := {(a, w), (u, v)}. Using the same partition as above, we choose ω_{d}^{u,w} = 4 and ω_{d}^{v,w} = 4. But because of (4.1d), we have to choose weights ω_{a}^{u,w} and ω_{a}^{v,w} with

ω_{a}^{u,w} + ω_{a}^{v,w} = ω_{aw} = −1/2,

such that with the weights ω_{d}^{u,w} and ω_{d}^{v,w} as above we still have (4.1a) and (4.1e). This can be done, for example, by choosing ω_{a}^{u,w} := ω_{a}^{v,w} := −1/4. With this, the collapse as above is allowed. The equations ω^{a,v} = 27/4 and ω^{a,u} = 25/4 follow immediately. We still have strict attraction in G′_{1} together with the final result.

The approach chosen in Example 2–4 is used in a companion paper [25] to develop a polynomial time algorithm for checking the criterion presented in Theorem 4. There, we present numerical results which show that by using this algorithm in conjunction with a nonlinear optimization code it is possible to reduce the computation time of the code while simultaneously enhancing the quality of the solution found.

REFERENCES

[1] K. D. Andersen, An efficient Newton barrier method for minimizing a sum of Euclidean norms, SIAM Journal of Optimization, 6 (1996), pp. 74–95.

[2] K. D. Andersen and E. Christiansen, A Newton Barrier method for Minimizing a Sum of Euclidean Norms subject to linear equality constraints, Preprint 95-07, Odense University, Department of Mathematics and Computer Science, Odense University, Denmark, February 13 1995. Electronically distributed as

ftp://ftp.imada.ou.dk/pub/papers/preprints95/preprint-95-07.ps.gz

[3] , A symmetric Primal-Dual Newton method for Minimizing a Sum of Norms. Electron-

ically distributed as ftp://info.mcs.anl.gov/pub/tech_reports/ip/pdsn.ps.Z, April 11

1995.

[4] K. D. Andersen, E. Christiansen, and M. L. Overton, Computing limit loads by minimizing a sum of norms. Unpublished, October 17 1994.

[5] P. H. Calamai and A. R. Conn, A projected Newton method for l_{p} norm location problems, Mathematical Programming, 38 (1987), pp. 75–109.

[6] E. Carrizosa and A. M. Rodríguez-Chía, Weber problem with alternative transportation systems, European Journal of Operation Research, 97 (1997), pp. 87–93.

[7] P.-C. Chen, P. Hansen, B. Jaumard, and H. Tuy, Solution of the Multisource Weber and Conditional Weber Problems by D.-C. Programming, Les Cahiers du GERAD / Groupe d’études et de recherche en analyse des décisions G–92–35, École Polytechnique, Montreal, Quebec, September 1992. Revised: March 1994.

[8] , Weber’s problem with attraction and repulsion, Journal of Regional Science, 32 (1992), pp. 467–486.

[9] R. Cominetti and C. Michelot, Sufficient conditions for coincidence in ℓ_{1}-minisum multifacility location problems, Operations Research Letters, 20 (1997), pp. 179–185.

[10] A. R. Conn and M. L. Overton, A Primal-Dual Interior Point Method for Minimizing a Sum of Euclidean Distances. Unpublished, July 20 1994.

[11] A. Dax, An Efficient Algorithm for Solving Rectilinear Multifacility Location Problems, IMA Journal of Numerical Analysis, 6 (1986), pp. 343–355.

[12] , A note on Optimality Conditions for the Euclidean Multifacility Location Problems, Mathematical Programming, 36 (1986), pp. 72–80.

[13] Z. Drezner, ed., Facility Location: A Survey of Applications and Methods, Springer Series in Operations Research, Springer Verlag, New York, 1995.

[14] Z. Drezner and G. O. Wesolowsky, The Weber problem on the plane with some negative weights, INFOR, 29 (1991), pp. 87–99.

[15] H. A. Eiselt and G. Laporte, Objectives in Location Problems, in Drezner [13], ch. 8, pp. 151– 180.

[16] E. Erkut and S. Newman, Analytical models for locating undesirable facilities, European Journal of Operation Research, 40 (1989), pp. 275–291.

[17] J. W. Eyster, J. A. White, and W. W. Wierwille, On Solving Multifacility Location Problems Using a Hyperboloid Approximation Procedure, AIIE Transactions, 5 (1973), pp. 1–6.

[18] A. Fajfar, Verbesserung von Schnittebenenverfahren zur Lösung von Minisum-Multilokationsproblemen, Diplomarbeit, Universität Dortmund, Fachbereich Mathematik, Universität Dortmund, 44221 Dortmund, Germany, March 1996.

[19] J. Fliege, Nichtdiskrete Multilokationsprobleme: Koinzidenzbedingungen und effiziente Punkte, Diplomarbeit, Universität Dortmund, Fachbereich Mathematik, Universität Dortmund, 44221 Dortmund, Germany, February 1993.

[20] , Some new coincidence conditions in minisum multifacility location problems with mixed gauges, in EWGLA 7 Proceedings, B. Boffey and J. Karkazis, eds., no. 7 in Studies in Locational Analysis, Smirnis 1, Zografu, Athens 15772, Greece, November 1994, Constantine Porphyrogenetus International Association, pp. 49–60.

[21] , Effiziente Dimensionsreduktion in Multilokationsproblemen, PhD thesis, Universität Dortmund, Fachbereich Mathematik, Universität Dortmund, 44221 Dortmund, June 1997. Shaker Verlag, Aachen, Germany. (An english translation is available from the author on request.).

[22] , Nondifferentiability Detection and Dimensionality Reduction in Minisum Multifacility Location Problems, Journal of Optimization Theory and Applications, 94 (1997), pp. 365– 380.

[23] , Some polynomial time algorithms for multifacility location problems with mixed gauges. Talk held at Modellierungsseminar im Rahmen von MISP (Location Planning: Theory and Application), Universität Kaiserslautern, Kaiserslautern, Germany, February 1997.

[24] , Coincidence conditions in multifacility location problems with positive and negative weights, European Journal of Operations Research, 104 (1998), pp. 310–320. Feature Issue. Twelveth [sic!] EURO Summer Institute: Locational Analysis. Guest Editor: J[aime] Barceló.

[25] , Special Cases and Efficient Algorithms for Multithreaded Dimension Reduction in Location Theory, Ergebnisberichte Angewandte Mathematik 154, Universität Dortmund, Fachbereich Mathematik, Universität Dortmund, 44221 Dortmund, Germany, April 1998. Submitted to SIAM Journal on Optimization.

[26] J. B. G. Frenk. Course notes on Location Theory, 1996.

[27] J. B. G. Frenk and M. J. Kleijn, On a Class of Algorithms solving the Multifacility Location Problem with Perturbed l_{p}-distances, Discussion paper TI 94–74, Tinbergen Institute, Tinbergen Institute Rotterdam, Oostmaaslaan 950–952, 3063 DM Rotterdam, The Netherlands, 1994.

[28] , On Miehle’s Algorithm and the Perturbed L_{p}-distance Multifacility Location Problem, Discussion paper TI 94–54, Tinbergen Institute, Tinbergen Institute Rotterdam, Oostmaaslaan 950–952, 3063 DM Rotterdam, The Netherlands, 1994.

[29] J. B. G. Frenk, M. T. Melo, and S. Zhang, The Weiszfeld method in single facility location, Investigação Operacional, 14 (1994), pp. 35–59.

[30] P. Hansen, J. Perreur, and J.-F. Thisse, Location Theory, Dominance, and Convexity: Some Further Results, Operation Research, 28 (1980), pp. 1241–1250.

[31] H. Idrissi, O. Lefebvre, and C. Michelot, Duality for constrained multifacility location problems with mixed norms and applications, vol. 18 of Annals of Operations Research, Basel, Switzerland, February 1989, J. C. Baltzer AG Scientific Publishing Company, pp. 71– 92.

[32] H. Juel and R. F. Love, Sufficient conditions for Optimal Facility Locations to Coincide, Transportation Science, 14 (1980), pp. 125–129.

[33] J. E. Kelley, The cutting plane methods for solving convex programs, Journal of the Society of Industrial and Applied Mathematics, 8 (1960), pp. 703–712.

[34] O. Lefebvre, C. Michelot, and F. Plastria, Geometric Interpretation of the Optimality Conditions in Multifacility Location and Applications, Journal of Optimization Theory and Applications, 65 (1990), pp. 85–101.

[35] , Errata corrige Geometric Interpretation of the Optimality Conditions in Multifacility Location and Applications, Journal of Optimization Theory and Applications, 68 (1991), pp. 393–394.

[36] , Sufficient conditions for coincidence in minisum multifacility location problems with a general metric, Operation Research, 39 (1991), pp. 437–442.

[37] , Boolean linear programming formulation of the attraction tree detection problem, in Proceedings of the VIth meeting of the EURO working group on locational analysis, J. A. M. Pérez, ed., Puerto de La Cruz (Tenerife), Spain, October 1992, pp. 123–134.

[38] H. Minkowski, Gesammelte Abhandlungen, vol. 2, Chelsea Publishing Company, New York, 1967. Reprint.

[39] L. N. Moses, Location and the theory of production, Journal of Economics, 72 (1958), pp. 259– 272.

[40] M. L. Overton, A quadratically convergent method for minimizing a sum of euclidean norms, Mathematical Programming, 27 (1983), pp. 34–63.

[41] G. Pesamosca and F. Mazzarella, The analytical solution of some EMFL minisum problems, Edmonton and Jasper, Canada, June 26 – July 3 1996. Talk held at the Seventh International Symposium on Locational Decisions, ISOLDE VII.

[42] J.-C. Picard and H. D. Ratliff, A Cut Approach to the Rectilinear Distance Facility Location Problem, Operation Research, 26 (1978), pp. 422–433.

[43] F. Plastria, The effects of majority in Fermat-Weber problems with attraction and repulsion in a pseudometric space, Yugoslav Journal of Operations Research, 1 (1991), pp. 141–146.

[44] , A majority theorem for Fermat-Weber problems in quasimetric spaces with applications to semidirected networks, in Proceedings of the VIth meeting of the EURO working group on locational analysis, no. 5 in Serie Informes, Secretariado de Publicaciones, Puerto de La Cruz (Tenerife), Spain, April 1992, pp. 153–165.

[45] , When Facilities Coincide: Exact Optimality Conditions in Multifacility Location, Journal of Mathematical Analysis and Applications, 169 (1992), pp. 476–498.

[46] , Continuous location anno 1992: a progress report, in ISOLDE VI SURVEY PAPERS, B. Boffey and J. Karkazis, eds., no. 5 in Studies in Locational Analysis, Juni 1993, pp. 85– 127. Republished as [47].

[47] , Continuous Location Problems, in Drezner [13], ch. 11, pp. 225–262.

[48] , Asymmetric distances, semidirected networks and majority in Fermat-Weber problems, Report BEIF/96, Center for Management Informatics, Vrije Universiteit Brussel, Belgium, April 1997. Submitted.

[49] H. Ribeiro, Sur les espaces à métrique faible, Portugaliae Mathematica, 4 (1943), pp. 21–40.

[50] H. D. Sherali and I. Al-Loughani, Equivalent Primal and Dual Differentiable Reformulations of the Euclidean Multifacility Location Problem, Report HDS96-7, Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061-0118, USA, June 1996.

[51] L.-N. Tellier and B. Polanski, The Weber problem: frequency of different solution types and extension to repulsive forces and dynamic processes, Journal of Regional Science, 29 (1989), pp. 387–405.

[52] H. Tuy, F. Al-Khayyal, and F. Zhou, A D. C. Optimization Method for Single Facility Location, Jounral of Global Optimization, 7 (1995), pp. 209–227.

[53] J. E. Ward and R. E. Wendell, Using Block Norms for Location Modelling, Operation Research, 33 (1985), pp. 1074–1090.

[54] G. O. Wesolowsky and R. F. Love, A nonlinear approximation method for solving a generalized rectangular distance Weber problem, Management Science, 18 (1972), pp. 656–663.

[55] C. Witzgall, Optimal Location of a Central Facility, Mathematical Models and Concepts, Tech. Report 8388, National Bureau of Standards, Applied Mathematics Division, Operations Research Section, U. S. Department of Commerce, Washington, D. C., June 30 1964.

[56] , On Convex Metrics, JOURNAL OF RESEARCH of the National Bureau of Standards— B. Mathematics and Mathematical Physics, 69B (1965), pp. 175–177.

[57] P. Wolfe, Convergence theory in nonlinear programming, in Integer and Nonlinear Programming, J. Abadie, ed., North-Holland Publishing Company, Amsterdam, London, 1970, ch. 1, pp. 1–36.

[58] G. Xue and Y. Ye, An Efficient Algorithm for Minimizing a Sum of Euclidean Norms with Applications, SIAM Journal on Optimization, 7 (1997), pp. 1017–1036.

[59] G. L. Xue, J. B. Rosen, and P. M. Pardalos, A polynomial time dual algorithm for the Euclidean multifacility location problem, Operations Research Letters, 18 (1996), pp. 201–