SPECIAL CASES AND EFFICIENT ALGORITHMS FOR 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. It is shown that a certain chararacterization of points at which nondifferentiabilities occur is checkable in polynomial time. Therefore, it is possible to check efficiently 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 simultaneously. Numerical results confirm that by using this strategy improved solutions can be found in less computation time.

Key words. facility location, coincidence conditions, dimension reduction, nondifferentiability detection, polynomial time algorithms, numerical comparison

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

In this paper we extend the results presented in [22] by deriving a polynomial time coincidence checking algorithm for multifacility location problems. It is shown that this algorithm detects more coincidences than the conditions proposed in the literature so far. Numerical results are presented for problems with up to 40.000 variables.

1. Preliminaries. We recall in short the notation and the results obtained in [22]. For an arbitrary set Λ an 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. For a fixed set X ≠ ∅ we define the set Δ by Δ := {(x, x) ∈ X × X | x ∈ X}, the diagonal of X × X.

1.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. 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). 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}

A semi-definite function d : X × X ⟶ IR which is either convex or concave is called distance cost function on X. A nonnegative convex distance cost function d is also called a weak metric [37, 39, 40, 36, 21].

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) \ Δ.

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

fliege@math.uni-dortmund.de

1.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}),

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.

1.2.1. Flows. Let G = (F, E) be a directed simple graph. Let there be given a nonempty source set Q ⊂ F, Q ≠ F, a nonempty sink set S ⊂ F, S ≠ F with Q ∩ S = ∅, and for each edge e ∈ E a capacity interval I_{e} = [a_{e}, b_{e}] ⊂ IR. Then, a family (φ_{e})_{e∈E} ∈ IR^{E} of real numbers φ_{e} ∈ IR (e ∈ E) is called a (Q, S)-flow, if

∑_{e∈E(Q,F)} φ_{e} − ∑_{e∈E(F,Q)} φ_{e} = ∑_{e∈E(F,S)} φ_{e} − ∑_{e∈E(S,F)} φ_{e},

∑_{e∈E(f,F)} φ_{e} = ∑_{e∈E(F,f)} φ_{e}

for all f ∈ F \ (Q ∪ S) and

φ_{e} ∈ I_{e}

holds for all e ∈ E. A (Q, S)-flow (φ_{e})_{e∈E} ∈ IR^{E} saturates an edge e ∈ E with interval of capacity I_{e} = [a_{e}, b_{e}], if φ_{e} = b_{e} holds. If the corresponding capacity intervals for the edges of G, a set of sources and a set of sinks are given, the graph G is also called a transportation network. In case the edges in E are weighted, i. e. for all e ∈ E there exists a weight ω_{e} ∈ IR, a family (φ_{e})_{e∈E} ∈ IR^{E} of real numbers φ_{e} ∈ IR (e ∈ E) is called a weighted (Q, S)-flow, if

∑_{e∈E(Q,F)} ω_{e}φ_{e} − ∑_{e∈E(F,Q)} ω_{e}φ_{e} = ∑_{e∈E(F,S)} ω_{e}φ_{e} − ∑_{e∈E(S,F)} ω_{e}φ_{e},

∑_{e∈E(f,F)} ω_{e}φ_{e} = ∑_{e∈E(F,f)} ω_{e}φ_{e}

for all f ∈ F \ (Q ∪ S) and

φ_{e} ∈ I_{e}

for all e ∈ E holds.

1.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. 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. A location x_{v} ∈ X for a node v ∈ V is called new location for 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.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} (1.1)

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

In what follows, we may assume without loss of generality that all functions d_{e} (e ∈ E) are unequal to the constant function 0. 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 as soon as it simplifies the notation.

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

1.4. Compatible Partitions. Let E_{≤} ⊆ E and E_{≥} ⊆ E be two given subsets of E with E_{≤} ∩ E_{≥} = ∅. Then, the notation of § 1.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 § 3. Here, it suffices to say that it will be meaningful to define E_{≥} as the set of all edges e ∈ E such that d_{e} is concave.

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 |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. 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 assume without loss of generality that E(U_{i}, F \ U_{i}) = E(U_{i}, F \ U_{i}) (0 ≤ i ≤ n − 1) holds.

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

1.5. A Coincidence Condition. 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 following theorem has been proved in [22]. It contains a new coincidence condition useful for reducing the dimension of a problem and the number of nondifferentiable terms in the objective function.

Theorem 1.2. 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

(1.2a) ∑_{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

(1.2b)  ∑_{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,

(1.2c) ∑_{{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},

(1.2d) ∑_{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

(1.2e)  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 (1.2a) 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.

2. Multiplicative Distance Cost Functions. The coincidence condition from the last section will now be applied to several special cases of the minisum multifacility location problem. For these special cases, we will simplify Theorem 1.2 in a considerable way. In § 3.1 and 4.1, we will compare the coincidence conditions derived here with other conditions from the literature. Using Example 3.2 from § 3, it will be shown that all the older conditions are not as flexible as the new ones. Moreover, it will become clear that all the older coincidence criteria can be derived as special cases from the ones presented here.

If several different distance cost functions d_{e} are used on the edges e ∈ E of the graph G, it will usually not be very easy to check the coincidence condition (1.2), even if the partition W of F and a set E_{s} ⊆ E are given. But consider the case of a fixed symmetric distance cost function d and given real numbers ω_{e} ∈ IR (e ∈ E(K ∪ U, U)) such that

ω_{e}d ≤ d_{e} (e ∈ E(K ∪ U, U))

holds. If we replace on each edge e ∈ E(K ∪ U, U) the function d_{e} by ω_{e}d, we obtain a new objective function Ψ̃ : X^{V} ⟶ IR with Ψ̃((y_{v})_{v∈V}) ≤ Ψ((y_{v})_{v∈V}) for all (y_{v})_{v∈V} ∈ X^{V} and Ψ̃((x̂_{v})_{v∈V}) = Ψ((x̂_{v})_{v∈V}). Suppose that we can proof one of the inequalities Ψ̃((x̂_{v})_{v∈V}) ≤ Ψ̃((x_{v})_{v∈V}) or Ψ̃((x̂_{v})_{v∈V}) < Ψ̃((x_{v})_{v∈V}). Then we can immediately conclude that Ψ((x̂_{v})_{v∈V}) ≤ Ψ((x_{v})_{v∈V}) or Ψ((x̂_{v})_{v∈V}) < Ψ((x_{v})_{v∈V}) holds. Of course, we can also replace the functions d_{e} by simpler ones on the edges e ∈ E(U, S). It may often be the case that the fulfillment of a coincidence condition with respect to the new problem is sufficient for a coincidence with respect to the original problem. For example, if all d_{e} (e ∈ E(U, S)) are convex and d is a weak metric, we may replace each d_{e} by ω_{e}d, where the weights ω_{e} are chosen such that d_{e} ≤ ω_{e}d holds (it is obvious that a coincidence is now ”not as easy as before”). The functions d_{s}^{f,v} (s ∈ S, v ∈ U, f ∈ F′_{≤}(pre(v), v)) needed in (1.2a) and (1.2b) may then be constructed by using information collected while checking coincidence conditions for the function Ψ̃.

In what follows, let d be a symmetric weak metric and d_{e} = ω_{e}d for all e ∈ E with certain ω_{e} ∈ IR. As it has been already remarked on page 3, we may assume without loss of generality d ≠ 0 and ω_{e} ≠ 0 for all e ∈ E. On the other hand, we may add any edge e ∉ E to the graph simply by setting ω_{e} = 0.

Let there be given two subsets E_{≤}, E_{≥} ⊆ E as on page 4 and a set E_{s} as in Theorem 1.2. Our goal is to derive simple, sufficient conditions for the system (1.2).

A natural approach uses the functions

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. For a given partition

W = {K, W_{1}, …, W_{n−1}, S}

compatible with Ψ, we are now in search for weights

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

such that the following conditions hold:

(2.1a) ∑_{s∈S} |ω_{s}^{f,v}| + ∑_{{w∈W (v)\\{v\} \atop g∈F{′ \atop ≤}(pre(w),w)}} (|ω_{v,w}^{f,g}| + |ω_{w,v}^{g,f}|) + ∑_{h∈pre(v)\F′_{≤}(pre(v),v)} |ω_{h}^{f,v}| ≤ ω^{f,v}

for all v ∈ U = F \ (K ∪ S) and f ∈ F′_{≤}(pre(v), v),

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

for all v ∈ U and s ∈ S,

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

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

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

+ ∑_{t∈F{′ \atop ≤}(v,succ(v)) u∈F{′ \atop ≤}(h,succ(v)) W (t)=W (u),t≠u} (ω_{u,t}^{h,v} + ω_{t,u}^{v,h})

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

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

+ ∑_{t∈F{′ \atop ≤}(f,succ(v)) u∈F{′ \atop ≤}(v,succ(v)) W (t)=W (u),t≠u} (ω_{t,u}^{f,v} + ω_{u,t}^{v,f})

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

Without loss of generality, we assume that the sets W_{i} (i = 1, …, n − 1) are singletons. That we do not lose any information by this assumption can be seen in the following way: let W_{i} ≠ K, W_{i} ≠ S be the ”deepest” set with more than one element, i := max{j | 1 ≤ j ≤ n − 1, |W_{j}| ≥ 2}. For an arbitrary w ∈ W_{i}, we define the set W̃ := {w} and place this set W̃ between W_{i} and W_{i+1} into the partition W. Simultaneously, we remove w from W_{i}. We can now show by some arduous calculations that the conditions (2.1) are fulfilled for the new partition W̃ just constructed if and only if they are fulfilled for the original partition W [19, Chapter 3]. Using this idea inductively on all sets W_{i} ∉ {K, S}, we see that we have to consider the case of one-elemental sets W_{i} only. But then, condition (2.1c) is trivially true. The conditions simplified in this way are

∑_{s∈S} |ω_{s}^{f,v}| + ∑_{h∈pre(v)\F′_{≤}(pre(v),v)} |ω_{h}^{f,v}| ≤ ω^{f,v} (2.2a)

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

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

for all v ∈ U and s ∈ S,

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

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

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

for all v ∈ U and f ∈ F′_{≤}(pre(v), v). Moreover, the derivation of Theorem 1.2 [19, 22] shows that we may replace (2.2d) by

(2.3)  ω^{f,v} ≤ ω_{fv} + ∑_{u∈F{′ \atop ≤}(v,succ(v)) withf∉F{′ \atop ≤}(pre(u),u)} ω_{f}^{v,u} + ∑_{u∈F{′ \atop ≤}(f,succ(v)) withv∉F{′ \atop ≤}(pre(u),u)} ω_{v}^{f,u}

(cp. [19, Bemerkung 2.2.6]). This will be used later on in § 4.1.

Problems with arbitrary convex and concave functions cannot be treated in the same way, since sums of convex and concave functions need to be neither convex nor concave.

3. Nonnegative Weights. Because of (2.1a) we have necessarily ω^{f,v} ≥ 0. Since the sets W_{i} (1 ≤ i ≤ n − 1) are singletons by now, we do not need to find weights ω_{v,w}^{f,g} (v ∈ U, w ∈ W (v) \ {w}, f ∈ F′_{≤}(pre(v), v), g ∈ F′_{≤}(pre(w), w)). By using the approach

E_{≥} := ∅

and ω_{h}^{f,v} := 0 (v ∈ U, f ∈ F′_{≤}(pre(v), v), h ∈ pre(v)\F′_{≤}(pre(v), v)), we see that (2.1d) resp. (2.2c) holds, too.

For the rest of this section we are only concerned with the case ω_{e} ≥ 0 for all e ∉ E(S, S). The corresponding functions d_{e} are convex, and we will use the additional constraints

ω_{s}^{f,v} ≥ 0

(v ∈ U, f ∈ F′_{≤}(pre(v), v), s ∈ S). With this, the system (2.2) simplifies to

∑_{s∈S} ω_{s}^{f,v} ≤ ω^{f,v} (3.1a)

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

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

for all v ∈ U and s ∈ S, and

ω^{f,v} = ω_{fv} (3.1c)

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

Obviously, condition (3.1c) can be dropped after replacing the right-hand side in (3.1a) by ω_{fv}. Thus, the coincidence condition can be written as

∑_{s∈S} ω_{s}^{f,v} ≤ ω_{fv} (3.2a)

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

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

for all v ∈ U and s ∈ S. Note that we would have arrived at exactly these two relations if we would have replaced (2.2d) by (2.3).

As one may suspect, we lose some of the generality that we had beforehand due to the additional constraints ω_{s}^{f,v} ≥ 0, at least if the partition W is fixed:

Example 3.1. Let a ∈ S, u ∈ W_{n−1}, w ∈ W_{n−2}, v ∈ W_{n−3}, f, g ∈ U_{n−4}, ω_{ua} = ω_{vu} = ω_{fv} = 1, and ω_{va} = ω_{wu} = ω_{gw} = 2. All other weights in the subgraph induced by a, f, g, u, v, and w are 0. Furthermore, let F′_{≤}(pre(u), u) = {v, w}. With ω_{a}^{w,u} := 2 and ω_{a}^{v,u} := −1 we see that we have attraction from u to v and to w. In the next step we have ω_{a}^{g,w} = 2 and therefore attraction from w to g and in the step afterwards ω_{a}^{f,v} = 1 and therefore attraction from v to f. But with the additional constraints ω_{a}^{v,u}, ω_{a}^{w,u} ≥ 0 it is not possible to choose ω_{a}^{f,v} in such a way that (3.2) holds. However, after changing the partition such that v ∈ W_{n−1}, u ∈ W_{n−2}, and w ∈ W_{n−3} we can work with nonnegative weights and get the desired result. We conjecture that this strategy of changing the partition leads to the desired result rather often.

The next example has already been used in [22] and will be used later on again to show that the coincidence conditions derived in other works do not find all coincidences which can be detected by the conditions derived here.

Example 3.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 n = 4, K = {a}, S = {b, c, d}, W_{1} = {u}, W_{2} = {v}, W_{3} = {w}, and E_{s} = ∅. Because of the symmetry of d we may turn around edges as we wish. Since K contains only one element, we have trivially x_{k} = x for all k ∈ K and all families (x_{v})_{v∈V}. Because (3.2b) has to hold for the weights ω_{d}^{u,w} and ω_{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 (3.2a) has to hold, we have to choose them in such a way that

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

and

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

holds. (Here, we may also consider (3.2a) for f := a. Because of ω_{aw} = 0 we have then to choose ω_{d}^{a,w} := 0.) As an example, we choose ω_{d}^{u,w} = 4 and ω_{d}^{v,w} = 4. With this, (3.2) holds with respect to w ∈ U and the set F′_{≤}(pre(w), w) = {u, v}. Our choice leads subsequently to ω_{d}^{a,u} = 4 and ω_{d}^{a,v} = 4, and (3.2) holds for all nodes necessary. It follows that

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

holds 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}.

The same result can be shown to hold if the edge (u, v) with the weight ω_{uv} = −1/2 is added to the graph. In this case we have to use E_{≥} := {(u, v)}, ω_{u}^{a,v} = −1/2, and ω^{a,u} = 13/2.

Consider now the case in which we add not only the edge (u, v) with ω_{uv} = −1/2 to the graph, 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 (2.2c), 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 (2.2d). 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 together with the final result.

3.1. Former Results: Attraction Trees and Attraction Set Trees. The most general coincidence conditions for minisum multifacility location problems with mixed weak metrics and nonnegative weights known so far can be found in [18]. There, the concept of attraction set trees was introduced. We consider this concept here for the special case d_{e} = ω_{e}d, d a symmetric weak metric. Let U = {R, U_{1}, …, U_{m}, O} be a partition of F with |R ∩ A| ≤ 1 and ⋃_{i=1}^{m} U_{i} ⊆ V and let T_{U} be a tree with node set {R, U_{1}, …, U_{m}}, root R, and edge set Γ. We denote the father node of a node U of T_{U} by father(U). Such a tree is called attraction set tree, if for each node U of the tree, U ≠ R, the sum of weights on edges leading to the father of U is greater than or equal to the the sum of weights on edges leading to children of U or to nodes in O:

∑_{e∈E(father(U),U)} ω_{e} ≥ ∑_{(U,W)∈Γ} ∑_{e∈E(U,W)} ω_{e} + ∑_{(W,U)∈Γ} ∑_{e∈E(W,U)} ω_{e} + ∑_{e∈E(U,O)} ω_{e}.

We have a coincidence result similar to Theorem 1.2, i. e. if T_{U} is an attraction set tree, then Ψ((x̂_{v})_{v∈V}) ≤ Ψ((x_{v})_{v∈V}) holds, where (x̂_{v})_{v∈V} is obtained from (x_{v})_{v∈V} by identifying the nodes in U_{i}, i = 1, …, m, with the ones in R (see [18]). In [18] it has also been shown that the attraction trees introduced by Lefebvre, Michelot, and Plastria [28, 29] are special cases of attraction set trees, since each coincidence detected by an attraction tree is also detected by some attraction set tree, but not every coincidence detected by an attraction set tree can be detected by an attraction tree.

Consider Example 3.2 without the negative weighted edges. If one tries to construct an attraction tree or an attraction set tree, it is immediately clear that none of the nodes b, c, or d may serve as the root node. Likewise, there exists no attraction (set) tree with root u, v, or w. Each attraction (set) tree with root a which attracts u to a has to suppress the edge (u, w). This means that the edge (v, w) and therefore the edge (v, a), too, has to be contained in the tree. But then we do not have attraction between a and v. Each attraction tree with root a that suppresses the edge (u, a) has to attract u to w. Therefore, the edge (u, w) has to be in the tree. But then w has to be attracted to v. Because of ω_{vw} = 6 and ω_{wd} = 8 we have a contradiction. As a consequence, there is no attraction tree and no attraction set tree in Example 3.2.

We will now show that the existence of an attraction set tree implies the existence of a partition compatible with Ψ and corresponding weights feasible to the system (3.2).

Let U = {R, U_{1}, …, U_{m}, O} be a partition of F and T_{U} be an attraction set tree as above. Let n − 1 be the height of T_{U}. (The root R has height 0, each son of the root has height 1, etc.) We have to construct a partition W = {K, W_{1}, …, W_{n−1}, S}. To this end, define W_{i} (0 ≤ i ≤ n − 1) as the set of all nodes w ∈ ⋃_{j=1}^{m} U_{j} which lie in those sets U_{j} that have height i in the tree T_{U}. Furthermore, set K := R and S := O. As usual, we assume without loss of generality E(W_{i}, W_{j}) = E(W_{i}, W_{j}) for i < j. The set E_{s} is defined as the set of all edges suppressed in T_{U}. For i = n − 1, …, 1 and s ∈ S we will define the weights ω_{s}^{f,v} (v ∈ W_{i}, f ∈ pre(v)) inductively as follows.

1. i = n − 1: Because of the attraction in T_{U} we have for all v ∈ W_{n−1} that

∑_{s∈S} ω_{vs} ≤ ∑_{e∈E′(W_{n−2},v)} ω_{e}. (3.3)

We define for each v ∈ W_{n−1} a transportation problem as follows: the nodes s ∈ S are the producers with capacity ω_{vs}, the edges e ∈ E′(W_{n−2}, v) are the consumers with demand ω_{e}. If we do not have equality in (3.3), we introduce, as usual in such a situation, a fictitious producer ŝ with capacity

ω̂ := ∑_{e∈E′(W_{n−2},v)} ω_{e} − ∑_{s∈S} ω_{vs} > 0.

For an arbitrary cost matrix we have a nonempty set of feasible points for the corresponding transportation problem. Let us fix an arbitrary feasible point and let ω_{s}^{f,v} be the demand of (f, v) served from s at this point. Because all demands are satisfied, we have (3.2a). Since succ(v) = ∅ and all capacities are completely used we have (3.2b).

2. i ⟶ i − 1, i ≥ 2: By the induction hypothesis we have constructed weights ω_{s}^{f,v} (v ∈ ⋃_{j=i}^{n−1} W_{j}, f ∈ F′_{≤}(pre(v), v), s ∈ S), for which (3.2) holds. Let v ∈ W_{i−1}. Because of the attraction condition and the definition of suppressed edges in T_{U} we have

∑_{e∈E′(v,S)} ω_{e} + ∑_{e∈E′(v,W_{i})} ω_{e} ≤ ∑_{e∈E′(W_{i−2},v)} ω_{e}.

EFFICIENT ALGORITHMS FOR MULTITHREADED DIMENSION REDUCTION 11

For each u ∈ F′(v, W_{i}) there exists weights ω_{s}^{v,u} such that

∑_{s∈S} ω_{s}^{v,u} ≤ ω_{vu}

holds. This can be deduced from (3.2a) and the induction hypothesis. Therefore,

∑_{s∈S} (ω_{vs} + ∑_{u∈F′_{≤}(v,W_{i})} ω_{s}^{v,u}) ≤ ∑_{e∈E′(W_{i−2},v)} ω_{e}

follows. Analogously to the start of the induction we can construct weights ω_{s}^{f,v} (v ∈ W_{i−1}, f ∈ F′_{≤}(pre(v), v) = F′(W_{i−2}, v), s ∈ S) such that

∑_{s∈S} ω_{s}^{f,v} ≤ ω_{fv}

holds for all v ∈ W_{i−1}, f ∈ F′_{≤}(W_{i−2}, v), and such that

∑_{f∈F′_{≤}(W_{i−2},v)} ω_{s}^{f,v} = ω_{vs} + ∑_{u∈F′_{≤}(v,W_{i})} ω_{s}^{v,u}

holds for all v ∈ W_{i−1}, s ∈ S. This completes the proof.

A discussion about other, not as general criteria (like the ones in [30, 11]) can be found in [19].

3.2. Flows: An Efficient Checking Algorithm. If W and E′ are given, the determination of weights which fulfill the system (2.1) is a simple feasibility problem in linear programming. Especially, a Phase I of the simplex method will be sufficient to check for the existence of these weights. Moreover, specially geared interior-point algorithms [42, 41] will lead to methods with polynomial run-time. However, up to now it is not clear how the combinatorial component of choosing the correct partition once the kernel K and the shell S are specified can be incorporated into the problem. This question will be answered in this subsection. At first, we will only consider problems with nonnegative weights. The results derived here will be generalized to the case of arbitrary weights later on (cp. § 4).

We will make use of our general assumption ω_{e} ≥ 0 for all e ∈ E(F \ (K ∪ S), F). Let there be given a partition W = {K, W_{1}, …, W_{n−1}, S} compatible with Ψ with kernel K, shell S, and a set E_{s} ⊇ ⋃_{i=0}^{n−1} E(W_{i}, W_{i}). As usual, we set E′ = E \ E_{s}. We define a transportation network T (W, E_{s}) = (F, Ê(W, E_{s})) as follows: T (W, E_{s}) has the set of sources K, the set of sinks S and with U := F \ (K ∪ S) the set of edges

Ê(W, E_{s}) := E′(K, U) ∪ E′(U, U) ∪ (U × S).

The interval of capacity of an edge e ∈ Ê(W, E_{s}) is [0, ω_{e}] for e ∈ E′ and {0} else. For a fixed partition W and fixed set E_{s} we abbreviate Ê := Ê(W, E_{s}).

Theorem 3.1. There exist weights ω_{s}^{f,v} ≥ 0 (v ∈ U, f ∈ F′_{≤}(pre(v), v), s ∈ S) which fulfill (3.2) if and only if there exists a (K, S)-flow (φ_{e})_{e∈Ê} on T (W, E_{s}) saturating all edges in U × S.

Proof. First, let there be given weights ω_{s}^{f,v} ≥ 0 (s ∈ S, v ∈ U, f ∈ F′_{≤}(pre(v), v)) such that (3.2) holds. For e = (k, v) ∈ E′(K, U) set

φ_{e} := ∑_{s∈S} ω_{s}^{k,v}

and, analogously,

φ_{e} := ∑_{s∈S} ω_{s}^{f,g}

for all e = (f, g) ∈ E′(U, U). For e = (v, s) ∈ U × S define φ_{e} := ω_{e} if e ∈ E′ and φ_{e} := 0 else. It is clear that (φ_{e})_{e∈Ê} saturates all edges in U × S. Let v ∈ U. Then it follows that Ê(F, v) = E′(pre(v), v) and Ê(v, F) = E′(v, succ(v)) ∪ ({v} × S). With (3.2b), we see that (φ_{e})_{e∈Ê} is conservative. Because of (3.2a) it is clear that each edge-flow φ_{e} is feasible.

Second, let there be given a conservative, feasible (K, S)-flow (φ_{e})_{e∈Ê} which saturates all edges in U×S (here, the set E_{s} is fixed). Since we have E_{s} ⊇ ⋃_{i=0}^{n−1} E(W_{i}, W_{i}), the edge set Ê contains no cycles. For (f, g) ∈ E′(U ∪ K, U) define the weight ω_{s}^{f,g} as the part of the total flow that flows via (f, g) to s ∈ S. The feasibility of the flow implies (3.2a). The conservativeness implies (3.2b). The nonnegativity is trivial.

Remark 3.2. Using the Theorem of Gale (cp., e. g., Berge and Ghuila-Houri [6, p. 192]) we see: there exist nonnegative weights which fulfill the conditions (3.2) if and only if for all subsets Ũ ⊆ U we have that

∑_{e∈E′(F \S,Ũ)} ω_{e} ≥ ∑_{e∈E′(Ũ,S)} ω_{e}

holds.

For the maximal flow problem there exist efficient algorithms (cp., e. g., [1] for an overview). Moreover, we can test in time O(|Ê|) = O(|E|) if a given (K, S)-flow saturates the sink edges. The question remains if there exists an efficient algorithm to compute a partition W = {K, W_{1}, …, W_{n−1}, S} compatible with Ψ and a flow satisfying the conditions above if only K and S are given. We will see that such an efficient algorithm exists.

Let K, S ⊆ F be fixed with |K ∩ A| ≤ 1, K ∩ S = ∅ and U := F \ (K ∪ S) ⊆ V. Without loss of generality, let E(K, U) = E(K, U) and E(U, S) = E(U, S). We define a transportation network T_{0} = (F, E_{0}) as follows: T_{0} shall have the node set F, the edge set

E_{0} := E(K, U) ∪ E(U, U) ∪ E(U, S),

the set of sources K, and the set of sinks S. The edges e ∈ E_{0} shall have the intervals of capacity [0, ω_{e}] if e ∈ E(K, U) ∪ E(U, S) and [−ω_{e}, ω_{e}] if e ∈ E(U, U).

Let (φ_{e})_{e∈E_{0}} be a feasible (K, S)-flow on T_{0}. First of all, we will ”turn around” all edges e = (f, g) ∈ E(U, U) with φ_{e} < 0: in the set E_{0}, the edge e is replaced by \overline{e} = (g, f) and we define φ\overline{e} := −φ_{e}. By doing this, the flow (φ_{e})_{e∈E_{0}} remains a conservative, feasible (K, S)-flow. But now we have φ_{e} ≥ 0 for all e ∈ E_{0}. Let Z ⊆ E(U, U) be a directed cycle with φ_{e} > 0 for all e ∈ Z. (i. e. it is Z = {(f_{1}, g_{1}), …, (f_{m}, g_{m})} with f_{j} = g_{j−1} (j = 2, …, m) and g_{m} = f_{1}.) We can ”lower” the flow (φ_{e})_{e∈E_{0}} on Z by δ_{Z} := min_{e∈Z} φ_{e} > 0 without destroying conservation or feasibility. Possible saturation properties on E(U, S) are not disturbed. After treating all cycles Z with δ_{Z} > 0 in this way (there is only a finite number of them), we define

E′ := {e ∈ E(U, U) | φ_{e} > 0}

and E_{s} := E(U, U) \ E′. The set E′ is the edge set of a directed graph with node set U which has no cycles. This means that we may topologically sort the node set U with respect to the partial ordering

f ≤ g :⟺ {it is f = g or there exists in E′ a directed path from f to g.

Let f_{1}, …, f_{|U|} be such a topological ordering of U, such that f_{i} ≤ f_{j} implies i ≤ j. Then, define

W_{i} := {f_{i}}

(i = 1, …, |U|).

We have just shown that for each (K, S)-flow on T_{0} saturating all edges in E(U, S) we can construct a partition W := {K, {f_{1}}, …, {f_{|U|}}, S} and a (K, S)-flow on the transportation network T_{0} that saturates all edges in E(U, S). This (K, S)-flow in turn induces a set E′ and a set E_{s} = E(U, U) \ E′ such that there exists a (K, S)-flow on T (W, E_{s}) saturating all edges in U × S.

On the other hand, for a given partition W and a given set E_{s} ⊆ E(U, U), it is easy to see that each (K, S)-flow on T (W, E_{s}) which saturates all edges in E(U, S) induces a (K, S)-flow on T_{0} saturating all edges in E(U, S).

To check the saturation of the edges, there is no need to modify the flow or sort the nodes topologically. The existence of the saturating flow is already ensured by the construction described above.

The derivation above shows that we have the following theorem.

Theorem 3.3. Let K and S be given with |K ∩ A| ≤ 1, K ∩ S = ∅ and U := F \ (K ∪ S) ⊆ V. Then, there exists a partition of U and corresponding nonnegative weights which fulfill system (3.2) if and only if there exists a flow on the transportation network T_{0} saturating all the edges in E(U, S).

Theorem 3.4. Let K and S be given with |K ∩ A| ≤ 1, K ∩ S = ∅ and U := F \ (K ∪ S) ⊆ V. Then, we can check in polynomial time if there exists a partition of U and corresponding nonnegative weights which fulfill (3.2).

Proof. For K and S given, we can rebuild the transportation network in polynomial time to an equivalent network containing exactly one sink and one source. A more detailed description of the process depends on the data structure in use and the representation of the graph G. We can now compute in polynomial time a maximal (K, S)-flow on T_{0}. For example, this can be done in time O(|U|^{2}\sqrt{|E(U, F)|}) [1]. If a maximal (K, S)-flow does not saturate the sink edges, there does not exist a feasible flow which saturates the sink edges. If, as it is usually done so in flow problems, all nodes in S are collapsed to one node in time O(|E(S, F)|) and all nodes in K are collapsed to one node in time O(|E(K, F)|) and a backflow edge is added, the saturation test can be performed in constant time. Otherwise, we need O(|E(U, S)|) steps for it.

Note that the checking algorithm outlined above is constructive in the sense that the nonnegative weights and the partition of U are constructed, if they exist.

In a practical setting, we will only be given a set Ũ ⊂ F such that |Ũ ∩ A| ≤ 1 holds, and this set Ũ will be only a candidate for a coincidence. A set K has still to be constructed. If Ũ ∩ A = {a} ≠ ∅ we have to check only the case K = {a}, U = Ũ \ K. Otherwise, we will use as K successively the one-elemental subsets of Ũ. Therefore, our checking algorithms will usually have another factor of |Ũ| in their run times. More details about an actual implementation can be found in [19] and in § 5.

Remark 3.5. The derivation above shows that the set E_{s} used in Theorem 1.2 can be defined as E_{s} := {e ∈ E(K ∪ U, K ∪ U) | φ_{e} = 0, ω_{e} > 0}, where (φ_{e})_{e∈E_{0}} is a constructed maximal flow. Then, the results derived for this set hold. Moreover, (3.2a) and thus (2.1a) as well as (1.2a) are strict for (f, v), if we have |φ_{fv}| < ω_{fv} for the constructed flow. In this way, we can distinguish between necessary coincidences and coincidences which do not occur necessarily in a solution of the facility location problem.

If an attraction structure with a set U ⊆ V and a kernel K is known and K is a singleton, we will usually simplify the problem by identifying all nodes in U with the node in K. The next two remarks deal with the consequences of such a collapse on future coincidence tests.

Remark 3.6. Let K_{1}, K_{2}, U_{1}, U_{2} ⊆ F be given sets with U_{i} ⊆ V, K_{i} singletons, S_{i} := F \ (K_{i} ∪ U_{i}) (i = 1, 2), K_{2} ⊆ K_{1} ∪ U_{1}, and U_{2} ⊆ U_{1}. If the nodes in U_{2} are identified with the node in K_{2}, the graph G is replaced by a graph Ĝ = (F̂, Ê), while U_{1} is replaced by a set Û_{1}. Each (K_{1}, S_{1})-flow on the transportation network with node set F and edge set E_{0} = E(K_{1}, U_{1}) ∪ E(U_{1}, U_{1}) ∪ E(U_{1}, S_{1}) saturating all sink edges induces a (K_{1}, S_{1})-flow on the transportation network with node set F̂ and edge set Ê_{0} = Ê(K_{1}, Û_{1}) ∪ Ê(Û_{1}, Û_{1}) ∪ Ê(Û_{1}, S_{1}), saturating all sink edges. This means that collapsing an attraction structure inside of another attraction structure does not destroy the outer structure.

We can also examine the behaviour of two ”competing” attraction structures which attract a subset of F to different kernels.

Remark 3.7. Let K_{1}, K_{2}, U_{1}, U_{2} ⊆ F be given sets such that |K_{i} ∩ A| ≤ 1, U_{i}∩K_{i} = ∅, U_{i} ⊆ V as well as K_{1}∩K_{2} = ∅, K_{i}∩U_{j} = ∅ (i ≠ j), and Ũ := U_{1}∩U_{2} ≠ ∅. Set S_{i} := F \(K_{i}∪U_{i}) (i = 1, 2) and S̃ := F \(U_{1}∪U_{2}∪K_{1}∪K_{2}). As above, we assume without loss of generality E(U_{i}, S̃) = E(U_{i}, S̃) and E(K_{i}, U_{i}) = E(K_{i}, U_{i}) (i = 1, 2). For i = 1, 2 there shall exist a (K_{i}, S_{i})-flow (φ_{e}^{(i)})_{e∈E_{0}^{(i)}} on the transportation network

with node set F and edge set E_{0}^{(i)} = E(K_{i}, U_{i}) ∪ E(U_{i}, U_{i}) ∪ (U_{i} × S_{i}) saturating all sink edges. (Note that the two transportation networks induce different intervals of capacity for the edges e ∈ E. For e ∈ E(Ũ, U_{1} \ Ũ) we have [ −ω_{e}, ω_{e}] as the interval of capacity for the first transportation network, but [ 0, ω_{e}] as the interval of capacity for the second network.) Now it is

∑_{e∈E(K_{1}∪(U_{1}\Ũ),Ũ)} ω_{e} ≥ ∑_{e∈E(K_{1}∪(U_{1}\Ũ),Ũ)} |φ_{e}^{(1)}|

≥ ∑_{e∈E(K_{1}∪(U_{1}\Ũ),Ũ)} φ_{e}^{(1)} − ∑_{e∈E(Ũ,K_{1}∪(U_{1}\Ũ))} φ_{e}^{(1)}

= ∑_{e∈E(Ũ,S̃)} φ_{e}^{(1)} + ∑_{e∈(Ũ×(K_{2}∪(U_{2}\Ũ)))} φ_{e}^{(1)}

= ∑_{e∈E(Ũ,S̃)} ω_{e} + ∑_{e∈E(Ũ,K_{2}∪(U_{2}\Ũ))} ω_{e}

≥ ∑_{e∈E(Ũ,S̃)} ω_{e} + ∑_{e∈E(Ũ,K_{2}∪(U_{2}\Ũ))} |φ_{e}^{(2)}|.

Likewise, it follows that

∑_{e∈E(Ũ,K_{2}∪(U_{2}\Ũ)))} |φ_{e}^{(2)}| ≥ ∑_{e∈E(Ũ,S̃)} ω_{e} + ∑_{e∈E(Ũ,K_{1}∪(U_{1}\Ũ))} ω_{e},

which means that

∑_{e∈E(K_{1}∪(U_{1}\Ũ),Ũ)} ω_{e} ≥ 2 ∑_{e∈E(Ũ,S̃)} ω_{e} + ∑_{e∈E(Ũ,K_{1}∪(U_{1}\Ũ))} ω_{e}

and therefore

∑_{e∈E(Ũ,S̃)} ω_{e} = 0

holds. Consequently, we have ω_{e} = 0 for all e ∈ E(Ũ, S̃). The chain of inequalities above simplifies to

∑_{e∈E(K_{1}∪(U_{1}\Ũ),Ũ)} ω_{e} ≥ ∑_{e∈E(K_{1}∪(U_{1}\Ũ),Ũ)} ω_{e},

which means that we have equality in each step, especially at the first two inequalities. This results in

∑_{e∈E(K_{1}∪(U_{1}\Ũ),Ũ)}(ω_{e} − φ_{e}^{(1)}) + ∑_{e∈E(Ũ,K_{1}∪(U_{1}\Ũ))}(ω_{e} + φ_{e}^{(1)}) = 0,

and after turning around all edges with φ_{e}^{(1)} < 0 we see that the flow (φ_{e}^{(1)})_{e∈E_{0}^{(1)}}

saturates all edges in E(Ũ, K_{1}∪(U_{1}\Ũ)). Likewise, after turning around those edges e with φ_{e}^{(2)} < 0, we see that the flow (φ_{e}^{(2)})_{e∈E_{0}^{(2)}} saturates all edges in E(Ũ, K_{2} ∪ (U_{2} \

Ũ)). By this, the set Ũ is completely determined. Furthermore, from each (K_{i}, S_{i})- flow (φ_{e}^{(i)})_{e∈E_{0}^{(i)}} we can construct by trivial modifications a (K_{i}, S_{i} ∪ Ũ)-flow on the transportation network with edge set

E(K_{i}, U_{i} \ Ũ) ∪ E(U_{i} \ Ũ, U_{i} \ Ũ) ∪ ((U_{i} \ Ũ) × (S_{i} ∪ Ũ))

which saturates all sink edges. This means that the set Ũ can be ”deleted” from each attraction structure. If only one attraction structure and a corresponding nonnegative flow are given, the only candidates for such a restructuring process are exactly those sets Ũ for which the flow saturates all edges in E(Ũ, F). A collapse of an attraction structure is no hindrance in the search for other attraction structures. These other attraction structures can still be found by the tools presented here.

In light of the two remarks above we should opt for a collapse of an attraction structure as soon as it has been found. To spare computation time, we should collapse nodes even if we have hope of finding a bigger attraction structure later on. The two last remarks show that we will not destroy any information needed later on by collapsing.

4. Arbitrary Weights. In this section, we will generalize the efficiently checkable reduction conditions derived in the last subsection such that they can handle problems with positive and negative weights. So, we are in search for sufficient conditions for the relations (2.1) that are easy to check. We will start by using the approach

E_{≥} := {e ∈ E | 0 > ω_{e}}.

If we now replace all weights ω_{e} < 0, e ∈ E(U, S), by their absolute values, we get a new problem in which we may introduce the additional constraints ω_{s}^{f,v} ≥ 0 (s ∈ S, v ∈ U, f ∈ F′_{≤}(pre(v), v)). This is exactly what we have done in the nonnegative case. If there exist weights for this new problem which fulfill (2.1), then there exist weights for the original problem which fulfill these conditions. The following example shows that the converse is not true.

Example 4.1. Let A = {a, b}, V = {v, w}, E = {(a, v), (v, b), (v, w), (w, b)}, ω_{va} = ω_{vw} = 1, ω_{vb} = 2, and ω_{wb} = −1. If we choose K = {a}, S = {b}, W_{1} = {v}, and W_{2} = {w}, we can first identify w with v and then v with a. If we use the absolute values of weights on the edges in E(U, S) = {(v, b), (u, b)}, our first step of identifying w with v is still feasible. However, the resulting weight ω_{vb} = 3 means that (2.1a) cannot hold for the node v.

The question remains if coincidence conditions for problems with positive and negative weights can also be checked efficiently by constructing a maximal (K, S)- flow. In what follows, we will give an affirmative answer to this question.

We will make use of our general assumption |W_{i}| = 1, i = 1, …, |U|. That we may do so without loss of generality has been discussed on page 6. We can therefore consider the conditions (2.2).

Let W_{ℓ} ≠ S be the ”deepest” set in W which is connected with a node in U by a negative weighted edge: ℓ := max{i < n | ∃ h ∈ U : ω_{hv} < 0 with W (v) = W_{i}}. Let W_{ℓ} = {v}. Furthermore, let h ∈ U be the ”deepest” node which is connected with W_{ℓ} by a negative weighted edge: W (h) = W_{j} and j := max{i < ℓ | W_{i} = {h} and ω_{hv} < 0}. We add two nodes s_{h} and s_{v} to S and replace the edge (h, v) by the edges (h, s_{h}) and (v, s_{v}), using the weights ω_{(h,s_{h})} = ω_{(v,s_{v})} = ω_{hv}. The result is a modified graph G̃ and a modified partition W̃. We will now show the following statement: if there exist weights which fulfill the conditions (2.2) with respect to G̃ and W̃, then there exist weights which fulfill the conditions (2.2) with respect to G and W.

We perform the construction from the proof of Theorem 1.2 (cp. [19, 22]) for the graph G, assuming that this construction is possible for G̃. For the steps i = n − 1, …, ℓ + 1 there will be no change compared to the construction for G̃. For i = ℓ we define ω_{h}^{f,v} := ω_{s_{v}}^{f,v} (f ∈ F′_{≤}(pre(v), v)) in order to construct the graph G_{ℓ} in an analogous way to G̃_{ℓ}. Then, the construction of the G_{i}, i = ℓ − 1, …, j + 1, can be done in an analogous way to the construction of the G̃_{i}. Since (2.2) holds for G̃, the graph G̃_{j} can be constructed. But the conditions necessary to construct G_{j} are even easier to fulfill, since terms from (2.2b) vanish in (2.2a) if they stem from the node s = s_{v}. Exactly those weights ω_{s_{v}}^{h,f} < 0 for which there is a path in G from f to v whose edges have nonnegative weights only do not occur. Likewise, for i = j − 1, …, 1 we can construct G_{i} in the same way as G̃_{i}. As a consequence, (2.2) holds for G and W.

If all edges in E(U, U) with negative weights are treated in this way, we have to work with a graph whose edges in E(U, U) have nonnegative weights only. If we use the absolute values of the weights on the edges in E(U, S), we can easily check the flow condition (Theorem 3.3 and 3.4) without knowledge of the partition W. The derivation above shows that this is a sufficient criterion for a coincidence on K ∪ U. Since we have only added nodes, redefined some edges and changed the sign on some numbers, we still have polynomial time complexity for our checking algorithm. Moreover, Remark 3.5 carries over to the case of arbitrary weights.

4.1. Former Results. To the author’s knowledge, the only coincidence conditions for multifacility location problems with positive and negative weights can be found in [21]. We will now examine if these conditions fit into the scheme presented in the last two sections. For a detailed statement of the former results we refer to [21].

Let U := {R, W_{1}, …, W_{n−1}, O} be a partition compatible with Ψ and T_{U} be an extended attraction set tree on G. Then, for all i, 1 ≤ i ≤ n−1, there exists a partition E(W_{i}, W_{i}) = T_{i} ∪S_{i} such that S_{i} ∩T_{i} = ∅ and ω_{e} ≥ 0 for e ∈ S_{i}. It is allowed that one or even both sets are empty. As a preliminary definition, define E_{s} as the set of all edges suppressed in T_{U}, K := R and S := O. We will now add more edges to E_{s}. For i ∈ {1, …, n−1} let Z be a directed cycle in T_{i} whose edges have positive weights only. Consider now those edges \overline{e} ∈ Z for which we have ω\overline{e} = δ_{Z} := min\{ω_{e} | e ∈ Z\} > 0. We remove these edges from T_{i} and add them to E_{s}. This modification is done for all directed cycles with positive edge weights only and all i ∈ {1, …, n − 1}. We sort the nodes in W_{i} (1 ≤ i ≤ n − 1) topologically according to the order induced by E′_{≤}(T_{i} \ E_{s}, T_{i} \ E_{s}) (cp. p. 13): W_{i} = {v_{1}^{(i)}, v_{2}^{(i)}, …, v_{m_{i}}^{(i)}}. Since T_{U} is a tree, we can sort the sets W_{1}, …, W_{n−1} topologically according to the order induced by the depth of the W_{i}. We assume without loss of generality that the given numbering already reflects this ordering. Both sortings induce a sorting on ⋃_{i=1}^{n−1} W_{i}. Set

W := {K, {v_{1}^{(1)}}, {v_{2}^{(1)}}, …, {v_{m_{1}}^{(1)}}, {v_{1}^{(2)}}, …, {v_{1}^{(n−1)}}, …, {v_{m_{n−1}}^{(n−1)}}, S}.

As it has been done in the case of attraction set trees (p. 10), we can now construct weights which fulfill (2.2a)–(2.2c) and (2.3). By the derivation of the last section it is clear that each extended attraction set tree can be detected by the conditions developed here.

5. Numerical Results. We will consider the following problem type. In this section let X := IR^{N} with 2 ≤ N ≤ 20, C = (IR^{N})^{V} as well as d_{e} = ω_{e}d, ω_{e} ∈ IR. Here, d is the metric induced by a p-norm (1.1 ≤ p ≤ 5). Almost all test cases of the literature known to the author belong to this class of problems. For a discussion of the modeling aspects with respect to the choice of the parameter p, we refer, e. g., to [5, 7, 8] and [35, p. 232]. The polynomial time algorithm described in § 3 and 4 works on problems from this class. We define, as it has already been done in § 4,

E_{≤} := {e ∈ E | 0 < ω_{e}}

and

E_{≥} := {e ∈ E | 0 > ω_{e}}.

5.1. The Nonlinear Programming Method. What kind of numerical algorithm should be used to solve a problem from the given class of nonconvex nondifferentiable optimization problems? In the literature known to the author only algorithms for the convex case, i. e. the case of positive weights (ω_{e} > 0, e ∈ E) (cp., e. g., [9, 27, 3]) or for the case |V | = 1 [10] are considered. Since our closest attention lies on the treatment of comparatively large scale unconstrained optimization problems, we use the conjugate gradient method in the modified form of Polak and Ribière (PRCG^{+} method) to minimize the objective function [25, Section 4.8]. Several tests in the literature confirm the competitiveness of this method, especially for large problems [33]. Moreover, the method needs to store only 4 vectors of length N|V |. Wesolowsky and Love [38] have already applied a CG-method on a special minisum multilocation problem. However, they have not documented any implementation details. Of course, the method may converge to a local minimum only. Therefore, in actual applications it has to be used with multistart techniques or in conjunction with a method from global optimization.

Since the PRCG^{+} method works on continuously differentiable objective functions only, we smooth the norms by using hyperbolic approximation [38, 15, 32, 23]. The approximation parameter ε is set to ε := 1 at the start of each iteration and damped by the factor 0.75 in each iteration step.

A restart is made after each mth iteration by using the negative gradient as the descent direction. The parameter m was set to m := 1+⌊|V |N/2⌋. If the number |V | is reduced by way of a successful coincidence test (cp. § 5.2), the number m is computed anew. Other restarts are made after unsuccessful line searches. In this line search, the simple Armijo criterion [4] with σ := 1 × 10^{−4} and quadratic Hermite interpolation has been used.

If the number of iterations is large, the approximation parameter ε used in the hyperbolic approximation will get so small that rounding errors occurring at coincidences will prevent a precise computation of ∇Ψ. If, on the other hand, the approximation parameter stays too large, we cannot use solutions of the approximated problem to come to conclusions about solutions of the original problem. This means that the usage of the approximated gradient in a stopping criterion of the iteration has to be augmented by other criteria. Therefore, we stop with the approximation X^{(t)} = (x_{v}^{(t)})_{v∈V} in the tth iteration, if the last line search was successful and for X^{(t)} and the approximation X^{(t−1)} from the (t − 1)th iteration we have that

∥∇Ψ(X^{(t)})∥_{2} < ε_{g}(1 + |Ψ(X^{(t)})|) (5.1)

or

Ψ(X^{(t−1)}) − Ψ(X^{(t)}) < ε_{f}(1 + |Ψ(X^{(t)})|) (5.2)

holds with certain problem specific stopping parameters ε_{f}, ε_{g} (cp., e. g. [25, S. 300ff.]). If the last line search was not successful or the last step length fulfills α < \sqrt{eps} with the machine precision eps, the only stopping criterion used is (5.1). The sensitivity of the method with respect to the stopping parameters was found to be rather small [19, Tabelle 5.2–5.3].

To compute a starting family (x_{v})_{v∈V} ∈ (IR^{N})^{V}, we define \underline{c}_{i} := min_{a∈A} (x_{a})_{i}, \overline{c}_{i} := max_{a∈A} (x_{a})_{i} (1 ≤ i ≤ N) and choose the ith coordinate of x_{v} ∈ IR^{N} (v ∈ V) randomly by using the uniform probability distribution on the interval [\underline{c}_{i}, \overline{c}_{i}]. Therefore, we have

x_{v} ∈ [\underline{c}_{1}, \overline{c}_{1}] × ⋯ × [\underline{c}_{N}, \overline{c}_{N}] ⊂ IR^{N}

for all v ∈ V. If ω_{e} ≥ 0 holds for all edges e ∈ E, at least one minimum of the objective function Ψ is contained in the product of these cubes [26, 16]. Naturally, this property does no longer hold if negative weights exist. However, in the test cases used below only a comparatively small number of weights is negative. As a consequence, the generation technique just described still seems to be an efficient way to generate starting points.

The program was developed under SPARCompiler Pascal 3.0 on a Sun SPARCstation-10 with SunOS Release 5.5.1 and compiled with the compiler option -O4. Double precision arithmetic was used throughout the whole program. Crosscompiling the source to C by using p2c version 1.20 posed no problems. However, program maintenance and testing was done with the original code.

5.2. Implementation of the Coincidence Tests. If a coincidence test shall be carried out with the methods from § 3 and 4, we have to provide a candidate set U ⊂ F with |U ∩A| ≤ 1. Recent results from complexity theory [31] make it likely that choosing the candidate set is more complex than detecting the coincidence itself. We will therefore use the following heuristic: after each iteration of the PRCG^{+} method in which a new approximation (x_{v})_{v∈V} has been computed, we define the subgraph G̃ := (V, Ẽ) of G as follows. Two nodes v, w ∈ V are connected by an edge in G̃ if and only if the corresponding locations are ”close to each other” and the nodes are already connected by a positive weighted edge in G. If \underline{c}_{i} and \overline{c}_{i} (i = 1, …, N) are defined as in § 5.1 we have with the current iteration vector (x_{v})_{v∈V} the relation (v, w) ∈ Ẽ if and only if

∑_{i=1}^{N} \frac{|(x_{v})_{i} − (x_{w})_{i}|}{max\{1, \overline{c}_{i} − \underline{c}_{i}\}} < δ

and

(v, w) ∈ E_{≤}.

Here, δ ∈ IR is a parameter which has to be chosen by the user. Each connectivity component of G̃ is then tested for coincidences. The combinatorial aspect to be found in all known coincidence tests enters here due to the the possibility that these connectivity components may be too large or too small. These sets may have too many or too few elements. One possibility consists now in applying the test derived on all subsets of each connectivity component. To reduce the computational effort, we use the following strategy instead: let Ũ ⊆ V be the node set of a connectivity component of G̃. All subsets U ⊆ Ũ with n elements, n = 1, 2, 3, 4, 5 and n = |Ũ| − 1 as well as n = |Ũ| will be used as candidate sets for the algorithm described in § 3. As kernel K, |K| = 1, we will use subsequently all sets

K ⊆ (Ũ \ U) ∪ ⋃_{v∈Ũ} F_{≤}(v, A).

As it has been shown in § 3, we only need to construct a maximal (K, F \(U ∪K))-flow on a certain transportation network and test saturation on all edges leading to a sink. Remark 3.6 and 3.7 show that it is advantageous to consider increasing cardinalities of the candidate set U and test all kernel K possible first before using another candidate set. The implementation follows this idea. If a coincidence test is successful, the nodes from the corresponding test set are identified with the node in the kernel immediately. The edges incident to those nodes are treated in an analogous way.

The strategy just described for computing the graph G̃ and the subsequent coincidence tests are carried out after each step of the CG-method until the T th iteration. Here, T ∈ IN_{0} is a parameter that has to be supplied by the user. That no coincidence test at all will be carried out can be achieved by setting T = 0.

The algorithm used to construct a maximum flow is the one from Edmonds and Karp [13] in the presentation of Gibbons [24]. More efficient algorithms exist [1, 2], but first test runs showed already such a clear improvement on earlier results that further implementations or the use of other methods have been postponed. Note that the coincidence test routine makes use of the topology of the graph G and the edge weights only, i. e. the implementation is independent of the weak metric used.

5.3. Test Problems. Most of the problems described in the literature are rather small. Moreover, negative weights are seldom considered, because the algorithms proposed by other authors usually do not work for this case. Therefore, we concentrate here on stochastically generated large scale test cases with positive and negative weights. A detailed discussion of the test results for test problems from the literature can be found in [19, Section 5.4].

In this section, the phrase ”to choose from the interval [α, β]” is used whenever a number in the interval [α, β] is computed by means of a random number generator simulating the uniformly distributed density on [0, 1 ].

For a given dimension N of the locational space, given |V |, |V | > 1, and given |A|, we will generate random problems as follows: The probability for the existence of an edge connecting two nodes in V with each other is 5/(|V | + 10). The probability for an edge e ∈ E(V, A) is 1/(|V | + |A|). A weight ω_{e} ∈ IR (e ∈ E) is negative with probability 0.05. If this is the case, it is chosen from the interval [−0.8 ln |V |, −1 ]. Otherwise, it is chosen with probability 0.95 from the interval [1, 1 + ln |V |] and with probability 0.05 from the interval [1, 1 + (ln |V |)^{2} ]. The average relative number of negative weights is now 5%. Raising this average or reducing the negative weights often leads to an objective function not bounded below.

After completing the process of generating edges and weights as described above, we determine two sets of nodes to simulate the clusters of nodes often found in applications. These two sets are defined by edges that carry relatively large weights. For n := ⌊|V |/5⌋ we choose randomly two n + 1-tuples (f_{0}, …, f_{n}), (g_{0}, …, g_{n}) ∈ F × V^{n} with pairwise independent components f_{0}, g_{0} …, f_{n}, g_{n}. In addition to the edges generated above we add the edges (f_{i}, f_{i+1}), (g_{i}, g_{i+1}) (i = 0, …, n − 1) to the graph and choose corresponding weights from the interval [1, 1+|V |]. If such an edge (f, g) or its counterpart (g, f) already exists, we identify the edges and add the weights together. After generating all edges we round off the weights to integer numbers.

Note that the test cases generated in this way are separable in the sense that the graph (V, E ∩ (V × V)) may contain several connectivity components. Moreover, it may be the case that E(V, a) = ∅ holds for an a ∈ A, which means that this object is not connected to the rest of the graph. Both of these problems will be detected by the code; the optimization process will take place on the objective functions induced by the connectivity components [34, 17, 20]. However, the test problems generated never had more than six connectivity components, even in the case |V | = 2000. For the problem mentioned with six components, five of these components contained exactly one node. Similar numbers hold for all other problems generated.

The ith coordinate of x_{a} ∈ IR^{N} (a ∈ A) is chosen from the interval [0, 100 ]. With this, we have x_{a} ∈ [0, 100]^{N} for the given dimension N ∈ IN. The p-norm used is determined by choosing the parameter p from the interval [1.1, 5 ].

The problem generation process just described is carried out for the dimensions N = 2, 3, 4, 5, 10, 15, 20 and the following (|V |, |A|)-pairs: (|V |, |A|) = (10k, 10(k + 1) for k = 1, …, 8, (|V |, |A|) = (100 + 10k, 100 + 10(k + 2)) for k = 0, …, 9, (|V |, |A|) = (200, 230), (|V |, |A|) = (100k, 100k + 50) for k = 2, …, 5, (|V |, |A|) = (100k + 50, 100(k + 1)) for k = 2, 3, 4, (|V |, |A|) = (100k, 100(k + 1)) for k = 6, …, 9 as well as (|V |, |A|) = (1000 + 200k, 1000 + 200(k + 1)) for k = 0, …, 5. Consequently, we consider 252 problems with up to 40000 unknowns.

The parameters described in § 5.1 and 5.2 are chosen problem specific as follows: ε_{f} := ε_{g} := 5 × 10^{−6}, δ := d/(|V | + |A|), and T := 1 + ⌊|V |/15⌋.

Fig. 5.1. Smallest objective function value found with coincidence tests divided by the smallest objective function value found without coincidence tests (N = 2, 3, 4).

0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 1.05 1.1  400 600 800 1000 1200 1400 1600 1800 2000 Quotient  |V |  N = 2 N = 3 N = 4

5.4. Test Results. All test runs have been made on a SUNSparc Ultra-2 with 256 MB main memory and a machine constant of eps ≈ 2.22 × 10^{−16}, using SunOS Release 5.5.1. A comparison shows that the PRCG^{+} method employed here seems to be competitive to algorithms from the literature [19, Tabelle 5.1].

In what follows, we briefly describe the performance of the code on the test problems with respect to the best objective function values found, the number of iterations and function evaluations, and the computation times. A more detailed discussion can be found in [19].

5.4.1. Objective Function Values. Figure 5.1 and 5.2 show the quotient of the smallest objective function value found with coincidence tests and the smallest objective function value found without coincidence tests for all problems with |V | ≥ 300. Reported are the objective function values for the largest connectivity component in the graph only. In all problems considered, the other connectivity components were trivial. Quotients less than 1 correspond to a decrease in the best objective function value found due to coincidence tests. As described above, the number of coincidence tests T was set anew for each problem considered.

In 191 of the 252 problems considered there was no deterioration or an improvement of up to 50%. For one problem, the best objective function value was more than halved, for two problems the decrease was between 50 and 60%, for four problems the decrease was between 60 and 70%, for 33 problems the decrease was between 70 and 80%, for 61 problems the decrease was between 80 and 90%, and for 66 problems the decrease was between 90 and 100%. For problems with |V | ≥ 1000 all quotients lie between 0.68 and 0.9. This means that in these cases the objective function values have been significantly reduced. On the other hand, an increase in objective function values when using coincidence tests has been observed for 61 problems. However, in 42 of these 61 problems, the increase was less than 10%. Moreover,

Fig. 5.2. Smallest objective function value found with coincidence tests divided by the smallest objective function value found without coincidence tests (N = 5, 10, 15, 20).

0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 1.05 1.1  400 600 800 1000 1200 1400 1600 1800 2000 Quotient  |V |  N = 5 N = 10 N = 15 N = 20

no deterioration was observed for problems with |V | > 600. For 200 < |V | ≤ 600, all increases in objective function values were less than 6%.

As an example, Figures 5.3–5.6 (p. 24–26) show the typical behaviour of the algorithm used with and without coincidence tests on large scale problems. In the first iterations, decreases in function values when using coincidence tests appear to be as good as the decreases when not using coincidence tests. But without coincidence tests the decrease slows down until a suboptimal point is reached. With coincidence tests, the stepwise decrease remains relatively efficient, until again strong improvements do not occur any longer. In total, better function values are achieved with less iterations by way of coincidence tests.

The coincidence tests implemented seem to delay the typical phenomenon of premature stopping of algorithms from nonlinear optimization, well observed for this class of problems [23]. This is especially clear for the large scale problems considered. For stochastically generated problems with smaller dimension, the results are not as uniform.

5.4.2. Iterations and Function Evaluations. Table 5.1 shows the number of iterations, the number of function evaluations, and the number of edge evaluations, i. e. the number of computations of the form ω∥x − y∥_{p} or ω∇(∥z∥_{p})|_{z=x−y}. Since the trivial connectivity components possibly existent in the graph may distort the overall impression, the iteration numbers cover the largest connectivity component only. However, the number of function and edge evaluations is the total number of these evaluations for a given problem. For example, the test case with N = 20, |V | = 2000, |A| = 2200 has two trivial connectivity components with one node in V and one edge each. Without coincidence tests, 49 and 58 iterations were needed to minimize the corresponding two separated objective functions. With coincidence tests, 2 iterations for each were needed.

The average amount of reduction of edge evaluations per problem due to coin-

Table 5.1 Sum of iterations, function evaluations, and edge evaluations for different dimensions.

iterations  function eval.  edge eval.
N T > 0 T = 0 T > 0 T = 0  T > 0  T = 0
2  3783  5305 15325 22802 35400607  52791090
3  4248  6731 16571 24857 39438837  66816811
4  5034  7427 19138 27099 48542483  73993688
5  5533  8208 20580 30467 48330410  78907387
10  7693 12653 25262 36689 61838056 128185983
15  8679 11975 28403 41025 72624636 121766039
20 14634 20207 41565 57226 99646015 179084508

Table 5.2 Sum of run times (in minutes) for different dimensions.

\begin{matrix}N & T > 0 & T = 0 \\ 2 & 8.3583 & 10.4715 \\ 3 & 10.3818 & 15.8697 \\ 4 & 14.4568 & 21.7636 \\ 5 & 16.0166 & 24.9682 \\ 10 & 32.0816 & 65.5998 \\ 15 & 52.4100 & 97.1467 \\ 20 & 88.7216 & 174.0734 \end{matrix}

cidence tests was 8.1% for N = 2, 14.3% for N = 3, 14.4% for N = 4, 10.4% for N = 5, and 16.5% for N = 10. For N = 15 there was an additional amount of work of 5.6%, while there was an additional amount of work of 1.5% for N = 20. These two deteriorations are due to singular bad results for N = 15, |V | = 70, |A| = 80 and N = 20, |V | = 200, |A| = 250. Without these two cases, we have an average amount of reduction of 3.8% for N = 15 and of 8.5% for N = 20. Analogous results hold for the number of function evaluations and the number of iterations. The total number of evaluations is reduced by a factor of ca. 2/3.

5.4.3. Computation Times. The computation times for the randomly generated problems considered are reported in Table 5.2. The documented times have been obtained with the UNIX time command. Input and output times are included in the figures given, since the set-up of the data structures needed (dynamically linked adjacency lists necessary for representing G) is an integral part of the algorithm. Profiles of the program developed show that ca. 10% of the computation time is needed for input, output, and set-up of data structures.

It can be clearly seen that the computation times with coincidence tests are far below the computation times without coincidence tests. In 192 of the 252 problems considered there have been observed computation time savings of up to a factor of 16. For fixed N, the average amount of reduction per problem is 7% for N = 2, 17% for N = 3, 20% for N = 4, 14% for N = 5, 19% for N = 10, −3% for N = 15 (This result is due to a singular deterioration for |V | = 70, |A| = 80. Without this case, the amount of reduction is 6%.), and 3% for N = 20. If only problems with |V | > 400 are considered, the average amount of reduction per problem is 16% for N = 2, 28% for N = 3, 30% for N = 4, 27% for N = 5, 38% for N = 10, 31% for N = 15, and 32% for N = 20. It seems that especially for large problems coincidence tests are responsible for a considerable reduction of the work needed. The total amount of computation time is approximately halved.

Profiles of the code during the solution of the larger test problems agree with the

Fig. 5.3. Objective function values until the end of the iteration for N = 2, |V | = 1800, and |A| = 2000, with (T > 0) and without (T = 0) coincidence tests.

1e+06 1.5e+06 2e+06 2.5e+06 3e+06 3.5e+06 4e+06 0  50  100  150  200  250  300  350  400 Ψ  Iteration  (T > 0) (T = 0)

reductions found in computation time and edge evaluations. Only 3% of the total computation time is used for coincidence tests. In contrast, function and gradient evaluations need about 80% of the total computation time.

5.5. Conclusions. In almost all problems with |V | > 300, using coincidence tests resulted in a decrease of best objective function values, iterations, function and edge evaluations, and computation time. These effects became more evident when the number of unknowns was increased.

More gains in efficiency with respect to computation times of methods which use coincidence tests have to be expected if the parameters T and δ, which control the number and the probability of success of these tests, are chosen optimal with respect to the problem class given. To this end, however, extensive numerical tests are necessary. Of course, the heuristic used here (cp. § 5.2) can be refined or replaced entirely.

If the metrics used are more realistic or more complex than the ones induced by p-norms, we will encounter a corresponding higher amount of work needed to compute a distance. For example, in discrete multilocation problems the locational space X is a graph and the distance between two points is induced by the weak metric of shortest paths. Therefore, we have to compute a shortest path between two points as soon as we want to compute the distance between them and the graph is sufficiently large [14]. Here, it is of prime importance to reduce the number of unnecessary distance calculations. The algorithms employed to construct candidate sets for coincidence tests may in this case be rather inefficient.

If global optimization problems of the scale considered here are investigated, restarts of the optimization method used are unavoidable to compute good approximative solutions. But for these restarts, coincidence tests are no longer necessary, since we can expect that we have already detected all detectable coincidences in former runs. Therefore, the computation times documented here correspond to the first

Fig. 5.4. Objective function values until the end of the iteration for N = 2, |V | = 2000, and |A| = 2200, with (T > 0) and without (T = 0) coincidence tests.

1.5e+06 2e+06 2.5e+06 3e+06 3.5e+06 4e+06 0  50  100 150 200 250 300 350 400 450 Ψ  Iteration  (T > 0) (T = 0)

Fig. 5.5. Objective function values until the end of the iteration for N = 20, |V | = 1800, and |A| = 2000, with (T > 0) and without (T = 0) coincidence tests.

2.5e+06 3e+06 3.5e+06 4e+06 4.5e+06 5e+06 0  200  400  600  800  1000  1200 Ψ  Iteration  (T > 0) (T = 0)

run of a multistart method. In all further runs, the collapsed problems will be solved faster than the original ones.

As a consequence, we can recommend the coincidence tests proposed here, as long as we are not only in search for a very rough approximation to an optimal solution. The tests work especially well when large scale problems are considered.

Fig. 5.6. Objective function values until the end of the iteration for N = 20, |V | = 2000, and |A| = 2200, with (T > 0) and without (T = 0) coincidence tests.

3.5e+06 4e+06 4.5e+06 5e+06 5.5e+06 6e+06 6.5e+06 7e+06 7.5e+06 8e+06 0  100  200  300  400  500  600 Ψ  Iteration  (T > 0) (T = 0)

REFERENCES

[1] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Some Recent Advances in Network Flows, SIAM Review, 33 (1991), pp. 175–219. Also published as [2].

[2] , Network Flows; Theory, Algorithms, and Applications, Prentice Hall, Englewood Cliffs, New Jersey, 1993.

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

[4] L. Armijo, Minimization of functions having Lipschitz continuous first partial derivatives, Pacific Journal of Mathematics, 16 (1966), pp. 1–3.

[5] W. Berens, The suitability of the weighted l_{p}-norm in estimating actual road distances, European Journal of Operation Research, 34 (1988), pp. 39–43.

[6] C. Berge and A. Ghuila-Houri, Programming, Games and Transportation Networks, Methuen and Co. Ltd., John Wiley and Sons Inc., London, New York, 1965. First published in France as Programmes, Jeux et Réseaux de Transport by Dunod, Paris, 1962.

[7] J. Brimberg and R. F. Love, Directional bias of the l_{p}-norm, European Journal of Operation Research, 67 (1993), pp. 287–294.

[8] , Estimating distances, in Drezner [12], ch. 1, pp. 9–32.

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

[10] P.-C. Chen, P. Hansen, B. Jaumard, and H. Tuy, Weber’s problem with attraction and repulsion, Journal of Regional Science, 32 (1992), pp. 467–486.

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

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

[13] J. Edmonds and R. M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems, Journal of the Association of Computing Machinery, 19 (1972), pp. 248–262.

[14] G. Ertl, Shortest path calculation in large road networks, Bericht 69, Spezialforschungsbereich F 003 (Optimierung und Kontrolle), Projektbereich Diskrete Optimierung, Karl-Franzens-Universität Graz & Technische Universität Graz, May 1996. Electronically distributed via

http://www.opt.math.tu-graz.ac.at/cgi-bin/replist.

[15] 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.

[16] 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.

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

[18] , 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.

[19] , 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.).

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

[21] , 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ó.

[22] , Multithreaded Dimension Reduction in Location Theory, Ergebnisberichte Angewandte Mathematik 153, Universität Dortmund, Fachbereich Mathematik, Universität Dortmund, 44221 Dortmund, Germany, April 1998. Submitted to SIAM Journal on Optimization.

[23] 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.

[24] A. Gibbons, Algorithmic graph theory, Cambridge University Press, Cambridge, London, New York, New Rochelle, Melbourne, Sidney, 1985.

[25] P. E. Gill, W. Murray, and M. H. Wright, Practical optimization, Academic Press Limited, Harcourt Brace and Company, London, 1995.

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

[27] 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.

[28] O. Lefebvre, C. Michelot, and F. Plastria, Sufficient conditions for coincidence in minisum multifacility location problems with a general metric, Operation Research, 39 (1991), pp. 437–442.

[29] , 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.

[30] C. Michelot. Private communication, September 26 1995. Lambrecht, EWGLA8 — EURO Working Group on Locational Analysis.

[31] C. Michelot and F. Plastria, Attraction Tree Detection is NP-Complete. Rapport du CERMSEM 9107, Université de Paris I — Panthéon-Sorbonne.

[32] J. G. Morris and W. A. Verdini, Minisum l_{p}-distance location problems solved via a perturbed problem and Weizsfeld’s algorithm, Operation Research, 27 (1979), pp. 1180–1188.

[33] J. Nocedal, The performance of several algorithms for large scale unconstrained optimization, in Large-Scale Numerical Optimization, T. F. Coleman and Y. Li, eds., SIAM Proceedings Series, Philadelphia, Pennsylvania, 1990, SIAM Society for Industrial and Applied Mathematics, pp. 138–151.

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

[35] , Continuous Location Problems, in Drezner [12], ch. 11, pp. 225–262.

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

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

[38] G. O. Wesolowsky and R. F. Love, A nonlinear approximation method for solving a gener-

alized rectangular distance Weber problem, Management Science, 18 (1972), pp. 656–663.

[39] 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.

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

[41] X. Xu, P. fang Hung, and Y. Ye, A simplified homogeneous and self-dual linear programming algorithm and its implementation, Annals of Operations Research, 62 (1996), pp. 151–171.

[42] Y. Ye, M. J. Todd, and S. Mizuno, An O(\sqrt{n}L)-iteration homogeneous and self-dual linear programming algorithm, Mathematics of Operations Research, 29 (1994), pp. 53–67.