SOME NEW COINCIDENCE CONDITIONS IN

MINISUM MULTIFACILITY LOCATION

PROBLEMS WITH MIXED GAUGES

Jörg Fliege

University of Dortmund Fachbereich Mathematik, 44221 Dortmund Tel.: 0231 / 755–5415 e-mail: fliege@euler.mathematik.uni-dortmund.de

Abstract

In minisum multifacility location problems the optimal locations of clusters of facilities frequently tend to coincide. Several conditions for coincidence using attraction trees have been published recently. These conditions are extended and improved to more general location problems. Using trees of sets of facilities, new sufficient coincidence conditions for location problems with mixed asymmetric gauges are given. Moreover, sufficient conditions are formulated, which only involve the given weights and certain values from a preprocessing step.

Keywords: Coincidence conditions, multifacility location problem, gauges.

Fliege: New Coincidence Conditions in Multifacility Location Problems

The minisum multifacility location problem could be stated as follows: let A be a set of fixed facilities located at x_{a} ∈ IR^{N} (a ∈ A) and V be a set of new facilities, which locations x_{v} ∈ IR^{N} (v ∈ V) should be chosen so as to minimize the weighted sum of some of the distances between the facilities. The distances between pairs of points in IR^{N} are measured with arbitrary gauges, a notion that goes back to Minkowski [5, pp. 131 – 135].

1 Preliminaries

1.1 Gauges

Definition 1.1 (Gauges) If B ⊂ IR^{N} is a convex, compact set with 0 ∈ int(B), the gauge γ of B is given by

γ(x) := inf{λ > 0 | x ∈ λB}.

The gauge of −B will be denoted by \overline{γ}.

Obviously, there is \overline{γ}(x) = γ(−x) for all x ∈ IR^{N}. Gauges are nonnegative, positive homogeneous, convex and finite-valued functions. Particularly, the triangle inequality,

γ(x − y) ≤ γ(x − z) + γ(z − y),

holds for all x, y, z ∈ IR^{N}. Moreover, one has γ(x) = 0 if and only if x = 0. Any function γ with all these features is a gauge of the compact convex unit ball B := {x ∈ IR^{N} | γ(x) ≤ 1}. Consequently, any positive linear combination of gauges is a gauge. But not every gauge is a norm: this holds only for symmetric unit balls B.

1.1.1 Comparison of Gauges

The “comparison step” should be a significant part of any computer code for testing coincidence conditions of the minisum multifacility location problem with mixed gauges. In this step two or more gauges are examined in order to find the one which is the “strongest”, i. e. the one which measures greater distances between pairs of points than the other gauges. This subsection shows an efficient way of transforming this task into a problem which could be solved in a preprocessing step.

Theorem 1.2 Let γ_{1} and γ_{2} be gauges. Then there exist two values α, β > 0 with

αγ_{1}(x) ≤ γ_{2}(x) ≤ βγ_{1}(x) for all x ∈ IR^{N}.  (1)

Proof: Let B_{1} and B_{2} be the unit balls of γ_{1} and γ_{2}. Choose α > 0 with αB_{2} ⊆ B_{1}. Then B_{2} ⊆ (1/α)B_{1} and one has for all x ∈ IR^{N}, that

αγ_{1}(x) = γ_{1}(αx) = inf{λ > 0 | x ∈ (λ/α)B_{1}}
≤ inf{λ > 0 | x ∈ λB_{2}} = γ_{2}(x).

For any β′ > 0 with β′B_{1} ⊆ B_{2} one has β′γ_{2}(x) ≤ γ_{1}(x) and with β := 1/β′ the result holds. □

Therefore, it is necessary and sufficient for (1) that

αB_{2} ⊆ B_{1} ⊆ βB_{2};

moreover, the estimate (1) cannot be improved, if

α = sup{μ > 0 | μB_{2} ⊆ B_{1}}  (2)

and

β = inf{μ > 0 | B_{1} ⊆ μB_{2}}.  (3)

Definition 1.3 (Comparison Factors) If two gauges γ_{1} and γ_{2} are given, then two scalars α, β > 0 with (1) are named lower and upper comparison factors of γ_{1} and γ_{2}.

If α satisfies (2), then α is named best lower comparison factor of γ_{1} and γ_{2}; if β satisfies (3), then β is named best upper comparison factor of γ_{1} and γ_{2}.

Plastria [7] defines a similar concept for distances defined by a quasimetric, the asymmetric equivalent of a metric. In the notation used here the skewness factor defined in [7] is the best upper comparison factor between a gauge γ and \overline{γ}.

1.2 Graphs

If F is a nonempty set and E ⊆ F × F is given, then G := (F, E) is named directed graph with node set F and edge set E. The notation uv will shortly refer to an edge (u, v) ∈ E.

For two subsets U_{1}, U_{2} ⊆ F, the set E(U_{1}, U_{2}) := E ∩ (U_{1} × U_{2}) denotes the set of edges that run from a node in U_{1} to a node in U_{2}. Also, let

E(U_{1}, U_{2}) := E(U_{2}, U_{1}) := E(U_{1}, U_{2}) ∪ E(U_{2}, U_{1}).

For a node f ∈ F and a subset U ⊆ F let E(f, U) := E({f}, U) be the set of edges which run from f into U. Similarly, let E(U, f) := E(U, {f}).

2 Formulation of the Problem

In what follows, let F be a nonempty, finite set of nodes, ∅ ≠ E ⊆ F ×F and G := (F, E) be a directed graph. The node set F represents a set of facilities, while the edge set E corresponds to interactions between these objects. Let the node set F be partitioned into the nonempty sets A and V. For all a ∈ A let a fixed vector x_{a} ∈ IR^{N} be given. The nodes v ∈ V represent facilities for which the best location is still unknown. For every edge e ∈ E let there be given a weight ω_{e} ≥ 0 and a gauge γ_{e}. The cost of the interaction between two nodes connected by an edge is measured by the corresponding gauge, the weight ω_{e} serves as a proportionality factor. The set of families (x_{v})_{v∈V} with x_{v} ∈ IR^{N} for all v ∈ V will be denoted by (IR^{N})^{V}. This is just the domain of the objective function. Now, let in addition to the vectors x_{a} ∈ IR^{N} (a ∈ A), a family (x_{v})_{v∈V} ∈ (IR^{N})^{V} be given. For any edge e = (f, g) ∈ E set x_{e} := x_{f} − x_{g}. The length of this vector will be measured with the gauge γ_{e}. Sometimes, a second family (x̂_{v})_{v∈V} is needed. Then the notation x̂_{e} := x̂_{f} − x̂_{g} (where clearly x̂_{a} := x_{a} (a ∈ A)) will be used.

Definition 2.1 (Multifacility Location Problem) The continuous minisum multifacility location problem with different gauges is the following optimization problem:

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

Ψ : (IR^{N})^{V} ⟶ IR
(x_{v})_{v∈V} ⟼ ∑_{e∈E} ω_{e}γ_{e}(x_{e}).  (4)

Particularly, there are no restrictions on the (x_{v})_{v∈V}.

Many assumptions about the structure of the graph G or the parameters could be made without reducing the class of problems. Some of them are found in Plastria [6] and in Fliege [1]. However, only three of them are necessary for the following discussion:

1. The weights are strictly positive, i. e. ω_{e} > 0 for all e ∈ E.

2. The graph G is simple: (f, f) ∉ E for all f ∈ F (the removal of such an edge does not change Ψ) and if (f, g) ∈ E then (g, f) ∉ E (otherwise, the new gauge ω_{fg}γ_{fg} + ω_{gf} \overline{γ_{gf}} with the new weight 1 could be used on the edge (f, g); the edge (g, f) could be removed).

3. The points x_{a} (a ∈ A) are mutually different. If x_{a} = x_{b} for two nodes a, b ∈ A with a ≠ b, one could reduce the problem by identifying a and b and redefining all involved edges.

The function Ψ is convex, nonnegative and not bounded from above. Therefore, the set of minima of Ψ is nonempty, convex and compact (Francis and Cabot [2], Fliege [1]).

3 Conditions for Coincidence

It is a well observed fact that often several new facilities tend to coincide at an optimal solution of the minisum multifacility location problem. Even if all gauges are as smooth as p-Norms with 1 < p < ∞, this leads to a nondifferentiability in a minimum of the original problem. But by testing sufficient conditions for coincidence, it is possible to collapse some coinciding facilities into one. This leads to a reduction of the problem’s dimension and of the degree of nondifferentiability [4, p. 437].

The following definition is an extension of the definition of attraction from Lefebvre, Michelot and Plastria [4].

Definition 3.1 Let W_{1}, W_{2} ⊆ F. The set W_{1} attracts the set W_{2}, if the following conditions are true:

• W_{1} ≠ ∅.

• ∅ ≠ W_{2} ⊆ V.

• W_{1} ∩ W_{2} = ∅.

• The set W_{1} contains at most one a ∈ A.

• With W := W_{1} ∪W_{2}, the following condition holds for all w ∈ W_{2} and all y ∈ IR^{N}:

∑_{e∈E(w,F \W)} ω_{e}γ_{e}(y) + ∑_{e∈E(F \W,w)} ω_{e}\overline{γ_{e}}(y) ≤ ∑_{e∈E(W_{1},w)} ω_{e}γ_{e}(y) + ∑_{e∈E(w,W_{1})} ω_{e}\overline{γ_{e}}(y). (5)

Now let W_{1} attract W_{2} and let at least one w ∈ W_{2} exists such that (5) is strict for all y ∈ IR^{N}, y ≠ 0. Then W_{2} is called strictly attracted by W_{1} and w is called a witness of strict attraction.

Remark 3.2 Let ∅ ≠ W_{1} ⊆ F, ∅ ≠ W_{2} ⊆ V, W_{1} ∩ W_{2} = ∅ and W := W_{1} ∪ W_{2}. The set W_{1} should contain at most one a ∈ A. If

E(W_{2}, F \ W) = ∅,

then W_{1} attracts the set W_{2}. Moreover, if at least one w ∈ W_{2} exists with E(w, W_{1}) ≠ ∅, then W_{2} is strictly attracted by W_{1} with witness w.

Proof: For all w ∈ W_{2} is E(w, F \ W_{2}) = ∅, therefore the left side of (5) is 0. If, in addition, at least one w ∈ W_{2} exists with E(w, W_{1}) ≠ ∅, the inequality (5) is strict for all y ≠ 0. □

Theorem 3.3 Let W_{1}, W_{2} ⊆ F, W := W_{1} ∪ W_{2} and let W_{1} attract the set W_{2}. Let a family (x_{v})_{v∈V} be given with x_{w} = x for all w ∈ W_{1} and define (x̂_{v})_{v∈V} by x̂_{w} := x for all w ∈ W and x̂_{v} := x_{v} for all v ∈ V \ W. Then it follows that

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

If W_{1} strictly attracts W_{2} and there exists a witness w ∈ W_{2} with x_{w} ≠ x, it follows that Ψ((x̂_{v})_{v∈V}) < Ψ((x_{v})_{v∈V}).

If (x_{v})_{v∈V} is a minimum of Ψ with x_{f} = x_{g} for all f, g ∈ W_{1}, then it follows for all (u, v) ∈ E(W_{2}, W_{2}) that x_{u} = x_{v}.

Proof: The difference Ψ((x̂_{v})_{v∈V}) − Ψ((x_{v})_{v∈V}) will be estimated. The following cases cover all e ∈ E:

1. e ∈ E(F \W, F \W) or e ∈ E(W_{1}, W_{1}):we have x̂_{e} = x_{e} and then γ_{e}(x̂_{e})−γ_{e}(x_{e}) = 0.

2. e ∈ E(W_{2}, W_{2}): then γ_{e}(x̂_{e}) − γ_{e}(x_{e}) = −γ_{e}(x_{e}).

3. e ∈ E(W_{1}, F \ W): here one has γ_{e}(x̂_{e}) − γ_{e}(x_{e}) = 0.

4. e ∈ E(W_{1}, W_{2}): we have γ_{e}(x̂_{e}) − γ_{e}(x_{e}) = −γ_{e}(x_{e}).

5. (a) e = (w, f) ∈ E(W_{2}, F \ W): here, x̂_{e} = x − x_{f} and x_{e} = x_{w} − x_{f}. The triangle inequality now shows that γ_{e}(x̂_{e}) ≤ γ_{e}(x − x_{w}) + γ_{e}(x_{w} − x_{f}) = γ_{e}(x − x_{w}) + γ_{e}(x_{e}). Consequently, one has γ_{e}(x̂_{e}) − γ_{e}(x_{e}) ≤ γ_{e}(x − x_{w}).

(b) e = (f, w) ∈ E(F \ W, W_{2}): in the same way, as before, one has γ_{e}(x̂_{e}) − γ_{e}(x_{e}) ≤ γ_{e}(x_{w} − x).

Now all edges in E are examined.

By the above considerations it follows that

Ψ((x̂_{v})_{v∈V}) − Ψ((x_{v})_{v∈V}) = ∑_{e∈E} ω_{e}(γ_{e}(x̂_{e}) − γ_{e}(x_{e}))

≤ ∑_{w∈W_{2}} ( ∑_{e∈E(w,F \W)} ω_{e}γ_{e}(x − x_{w}) + ∑_{e∈E(F \W,w)} ω_{e}γ_{e}(x_{w} − x)

− ∑_{e∈E(w,W_{1})} ω_{e}γ_{e}(x_{e}) − ∑_{e∈E(W_{1},w)} ω_{e}γ_{e}(x_{e}))

− ∑_{e∈E(W_{2},W_{2})} ω_{e}γ_{e}(x_{e})

≤ − ∑_{e∈E(W_{2},W_{2})} ω_{e}γ_{e}(x_{e})
≤ 0

because of (5). Therefore, the first statement follows. If (5) is strict for at least one w ∈ W_{2} with x_{w} ≠ x and all y ∈ IR^{N} \ {0}, the last but one inequatlity is also strict. The statement Ψ((x̂_{v})_{v∈V}) < Ψ((x_{v})_{v∈V}) follows.

Now let (x_{v})_{v∈V} be a minimum of Ψ. Then

0 ≤ Ψ((x̂_{v})_{v∈V}) − Ψ((x_{v})_{v∈V}) ≤ − ∑_{e∈E(W_{2},W_{2})} ω_{e}γ_{e}(x_{e}) ≤ 0

and then γ_{e}(x_{e}) = 0, i. e. x_{e} = 0 for all e ∈ E(W_{2}, W_{2}). □

Consider now the special case when all gauges γ_{e} are equal to one norm γ. Let (5) hold, let W_{1} = {g} and let E(g, w) ≠ ∅ hold for all w ∈ W_{2}. Then W_{2} is the leaf-set of an attraction tree (cf. [4]) of height 1 with root g. The suppressed edges are the edges in E(W_{2}, W_{2}). If W_{2} = {f}, then (5) simplifies to the attraction condition of [4].

The next example (due to Plastria [8]) uses only one norm instead of several different ones.

Example 3.4 Let A = {a, b, c, d}, V = {t, u, v, w},

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

All γ_{e} are equal to a norm γ. The weights are ω_{ua} = ω_{va} = ω_{wa} = ω_{ut} = ω_{wt} = ω_{vt} = 3 and ω_{ub} = ω_{vd} = ω_{wc} = 1. Taking W_{1} := {a} and W_{2} := V one gets strict attraction between W_{1} and W_{2}. Especially, every element of V except t is a witness of strict attraction. Therefore, it is x_{a} = x_{t} = x_{u} = x_{v} = x_{w} for all minima of the constructed minisum multifacility location problem.

It should be noted that in this example no attraction tree as defined in [4] exists. Therefore, none of Lefebvre, Michelot and Plastria’s results will yield any coincidences. The same holds for example 2.2 in [1]. This example is smaller than the one presented here, but uses mixed norms instead of a single one.

Since (5) is a functional inequality, it is not clear how to check these coincidence condition in a computer code. However, it is possible to derive sufficient conditions for (5), which only involve the given weights and certain comparison factors. In a computer code, these conditions can then be used to detect coincidences in location problems with mixed gauges.

Theorem 3.5 Let ∅ ≠ W_{1} ⊂ F, ∅ ≠ W_{2} ⊆ V and W := W_{1} ∪ W_{2}. Also, at most one a ∈ A should be in W_{1}. For all w ∈ W_{2} let γ_{w}^{(1)} and γ_{w}^{(2)} be two gauges and let α_{e,w}^{(i)}, β_{e,w}^{(i)} > 0 (i = 1, 2) be comparison factors with

α_{e,w}^{(i)}γ_{w}^{(i)} ≤ γ_{e} ≤ β_{e,w}^{(i)}γ_{w}^{(i)} (e ∈ E, i = 1, 2).

If

∑_{e∈E(w,F \W)} ω_{e}β_{e,w}^{(1)} ≤ ∑_{e∈E(W_{1},w)} ω_{e}α_{e,w}^{(1)}  (6)

and

∑_{e∈E(F \W,w)} ω_{e}β_{e,w}^{(2)} ≤ ∑_{e∈E(w,W_{1})} ω_{e}α_{e,w}^{(2)}  (7)

hold for all w ∈ W_{2}, then W_{2} is attracted by W_{1}.

If, additionally, (6) or (7) is strict for at least one w ∈ W_{2}, then W_{2} is strictly attracted by W_{1}.

Proof: For all e ∈ E one has

α_{e,w}^{(i)}\overline{γ_{w}^{(i)}} ≤ \overline{γ_{e}} ≤ β_{e,w}^{(i)}\overline{γ_{w}^{(i)}} (i = 1, 2).

Let w ∈ W_{2}. Then

∑_{e∈E(w,F \W)} ω_{e}γ_{e} + ∑_{e∈E(F \W,w)} ω_{e}\overline{γ_{e}}

≤ ∑_{e∈E(w,F \W)} ω_{e}β_{e,w}^{(1)}γ_{w}^{(1)} + ∑_{e∈E(F \W,w)} ω_{e}β_{e,w}^{(2)}\overline{γ_{w}^{(2)}}
= ( ∑_{e∈E(w,F \W)} ω_{e}β_{e,w}^{(1)}) γ_{w}^{(1)} + ( ∑_{e∈E(F \W,w)} ω_{e}β_{e,w}^{(2)}) \overline{γ_{w}^{(2)}}
≤ ( ∑_{e∈E(W_{1},w)} ω_{e}α_{e,w}^{(1)}) γ_{w}^{(1)} + ( ∑_{e∈E(w,W_{1})} ω_{e}α_{e,w}^{(2)}) \overline{γ_{w}^{(2)}}
= ∑_{e∈E(W_{1},w)} ω_{e}α_{e,w}^{(1)}γ_{w}^{(1)} + ∑_{e∈E(w,W_{1})} ω_{e}α_{e,w}^{(2)}\overline{γ_{w}^{(2)}}
≤ ∑_{e∈E(W_{1},w)} ω_{e}γ_{e} + ∑_{e∈E(w,W_{1})} ω_{e}\overline{γ_{e}}

and (5) follows. Also, (5) is strict for all y ∈ IR^{N} \ {0}, whenever (6) or (7) is strict. □ The next example, however, shows that (6) and (7) are not necessary for (5):

Example 3.6 This example is in dimension N = 2. Choose W_{2} = {w}, E(w, F \W) = E(w, F \ W) = {e_{1}, e_{2}}, E(w, W_{1}) = E(W_{1}, w) = {e_{3}, e_{4}}, and assume that (7) holds for all gauges γ^{(2)}. Let also ω_{e_{i}} := 1 (i = 1, 2, 3, 4) and

γ_{e_{1}}(x_{1}, x_{2}) := γ_{e_{3}}(x_{1}, x_{2}) := (1/2)|x_{1} | + (1/2)|x_{2} |
γ_{e_{2}}(x_{1}, x_{2}) := γ_{e_{4}}(x_{1}, x_{2}) := max{(1/3)|x_{1} |, |x_{2} |}.

Then (5) is true. Now let γ_{w}^{(1)} be an arbitrary gauge. If (6) would hold, one would get β_{e_{1},w}^{(1)} + β_{e_{2},w}^{(1)} ≤ α_{e_{3},w}^{(1)} + α_{e_{4},w}^{(1)}. With α_{e_{3},w}^{(1)} ≤ β_{e_{1},w}^{(1)} and α_{e_{4},w}^{(1)} ≤ β_{e_{2},w}^{(1)} it would follow that β_{e_{1},w}^{(1)} = α_{e_{3},w}^{(1)} and β_{e_{2},w}^{(1)} = α_{e_{4},w}^{(1)}. But one has α_{e_{3},w}^{(1)}γ^{(1)} ≤ γ_{e_{3}} = γ_{e_{1}} ≤ β_{e_{1},w}^{(1)}γ^{(1)} and α_{e_{4},w}^{(1)}γ^{(1)} ≤ γ_{e_{4}} = γ_{e_{2}} ≤ β_{e_{2},w}^{(1)}γ^{(1)}. Therefore, one would get α_{e_{3},w}^{(1)}γ^{(1)} = γ_{e_{3}} and α_{e_{4},w}^{(1)}γ^{(1)} = γ_{e_{4}}. It would follow that γ_{e_{3}} = cγ_{e_{4}} with c > 0, which leads to a contradiction.

Instead of (6) and (7), one could also use

∑_{e∈E(w,F \W)} ω_{e}β_{e,w}^{(1)} ≤ ∑_{e∈E(w,W_{1})} ω_{e}\overline{α}_{e,w}^{(1)}  (8)

and

∑_{e∈E(F \W,w)} ω_{e}β_{e,w}^{(2)} ≤ ∑_{e∈E(W_{1},w)} ω_{e}\overline{α}_{e,w}^{(2)}  (9)

(here we have \overline{α}_{e,w}^{(i)}γ_{w}^{(i)} ≤ \overline{γ_{e}}, (w ∈ W_{1}, e ∈ E, i = 1, 2)). These two conditions are also sufficient for (5). But the last example could be used to construct a counterexample to show that (5) is not sufficient for (8) and (9).

Now let γ̃_{w} = γ_{w}^{(1)} = γ_{w}^{(2)} for a w ∈ W_{2} and let \overline{α̃}_{e,w}, \overline{β̃}_{e,w} α̃_{e,w}, β̃_{e,w} > 0 be comparison factors with α̃_{e,w}γ̃_{w} ≤ γ_{e} ≤ β̃_{e,w}γ̃_{w} and \overline{α̃}_{e,w}γ̃_{w} ≤ \overline{γ_{e}} ≤ \overline{β̃}_{e,w}γ̃_{w} (e ∈ E(w, F \ W_{2})). Instead of (6) and (7), the following condition could be used:

∑_{e∈E(w,F \W)} ω_{e}β̃_{e,w} + ∑_{e∈E(F \W,w)} ω_{e}\overline{β̃}_{e,w} ≤ ∑_{e∈E(W_{1},w)} ω_{e}α̃_{e,w} + ∑_{e∈E(w,W_{1})} ω_{e}\overline{α̃}_{e,w}.  (10)

This condition also implies (5). But the existence of two gauges γ^{(1)} and γ^{(2)} with (6) and (7) is neither necessary nor sufficient for the existence of a gauge γ̃ with (10), as the following examples show.

Example 3.7 Let w ∈ W_{2}, E(w, F \W) = {e_{1}}, E(F \W, w) = {e_{2}}, E(W_{1}, w) = {e_{3}} and E(w, W_{1}) = {e_{4}}. The gauges γ_{e_{i}} and the weights ω_{e_{i}} (i = 1, 2, 3, 4) are chosen as in example 3.6. With γ^{(1)} = γ_{e_{1}} = γ_{e_{3}} and γ^{(2)} = γ_{e_{2}} = γ_{e_{4}}, (6) and (7) hold. Now let (10) hold for a gauge γ̃_{w}. Then β̃_{e_{1},w} + \overline{β̃}_{e_{2},w} ≤ α̃_{e_{3},w} + \overline{α̃}_{e_{4},w} would hold. But as in example 3.6, a contradiction would follow.

Example 3.8 Let w ∈ W_{2}, E(w, F \W) = {e_{1}}, E(F \W, w) = {e_{2}}, E(W_{1}, w) = {e_{3}} and E(w, W_{1}) = {e_{4}}. Let γ_{e_{1}} = γ_{e_{2}} = γ_{e_{3}} = γ_{e_{4}} =: γ be a norm, ω_{e_{1}} = ω_{e_{4}} = 2 and ω_{e_{2}} = ω_{e_{3}} = 1. With γ̃ = γ one has (10). Now let γ^{(1)} be an arbitrary gauge. Then (6) is equivalent to 2β_{e_{1},w}^{(1)} ≤ α_{e_{3},w}^{(1)}. But with γ_{e_{1}} = γ_{e_{3}} one has α_{e_{3},w}^{(1)} ≤ β_{e_{1},w}^{(1)}, so (6) cannot be true.

Likewise, (8) and (9) is neither necessary nor sufficient for (10).

Obviously, the new coincidence conditions could be used recursively, once at least one coincidence has been established. In this way, one gets theorems similar to the theorem 3 from Juel and Love [3] (this result could only be used if all gauges are equal to one norm). In multilocation problems with different gauges, one could use different comparison gauges and therefore different comparison values in each recursion step.

In the special case of the Fermat-Weber-problem (V = {v}) with one quasimetric as a distance function, Plastria [7] proves a majority theorem which plays the same role as the conditions (6)–(10) for the Fermat-Weber-problem. If a gauge γ is used to define a quasimetric, the conditions (6)–(10) collapse into the asymmetric majority theorem from [7], as long as γ is also used as a comparison gauge. But by using different comparison gauges or condition (5), one obtains greater flexibility in checking coincidences.

Still other new conditions could be constructed by using the idea of attraction trees on disjoint sets W_{1}, …, W_{n}.

Definition 3.9 (Set-Trees) Let W be a partition of F and let O ∈ W. A tree T_{W} = (F_{W}, E_{W}) with node set F_{W} := W \ {O} is called set-tree on F. The set O is called outer part of T_{W}.

Now let T_{W} be rooted with root R ∈ F_{W}. The tree T_{W} is called compatible with Ψ, if at most one a ∈ A is in R and all other sets W ∈ F_{W} are subsets of V, i. e. ⋃_{W ∈F_{W}}(W \ R) ⊆ V. For W ∈ F_{W}, W ≠ R denote with pre(W) the father of W, the first node on the path from W to the root R.

Definition 3.10 (Cleaned Up Graphs) Let W be a partition of F and let T_{W} = (F_{W}, E_{W}) be a set-tree on F with root R and outer part O, which is compatible with Ψ. The graph

G′(T_{W}) := (F, E′(T_{W}))

with

E′(T_{W}) := E(O, F) ∪ ⋃_{{W ∈F_{W} \atop W ≠R}} E(W, pre(W))

is called cleaned up graph. The set

Es^{′}(T_{W}) := E \ E′(T_{W})

is called set of suppressed edges.

Definition 3.11 (Attraction Set-Trees) Let W be a partition of F and let T_{W} = (F_{W}, E_{W}) be a set-tree on F with root R and outer part O, which is compatible with Ψ. The tree T_{W} is named attraction set-tree, if every W ∈ F_{W}, W ≠ R, is attracted by its father pre(W) relative to G′(T_{W}) (an attraction disregarding all suppressed edges).

Theorem 3.12 Let W be a partition of F and T_{W} = (F_{W}, E_{W}) be a set-tree on F with root R and outer part O, which is compatible with Ψ and which is an attraction set-tree. Let a family (x_{v})_{v∈V} be given with x_{r} = x for all r ∈ R and define (x̂_{v})_{v∈V} by x̂_{p} := x_{p} for all p ∈ O and x̂_{f} := x for all f ∈ F \ O. Then it follows that

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

If at least one W ∈ F_{W} is strictly attracted by its father pre(W) relative to G′(T_{W}) and at least one witness w ∈ W of this exists with x_{w} ≠ x, it follows that

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

Let additionally (x_{v})_{v∈V} be a minimum of Ψ. Then it is x_{f} = x_{g} for all (f, g) ∈ Es^{′}(T_{W}).

Proof: The proof runs the same way as the proof of the attraction theorem in [4] or [1]. Set E′ := E′(T_{W}), Es^{′} := Es^{′}(T_{W}) and G′ := G′(T_{W}). For (y_{v})_{v∈V} ∈ (IR^{N})^{V} set

Ψ′((y_{v})_{v∈V}) := ∑_{e∈E′} ω_{e}γ_{e}(y_{e}).

By repeated application of theorem 3.3 on Ψ′ and the nodes W ≠ R and pre(W) of T_{W}, one obtains Ψ′((x̂_{v})_{v∈V}) ≤ Ψ′((x_{v})_{v∈V}). This inequality is strict, if at least one W ∈ F_{W} is strictly attracted by its father pre(W) relative to G′ and at least one witness w ∈ W of this exists with x_{w} ≠ x. Moreover, it is x̂_{e} = 0 for all suppressed edges e ∈ Es^{′}. Therefore,

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

and the first and second part of the theorem is proven. Now let additionally (x_{v})_{v∈V} be a minimum of Ψ. It follows that Ψ((x̂_{v})_{v∈V}) = Ψ((x_{v})_{v∈V}). Thus

Ψ((x_{v})_{v∈V}) = Ψ′((x_{v})_{v∈V}) + ∑_{e∈E′_{s}} ω_{e}γ_{e}(x_{e}) ≥ Ψ′((x_{v})_{v∈V})
≥ Ψ′((x̂_{v})_{v∈V}) = Ψ((x̂_{v})_{v∈V}) = Ψ((x_{v})_{v∈V}).

Therefore, ∑_{e∈E′_{s}} ω_{e}γ_{e}(x_{e}) = 0 and the last part follows. □

References

[1] Jörg Fliege. Nichtdiskrete Multilokationsprobleme: Koinzidenzbedingungen und effiziente Punkte. Diplomarbeit, Universität Dortmund, FB Mathematik, Universität Dortmund, 44221 Dortmund, February 1993.

[2] R. L. Francis and A. V. Cabot. Properties of a Multifacility Location Problem Involving Euclidean Distances. Naval Research Logistics Quarterly, 19:335–353, 1972.

[3] Henrik Juel and Robert F. Love. Sufficient conditions for Optimal Facility Locations to Coincide. Transportation Science, 14(2):125–129, May 1980.

[4] O[dile] Lefebvre, C[hristian] Michelot, and F[rank] Plastria. Sufficient conditions for coincidence in minisum multifacility location problems with a general metric. Operation Research, 39(3):437–442, May–June 1991.

[5] Hermann Minkowski. Gesammelte Abhandlungen, volume 2. Chelsea Publishing Company, New York, 1967. Reprint.

[6] F[rank] Plastria. When facilities coincide: exact optimality conditions in multifacility location. Report BEIF/6 (Version 2), Centre for Industrial Location and Development, Centre for Management Informatics, Vrije Universiteit Brussel, March 1991.

[7] Frank Plastria. 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, Puerto de La Cruz (Tenerife), Spain, April 1992.

[8] Frank Plastria. Private communication, May 7, 1993.