A Polynomial Time Coincidence Detector

for Multifacility Location Problems

J. Fliege^{∗}, C. Michelot^{†}, and F. Plastria^{‡}^{§}

Revised Version — Limited distribution

Abstract. We reduce the problem of checking for coincidences in minisum multifacility location problems in a general metric space to the problem of constructing a maximal flow. If a coincidence is detected, the number of unknowns in a given problem can be reduced. Moreover, in a normed space setting the number of nondifferentiable terms in the objective function is then decreased.

The new coincidence check makes use of the topology and the edge-weights of the facility interactions graph only. It is shown that the algorithm proposed is best possible in the sense that any condition detecting more coincidences has to use additional properties of the underlying metric space. Moreover, the amount of work necessary to detect all space-independent coincidences increases only polynomially in the problem size given.

Key Words. Coincidence conditions, multifacility location problem, optimality criteria, metric spaces, flow problems

∗Assistant Professor, Fachbereich Mathematik, Universität Dortmund, Dortmund, Germany.

†Professor, AAO & LATEC, Université de Bourgogne, Dijon, France.

‡Professor, BEIF Department of Management Informatics, Vrije Universiteit Brussel, Brussels, Belgium.

§Corresponding author.

1 Introduction

Minisum multifacility location problems are easy to describe, but hard to solve. Usually, we have given a metric space (X, d), a set A of fixed facilities whose locations x_{a} ∈ X (a ∈ A) are known, and a set V of new facilities, the locations x_{v} ∈ X (v ∈ V) of which should be determined so as to minimize some sum of weighted distances between the facilities involved. Naturally, the distances between pairs of points in X are measured by the metric d. The amount of literature about this problem is monumental; see, e. g., Plastria [35] for a comprehensive list of references. Possible applications include locating one or more interacting facilities (warehouses, production plants, etc.) [28], computing the statics of spring systems [32], limit load analysis [6, 3], etc.

It has been observed that at optimal solutions clusters of facilities frequently tend to coincide, i.e. they share the same location. When this is known to happen, the dimension of the problem can be reduced.

This is of particular importance when X is finite or a network, see e. g. Tansel, Francis and Lowe [39, 40]. The problem is then basically of combinatorial nature with complexity strongly influenced by the number of new facilities. Lowering this number results in a reduction of the computational effort. However, none of the algorithms known to the authors used in these settings exploit coincidence information.

In a continuous setting, coincidences lead to the additional problem of nondifferentiabilities at optimal solutions, which often make special precautions necessary.

A first kind of such a precaution has been proposed by Calamai and Conn [8, 9]. They try to detect coincidences while applying a projected descent direction method, however, at the expense of a comparatively high computational effort. Moreover, some assumptions made in the convergence proofs on the structure of the problem seem to hold for special cases only [12].

A different approach consists of solving a differentiable reformulation of the primal or dual problem, as it has been proposed by Sherali and Al-Loughani [38]. However, up to now this reformulation seems to be possible for the Euclidean norm case only.

Other computational methods in the continuous setting are the Partial Inverse Method by Idrissi, Lefebvre and Michelot [22] or Michelot and Lefebvre [29] and a cutting plane approach [33, 14]. These methods are designed for nondifferentiable cost functions, which has to be seen as a disadvantage here. Since no second order information is used, we have a comparatively slow convergence [24, 42].

In recent times, interior point methods have been applied to special cases of the minisum multifacility location problem with Euclidean distances [6, 3] and with ℓ_{p}-norms [45]. Some complexity results have been proven, also [44, 43]. Since some of these algorithms have a polynomial time complexity, these methods seem to be not as sensitive to coincidences as others. This is confirmed by first numerical results [11, 4, 5, 44].

Some of the drawbacks mentioned above can be avoided by approximating the cost function by a differentiable one. This has been done, among others, by Eyster, White and Wierwille [13], by Morris and Verdini [31] and by Frenk and Kleijn [20, 19]. However, such an approximation is necessarily bad at solutions which include coincidences, because otherwise no differentiability can be achieved. Since the optimal locations of several facilities frequently coincide, the use of such approximation techniques alone seems to be problematic, because the algorithms run inevitably into stability problems. This can be seen by the computational results presented in [16]: testing coincidence conditions in the course of an iterative algorithm for solving general location problems results in a reduction of the computational effort by 50% to more than 90%. Moreover, due to a simultaneous reduction of the nondifferentiabilities, the solutions computed with the aid of coincidence conditions have usually a much higher quality than those found without them.

Witzgall [41] was probably the first to derive a sufficient condition for coincidence of a new facility with a fixed facility in a metric space. Extensions to more new facilities have been derived by Juel and Love [23], Lefebvre, Michelot and Plastria [27], and by Fliege [15, 17, 18, 16]. The arguments used by all these authors are essentially based on the axioms of a metric space only, while Lefebvre, Michelot and Plastria [25, 26], Plastria [34], and Cominetti and Michelot [10] describe coincidences by using tools from convex analysis.

In the present paper, a new sufficient condition for coincidence is introduced, which allows for a greater flexibility than the one obtained by way of attraction trees as outlined in [27], and still remaining valid in any metric space. Moreover, we derive a polynomial time algorithm which tests for the occurrence of a coincidence in a given problem. An example shows that this algorithm actually finds more coincidences than other conditions known so far. The condition outlined below makes use of the weights on the distances only. It is shown that any other coincidence condition detecting more coincidences than the condition proposed here has to employ additional assumptions concerning the metric space or the locations of the fixed facilities.

2 Notation and Statement

In this section, the notation used as well as the optimization problem under attack is defined. Basically, we recall the notation from [17, 25].

For an arbitrary set Λ and an arbitrary index set I define

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

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

2.1 Graphs

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

For any two subsets U_{1}, U_{2} ⊆ F, the set E(U_{1}, U_{2}) := E ∩ (U_{1} × U_{2}) denotes the set of edges starting from a node in U_{1} and leading to a node in U_{2}. If the direction of the edges is of no interest, the set

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

will be used. For a single node f ∈ F and a subset U ⊆ F set E(f, U) := E({f}, U). The other notation is modified analogously.

2.2 The Problem

In what follows, let F be a nonempty, finite set of nodes, ∅ ≠ E ⊆ F × F and G := (F, E) be a directed simple graph. The node set F represents a set of facilities, while the edge set E corresponds to interactions between these objects. Moreover, let (X, d) be a metric space. If, for every facility f ∈ F, a location x_{f} ∈ X is known, one can calculate the total cost of the interactions by computing the sum of all weighted distances between locations for which the corresponding nodes are connected by an edge. If we assume that the locations of some of the facilities are fixed in advance, we face the problem of finding locations for the other facilities such that the total cost of interactions is minimized. This leads to the following notation.

Let the node set F be partitioned into the nonempty sets A and V. For all a ∈ A let a fixed point x_{a} ∈ X be given, called the known or old location of the corresponding facility. The nodes v ∈ V represent facilities for which the best location is not yet known. For every edge e ∈ E let there be given a weight ω_{e} > 0, which will serve as the distance-cost proportionality factor. A location x_{v} ∈ X for a node v ∈ V is called new location of the corresponding facility.

Now, let in addition to the points x_{a} ∈ X (a ∈ A) a family of new locations (x_{v})_{v∈V} ∈ X^{V} be given. For any edge e = (f, g) ∈ E set x_{e} := (x_{f}, x_{g}) ∈ X × X. The cost of the interaction between f and g is measured by ω_{e}d(x_{e}). For a second family (x̂_{v})_{v∈V} ∈ X^{V} the notation x̂_{e} := (x̂_{f}, x̂_{g}) (where clearly x̂_{a} := x_{a} (a ∈ A)) will be used, and similarly for (x_{v}^{∗})_{v∈V}.

Definition 1 (Multifacility Location Problem) The minisum multifacility location problem is the following optimization problem:

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

Ψ : X^{V} ⟶ IR
(x_{v})_{v∈V} ⟼ ∑_{e∈E} ω_{e}d(x_{e}).  (1)

In what follows, we assume without loss of generality that E(A, A) = ∅, since edges joining two fixed facilities only show up as constant terms in the objective function.

2.3 Flows

Let T = (F, E) be a directed simple graph. For each edge e ∈ E let there be given 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 feasible flow when φ_{e} ∈ I_{e} holds for all e ∈ E. The value φ_{e} is called the flux on edge e.

It is a (feasible) circulation if in addition the flow is conserved at all nodes, i.e. for all f ∈ F one has

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

For any simple directed cycle C ⊂ E and any real number λ ∈ IR we define λC as the flow with flux λ on each edge e ∈ C and 0 on all other edges. It is easy to see that λC is a circulation on T.

We will make use of the following technical lemmas.

Lemma 1 Let α ∈ IR^{E} be a circulation on the graph T = (F, E) with capacity intervals I_{e} = [0, +∞[ for all e ∈ E. For any ē ∈ E with αē > 0, there exists a circulation β ∈ IR^{E} on the same graph satisfying βē = αē and 0 ≤ β_{e} ≤ αē for all e ∈ E.

Proof:

See [37, p. 71].

The feasible distribution problem defined as

Given capacity intervals I_{e} = [a_{e}, b_{e}] for all edges e and supply values b_{f} for all nodes f, find a flow φ such that it is feasible and div_{f}φ = b_{f} for all f.

has a solution if and only if

∑_{f} b_{f} = 0 and for all cuts Y ⊂ F, we have

∑_{f∈Y} b_{f} ≤ ∑_{e∈E(Y,F \Y)} b_{e} − ∑_{e∈E(F \Y,Y)} a_{e}.

□

Lemma 2 Let α ∈ IR^{E} be any circulation on the graph T = (F, E) without capacity constraints. For any ē ∈ E with αē ≠ 0, there exists a circulation β ∈ IR^{E} on the same graph satisfying

• βē = αē

• if α_{e} = 0 then β_{e} = 0

• if α_{e} > 0 then β_{e} ≥ 0 • if α_{e} < 0 then β_{e} ≤ 0

• |β_{e}| ≤ |αē| for all e ∈ E.

Proof:

Indeed, letting E_{α}^{−} = {e ∈ E : α_{e} < 0}, E_{α}^{+} = {e ∈ E : α_{e} > 0} and E_{α}^{0} = {e ∈ E : α_{e} = 0}, consider the network T′ := (F, E′) obtained from T by inverting all edges of E_{α}^{−} and deleting all edges of E_{α}^{0}. We obtain a nonnegative circulation α′ on T′ by changing the sign of each α_{e} on all edges e ∈ E_{α}^{−}.

Now use lemma 1 to construct a circulation β′ on T′, with β′ ; ē = α′ ; ē and 0 ≤ β′_{e} ≤

α′ ; ē = |αē| for all e ∈ E′.

Finally we define β on T by β_{e} = −β′_{e} for all e ∈ E_{α}^{−}, keeping β_{e} = β′_{e} for all e ∈ E_{α}^{+} and setting β_{e} = 0 for all e ∈ E_{α}^{0}.

One easily checks that β satisfies all sought properties. □

Given a nonempty source set S ⊂ F, S ≠ F and a nonempty sink set Q ⊂ F, Q ≠ F with S ∩ Q = ∅, the flow φ ∈ IR^{E} is an (S, Q)-flow on T if it is conserved at all f ∈ F \ (S ∪ Q). As a consequence, one then also has

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

and this value is the flow value v_{φ} of φ. For given sets S, Q ⊂ F as above, define U := F \ (S ∪ Q). In what follows, we will always assume E(S, F) = E(S, U) as well as E(F, Q) = E(U, Q). This results in E(S, S) = E(Q, Q) = E(U, S) = E(Q, U) = ∅. Moreover, we will frequently use for technical convenience an augmented network T̄ by introducing a new source node f_{S} and new sink node f_{Q} to F, and likewise adding new edges (f_{S}, s) for all sources s ∈ S and (q, f_{Q}) for all sinks q ∈ Q to E. All these new edges have a capacity interval ] − ∞, +∞[. In this way, one can consider networks in which the set of sources as well as the set of sinks are singletons.

If the corresponding capacity intervals for the edges of T, a set of sources and a set of sinks are given, the graph T is also called a transportation network. Edges in E(S, F) are called source edges, edges in E(F, Q) are called sink edges.

Lemma 3 Let a transportation network T = (F, E) be given with capacity intervals I_{e} = [a_{e}, b_{e}] and a source set S and sink set Q. Let φ be an (S, Q)-flow in T with flow value v_{φ}. Define the (strictly positive) value

ε = min ({φ_{e} − a_{e} : e ∈ E, φ_{e} > a_{e}} ∪ {b_{e} − φ_{e} : e ∈ E, φ_{e} < b_{e}}) .  (2)

For any edge ē ∈ E the following holds :

if there exists some (S, Q)-flow φ′ in T with the same flow value (v_{φ′} = v_{φ}) but with different flux on ē (φ′ ; ē ≠ φē), then there also exists some (S, Q)-flow ξ in T with the same flow value v_{ξ} = v_{φ} and a flux on ē differing by at least ε, i.e. |ξē − φē| ≥ ε

Proof: First observe that by its definition ε allows the following assertions for any edge e ∈ E:

If φ_{e} > a_{e}, then φ_{e} ≥ a_{e} + ε,

If φ_{e} < b_{e}, then φ_{e} ≤ b_{e} − ε. (3)

Now extend the network T to the new network T̄ by introducing a new source node f_{S} and new sink node f_{Q}, and with new edges (f_{S}, s) for all sources s ∈ S and (q, f_{Q}) for all sinks q ∈ Q, all with capacity interval IR. It is well known that there is an evident one-one relation between (S, Q)-flows φ on T and (f_{S}, f_{Q})-flows φ̄ on T̄, conserving the flow value, given by φ_{e} = φ̄_{e} for all e ∈ E, φ̄_{(f_{S},s)} = ∑_{e∈E(s,V)} φ_{e} for all sources s ∈ S, and φ̄_{(q,f_{Q})} = ∑_{e∈E(V,q)} φ_{e} for all sinks q ∈ Q. The new set of edges will be denoted by Ē, i. e. Ē := E ∪ ({f_{S}} × S) ∪ (Q × {f_{Q}}).

Consider any (S, Q)-flow φ′ in T with the same flow value but with different flux on ē ∈ E, and define the difference α = φ̄ − φ̄′. Then α defines a circulation on T̄ = (F̄, Ē), i.e. the flow-conservation equality holds at all f ∈ F̄, in particular also at f_{S} and f_{Q}, thanks to the equality v_{φ′} = v_{φ}.

The assumptions also imply that αē ≠ 0. By lemma 2 a circulation β ∈ IRĒ exists with the following properties: βē = αē; if α_{e} = 0 then β_{e} = 0; if α_{e} > 0 then β_{e} ≥ 0; if α_{e} < 0 then β_{e} ≤ 0; and |β_{e}| ≤ |αē| for all e ∈ E.

Next, define on T̄ the ({f_{S}}, {f_{Q}})-flow

ξ̄ = φ − \frac{ε}{|αē|}β

which evidently has the same flow value as φ. Finally, define ξ as the restriction of ξ̄ on T.

The flow ξ is feasible since for any edge e ∈ E we have

• If φ_{e} = φ′_{e}, α_{e} = β_{e} = 0, so ξ_{e} = φ_{e} ∈ I_{e}.

• If φ_{e} < φ′_{e} then φ_{e} < b_{e}, so by (3) φ_{e} ≤ b_{e} − ε. Since then also α_{e} < 0, we have 0 ≥ β_{e} ≥ −|αē|, and hence ξ_{e} = φ_{e} − \frac{ε}{|αē|}β_{e} ≤ φ_{e} + ε ≤ b_{e}. At the other hand ξ_{e} ≥ φ_{e} ≥ a_{e}.

• The inverse case when φ_{e} > φ′_{e} is handled similarly by symmetry.

Finally we also have |ξē − φē| = ε\frac{|βē|}{|αē|} ≥ ε. □

With this auxiliary result, we can prove the next theorem below, which will be needed later on in Section 4. There we will show how to construct coinciding clusters of points efficiently.

Transportation networks are the natural setting for maximal flow problems, i. e. problems where one tries to maximise the flow value. Let the set of all maximal flows on a transportation network T be denoted by M(T) ⊆ IR^{E}.

The flow φ ∈ IR^{E} saturates the edge e ∈ E with capacity interval I_{e} = [0, ω_{e}] or I_{e} = [−ω_{e}, ω_{e}] if |φ_{e}| = ω_{e}.

Theorem 4 Let a transportation network T be given with an edge set E such that E(F, S) = E(Q, F) = E(S, Q) = ∅. Let the capacity intervals be given as I_{e} = [0, ω_{e}], ω_{e} > 0, for e ∈ E(S, F \ S) ∪ E(F \ Q, Q) and I_{e} = [−ω_{e}, ω_{e}], ω_{e} > 0, for e ∈ E(F \ (Q ∪ S), F \ (Q ∪ S)). The set

E_{ns} := {e ∈ E : ∃ φ ∈ M(T) : |φ_{e}| < ω_{e}}

(where ns stands for nonsaturated) can be determined in time

O(|E|μ(|F |, |E|))

where μ(m, n) denotes the complexity of a maximal flow algorithm on a network with m nodes and n edges.

Proof: For an arbitrary maximal flow φ ∈ M(T) define U := F \ (S ∪ Q) and E(φ) := {e ∈ E : |φ_{e}| < ω_{e}} ⊆ E_{ns}.

First, suppose E(φ) = ∅. We may turn around edges in E(U, U) as we wish as long as we change the sign of the flow φ_{e} along these edges, and we do so with all edges e for which φ_{e} < 0 holds. If E(U, U) is now free of directed cycles then all flows ψ ∈ M(T) satisfy E(ψ) = ∅ and therefore E_{ns} = ∅. Otherwise there exists an directed cycle C ⊆ E(U, U) along which φ is positive. Taking λ = min_{e∈C} φ_{e}, the flow ψ = φ − λC ∈ M(T) satisfies E(ψ) ≠ ∅.

Hence we assume in the sequel that E(φ) ≠ ∅ and define

ε := min ({ω_{e} − |φ_{e}| : e ∈ E(φ)} ∪ {|φ_{e}| : e ∈ E(S, U) ∪ E(U, Q), φ_{e} ≠ 0}) > 0.

For any ē ∈ E \E(φ) consider the modified transportation network Tē in which ωē is replaced by ωē − ε. Construct a maximal flow ξ on Tē. If the flow values of ξ and φ are the same, we obviously have ē ∈ E_{ns}, since then ξ ∈ M(T) and |ξē| ≤ ωē−ε < ωē. Inversely, if ē ∈ E_{ns}, then some η ∈ M(T) exists with |ηē| < ωē, and hence by lemma 3 some η′ ∈ M(T) exists with |η′ ; ē| ≤ ωē − ε. It follows that η′ is also a feasible flow on Tē which has the same flow value as φ, so must be maximal. Therefore, if the flow values of ξ and φ differ, we must have ē ∉ E_{ns}.

Iterating this test over all ē ∈ E \ E(φ) thus determines E_{ns}.

After calculating the first maximal flow φ in time μ(|F |, |E|) and constructing E(φ), we might need to check if E(U, U) is free of directed cycles. This can be done in time O(|E(U, U)|^{2}) by repeated breadth-first-search. After that, O(|E|) maximal flows have to be constructed. Since we always have n ≤ μ(m, n), the total complexity is O(|E|μ(|F |, |E|)). □

Remark 5 As seen in the proof of the theorem above, the actual complexity is slightly lower than stated. If φ ∈ M(T) is the maximal flow constructed firsthand and E(φ) is defined as in the proof, then the actual number of operations needed is O((|E| − |E(φ)| + 1)μ(|F |, |E|)).

Corollary 6 Let e ∉ E_{ns} and φ, ψ ∈ M(T). Then φ_{e} = ψ_{e}.

Proof: We have |φ_{e}| = |ψ_{e}| = ω_{e}. Suppose φ_{e} = ω_{e} but ψ_{e} = −ω_{e}. Since μ := (1/2)φ + (1/2)ψ ∈ M(T), we get μ_{e} = 0 and e ∈ E_{ns}, a contradiction. □

This corollary means that a transportation network T induces on edges in E\E_{ns} a unique orientation by way of the direction in which all maximal flows are using the edge.

Corollary 7 The sets

E_{+} := {e ∈ E \ E_{ns} | ∀φ ∈ M(T) : φ_{e} = ω_{e}},
E_{−} := {e ∈ E \ E_{ns} | ∀φ ∈ M(T) : φ_{e} = −ω_{e}}

are well defined. Moreover, the sets E_{ns}, E_{+}, E_{−} form a partition of E.

As a consequence, we may invert the edges of E_{−}, which moves them to E_{+}. Therefore, in the remainder we consider without loss of generality all always saturated edges to have a positive flow, i. e. E is partitioned into E_{ns} and E_{+}. (Note that this is automatically the case if for some φ ∈ M(T) all edges with negative flow are inverted.)

Observe also that there always exists a flow φ^{k} ∈ M(T) such that E_{+} = {e ∈ E : φ_{e}^{k} = ω_{e}} and E_{ns} = {e ∈ E : |φ_{e}^{k}| < ω_{e}}. Indeed, if E_{ns} = ∅ the M(T) is a singleton. But if E_{ns} ≠ ∅, then for each e ∈ E_{ns} there exists some φ^{e} ∈ M(T) with |φ_{e}^{e}| < ω_{e}, and it suffices to take their average, i.e.

φ^{k} = \frac{1}{|E_{ns}|} ∑_{e∈E_{ns}} φ^{e}.

3 A best possible coincidence condition

It is a well observed fact that often several new facilities tend to coincide at an optimal solution of the minisum multifacility location problem as defined by (1). It is therefore of interest to be able to detect such coincidences without actually having to solve the problem. This leads to a reduction of the problem’s dimension and of the degree of nondifferentiability in the normed space setting [27, 17].

Let there be given two nonempty disjoint sets K, U ⊆ F such that |K| = 1 and U ⊆ V. The question that we address in this section is: does there exist a minimum (x̂_{v})_{v∈V} of Ψ such that x̂_{v} = x̂_{w} holds for all v, w ∈ U ∪ K? We will give a new criterion for this and show that it cannot be improved in a general setting. The computational effort involved is studied in the next section.

With the abbreviation S := F \ (K ∪ U) we assume without loss of generality E(U, K) = E(U, K) and E(S, U) = E(S, U), the direction of the edges being arbitrary. The two sets K and U define a transportation network T_{S,K} with node set F, source set S, sink set K, edge set

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

and intervals of capacity [0, ω_{e}] for e ∈ E(S, U) ∪ E(U, K) and [−ω_{e}, ω_{e}] for e ∈ E(U, U).

Theorem 8 Let there exist an (S, K)-flow φ on T_{S,K} which saturates all source edges and let K = {k}. Let (x_{v})_{v∈V} ∈ X^{V} be given and define (x̂_{v})_{v∈V} ∈ X^{V} by x̂_{u} := x_{k} for all u ∈ U and x̂_{v} := x_{v} for all v ∈ V \ U. Then

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

Moreover, if there exists an e ∈ E(U, U ∪ K) with |φ_{e}| < ω_{e} and d(x_{e}) ≠ 0, we have

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

Proof: We have

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

= ∑_{e∈E(S,U)} ω_{e}d(x̂_{e}) − ( ∑_{e∈E(S,U)} ω_{e}d(x_{e}) + ∑_{e∈E(U,U)} ω_{e}d(x_{e}) + ∑_{e∈E(U,K)} ω_{e}d(x_{e}))(4)

Let φ = (φ_{e})_{e∈E} be a flow on T_{S,K} saturating the source edges. If E(S, U) = ∅, the first term in (4) is zero and the theorem trivially holds. So we assume from now on that E(S, U) ≠ ∅, so φ is a nonzero flow.

If φ_{e} < 0 for an edge e = (u, v) ∈ E(U, U), we can replace this edge by (v, u) and φ_{e} by −φ_{e} without destroying the flow property. We may therefore assume without loss of generality that φ_{e} ≥ 0 for all e ∈ E_{T}. Moreover, due to the feasibility of the flow, we have φ_{e} ≤ ω_{e} for all e. By replacing ω_{e} by φ_{e} in (4) we have

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

≤ ∑_{e∈E(S,U)} ω_{e}d(x̂_{e}) − ( ∑_{e∈E(S,U)} φ_{e}d(x_{e}) + ∑_{e∈E(U,U)} φ_{e}d(x_{e}) + ∑_{e∈E(U,K)} φ_{e}d(x_{e})) .(5)

According to the Conformal Realization Theorem [37, Chapter 4B], the nonzero (S, K)-flow φ can be written as

φ = ∑_{P ∈P} φ^{(P)},  (6)

where P is the set of all directed paths joining S with K and for each P ∈ P the nonnegative flow φ^{(P)} ∈ IR^{E} is zero outside the path, φ_{e}^{(P)} = 0 ∀ e ∉ P, and constant along the path, φ_{e}^{(P)} = φ_{P} ≥ 0 ∀ e ∈ P. As a consequence,

∑_{e∈E(S,U)} φ_{e}d(x_{e}) + ∑_{e∈E(U,U)} φ_{e}d(x_{e}) + ∑_{e∈E(U,K)} φ_{e}d(x_{e})

= ∑_{e∈E(S,U)} ∑_{P ∈P} φ_{e}^{(P)}d(x_{e}) + ∑_{e∈E(U,U)} ∑_{P ∈P} φ_{e}^{(P)}d(x_{e}) + ∑_{e∈E(U,K)} ∑_{P ∈P} φ_{e}^{(P)}d(x_{e})
= ∑_{P ∈P} ( ∑_{e∈E(S,U)} φ_{e}^{(P)}d(x_{e}) + ∑_{e∈E(U,U)} φ_{e}^{(P)}d(x_{e}) + ∑_{e∈E(U,K)} φ_{e}^{(P)}d(x_{e}))
= ∑_{P ∈P} ( ∑_{e∈P ∩E(S,U)} φ_{e}^{(P)}d(x_{e}) + ∑_{e∈P ∩E(U,U)} φ_{e}^{(P)}d(x_{e}) + ∑_{e∈P ∩E(U,K)} φ_{e}^{(P)}d(x_{e}))
= ∑_{P ∈P} φ_{P} ( ∑_{e∈P ∩E(S,U)} d(x_{e}) + ∑_{e∈P ∩E(U,U)} d(x_{e}) + ∑_{e∈P ∩E(U,K)} d(x_{e})) .  (7)

Let \overline{e} = (s, u) ∈ E(S, U) and consider the set P(\overline{e}) of all paths P ∈ P of which the first edge is \overline{e}. All these paths end in k. Using the triangle inequality, we get for any P ∈ P(\overline{e})

\begin{aligned}d(x̂\overline{e}) & = & d(x_{s}, x_{k}) \\ & ≤ & ∑_{e∈P} d(x_{e}) \\ & = & ∑_{e∈P ∩E(S,U)} d(x_{e}) + ∑_{e∈P ∩E(U,U)} d(x_{e}) + ∑_{e∈P ∩E(U,K)} d(x_{e}) \end{aligned} (8)

Observe that φ(P) ; \overline{e} = 0 for P ∉ P(\overline{e}). Hence, due to (6), ∑_{P ∈P(\overline{e})} φ(P) ; \overline{e} = φ\overline{e}. As a consequence, multiplying (8) with φ_{P} and summing over all P ∈ P(\overline{e}) yields

φ\overline{e}d(x̂\overline{e}) ≤ ∑_{P ∈P(\overline{e})} φ_{P} ( ∑_{e∈P ∩E(S,U)} d(x_{e}) + ∑_{e∈P ∩E(U,U)} d(x_{e}) + ∑_{e∈P ∩E(U,K)} d(x_{e})) . (9)

The saturation property ensures φ\overline{e} = ω\overline{e}. Moreover, we have

P = ⋃_{e∈E(S,U)} P(e)

and P (e_{1}) ∩ P (e_{2}) = ∅ for e_{1} ≠ e_{2}. Summing up (9) over all \overline{e} ∈ E(S, U) results in

∑_{e∈E(S,U)} ω_{e}d(x̂_{e}) ≤ ∑_{P ∈P} φ_{P} ( ∑_{e∈P ∩E(S,U)} d(x_{e}) + ∑_{e∈P ∩E(U,U)} d(x_{e}) + ∑_{e∈P ∩E(U,K)} d(x_{e})) .

By (5) and (7), this means that

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

In order to show the second part of the theorem, it suffices to observe that if there exists an e ∈ E(U, U ∪ K) with |φ_{e}| < ω_{e} and d(x_{e}) ≠ 0 the inequality (5) is strict.

□

Corollary 9 Let there exist a (S, K)-flow on T_{S,K} which saturates all source edges and let there exist a minimum of Ψ. Then there exists a minimum (x̂_{v})_{v∈V} ∈ X^{V} of Ψ with x̂_{u} = x̂_{k} for all u ∈ U.

Moreover, if the flow does not saturate an edge e ∈ E(U, U ∪ K), all minima (x_{v}^{∗})_{v∈V} fulfil d(x_{e}^{∗}) = 0, i. e. the facilities connected by the edge always coincide at optimality.

Note that the additional assumption of existence of a minimum is always fulfilled when d is induced by a norm and X is the corresponding normed space.

Remark 10 In case we have different metrics d_{e} given for each edge e ∈ E in our problem definition, we can make use of the notion of comparison factors, see [17]. For this, let α_{e}, β_{e} > 0 and d be a metric on X with

α_{e}d(x, y) ≤ d_{e}(x, y) ≤ β_{e}d(x, y)  (10)

for all x, y ∈ X and e ∈ E. By using the weights α_{e}ω_{e} resp. β_{e}ω_{e} on the corresponding edges (cp. [17]), we obtain results similar to the theorem and the corollary above.

The coincidence condition presented in Theorem 8 and Corollary 9 is independent of the metric used. This is the main difference with the condition proposed by Cominetti and Michelot [10], whose approach works for the ℓ_{1}-norm case only. Of course, their condition is more powerful in this specific case.

Note that Lefebvre, Michelot, and Plastria [25, 26] and Plastria [34] use ideas from subdifferential calculus to derive a characterization of the complete solution set. However, the resulting highly nonlinear and high dimensional conditions do not seem to be easily applicable on arbitrary problems. Their coincidence condition, however, Figure 1: Graph of the problem defined in Example 1

[figure: .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; a; b; c; d; u; v; w; 7; 7; 2; 2; 6; 6; 8]

involves only several one-dimensional inequalities with respect to the weights. In this respect, it is similar to our condition proposed here. But it is not clear how to check their condition efficiently.

The following example shows that the condition proposed here is not only easy to apply, but actually detects more coincidences than other conditions known so far.

Example 1 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. (cp. Figure 1).

Furthermore, let Ψ((x_{u}, x_{v}, x_{w})) = ∑_{e∈E} ω_{e}d(x_{e}) with an arbitrary metric d. Now, define K := {a}, U := V and consequently S = {b, c, d}. We may turn around edges as we wish, and we will do so by using (b, u), (c, v), and (d, w) instead of (u, b), (v, c), and (w, d). As it is easy to see, a maximum flow (φ_{e})_{e∈E_{T}} is given by φ_{dw} = 8, φ_{bu} = φ_{cv} = 2, φ_{uw} = φ_{vw} = −4, and φ_{ua} = φ_{va} = 6. This flow saturates all source edges, and therefore we have Ψ((x_{a})_{v∈V}) ≤ Ψ((x_{v})_{v∈V}) for all (x_{v})_{v∈V} ∈ X^{V}. As a consequence, there exists a minimum (x̂_{v})_{v∈V} of Ψ with x̂_{u} = x̂_{v} = x̂_{w} = x_{a}.

Since none of the edges (u, w), (v, w), and (u, a) (and also (v, a), but this is superfluous) are saturated by φ, the second part of Corollary 9 shows that we have x_{u}^{∗} = x_{v}^{∗} = x_{w}^{∗} = x_{a} for all minima. This allows us to conclude that this is the unique optimal solution.

It has to be noted that in this example none of the coincidence conditions in [17] or [18] will detect any coincidence.

Consider a subtree (H, E_{H}) of G with root r ∈ F such that each node in the tree except possibly the root is a new facility, i. e. H \ {r} ⊆ V. Without loss of generality, the edge between a node v ∈ H, v ≠ r, should be oriented towards its father: (v, father(v)) ∈ E_{H}, but (father(v), v) ∉ E_{H} for all v ∈ H \ {r}. Such a tree is called an attraction tree [25, 27, 26] if for each node v ∈ H, v ≠ r, the weight on (v, father(v)) is greater or equal to the sum of weights on edges leading to the children of v or to nodes outside the tree:

ω_{(v,father(v))} ≥ ∑_{e∈E_{H}∩E(F,v)} ω_{e} + ∑_{e∈E(v,F \H)} ω_{e}.  (11)

In [25, 27, 26] a coincidence result is obtained similar to Theorem 8, i. e. if (H, E_{H}) is an attraction tree then Ψ((x̂_{v})_{v∈V}) ≤ Ψ((x_{v})_{v∈V}) holds, where (x̂_{v})_{v∈V} is defined by x̂_{h} := x_{r} (h ∈ H) and x̂_{v} := x_{v} (v ∈ V \ H), see [27, 26]. However, it is easy to see that no attraction tree exists in Example 1.

On the other hand, we have the following

Lemma 11 If there exists an attraction tree (H, E_{H}) of G with root r ∈ F, then there exists a flow on the transportation network T_{F \H,{r}} saturating all source edges.

Proof: Consider the transportation network T_{S,K} with K = {r} and S = F \ H. By (11), we see that the capacity on each edge in the attraction tree is large enough to allow for a flow φ with φ_{e} = 0 for all e ∉ E_{H} ∪ E(S, H) and that saturates all source edges of the transportation network. □

As a consequence, the coincidence condition proposed in this paper detects more coincidences than the attraction tree condition. In fact, the next lemma basically states that the coincidence condition of Theorem 8 is the best possible one for arbitrary metric spaces.

Lemma 12 Let U ⊆ V and let K = {k} ⊂ F \ U. Let S = F \ (U ∪ K). Consider the metric space (IR, |·|) as the locational space in use. Assume that for an arbitrary choice of fixed facility locations x_{a} ∈ X (a ∈ A), for any family of free facility locations (x_{v})_{v∈V}, and for the corresponding family (x̂_{v})_{v∈V} defined as in Theorem 8, the inequality

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

holds. Then, there exists a flow on the transportation network T_{S,K} which saturates all source edges e ∈ E(S, U).

Proof: Consider an instance of the problem with x_{a} = 1 (a ∈ A, a ≠ k), but let x_{k} = 0 if k ∈ A. Let W ⊆ U and choose a t ∈] 0, 1 [. Now define the family (x_{v})_{v∈V} ∈ IR^{V} by x_{u} := 0 for all u ∈ U \ W, x_{v} := 1 for v ∈ V \ U, but x_{w} := t for all w ∈ W as well as x_{k} := 0 if k ∈ V. A simple calculation shows that

Ψ((x_{v})_{v∈V}) = Ψ((x̂_{v})_{v∈V}) + ( ∑_{e∈E(K∪U\W,W)} ω_{e} − ∑_{e∈E(S,W)} ω_{e}) t.

By assumption, we have Ψ((x̂_{v})_{v∈V}) ≤ Ψ((x_{v})_{v∈V}). As a consequence,

∑_{e∈E(S,W)} ω_{e} ≤ ∑_{e∈E(K∪U\W,W)} ω_{e}  (12)

holds. Since W ⊆ U is an arbitrary set, the Theorem of Gale (cp., e. g., [21] or [2, Theorem 6.12]) shows us that there exists a source-edge saturating flow on the transportation network T_{S,K}. □

Remark 13 In the lemma above, suppose that an edge \overline{e} ∈ E(U, U) is given such that Ψ((x̂_{v})_{v∈V}) < Ψ((x_{v})_{v∈V}) follows as soon as d(x_{e}) ≠ 0 holds. Using the same reasoning as in the proof above, we conclude then that

∑_{e∈E(S,W)} ω_{e} < ∑_{e∈E(K∪U\W,W)} ω_{e}  (13)

holds for all W ⊆ U with \overline{e} ∉ E(W, W). The edge \overline{e} appears only in the right-hand side of each of these inequalities and in none of the inequalities (12) for other W. Because there are only a finite number of subsets W ⊆ U, we can consider a perturbed problem in which, instead of ω\overline{e} we use ω\overline{e} − ε as the weight on the edge \overline{e}. If ε > 0 is sufficiently small, the inequalities (13) still hold for the perturbed problem. Applying the Theorem of Gale to this perturbed problem yields the existence of an (S, K)-flow saturating all source edges. This is also a flow on the unperturbed problem which does not saturate the edge \overline{e}.

As Lemma 12 shows, the coincidence condition stated in Theorem 8 is best possible for location problems on the real line. But this condition uses information about the weights ω_{e} of the interconnections e ∈ E only. Therefore, the condition is the best possible one among all those using this kind of information only. A coincidence condition detecting more coincidences will always have to employ characteristics of the locational space and/or the relative positions of the fixed facilities.

Conclusion 14 No coincidence condition applicable to arbitrary metric spaces and using information of the graph G and the weights on the edges only can detect more coincidences than the coincidence condition from Theorem 8.

4 Detecting Coincidences Efficiently

In this section, we will derive a polynomial time algorithm to detect all subsets of facilities which coincide at some or at all optimal solutions of any multifacility location problem with the given graph and weights in an arbitrary metric space.

Obviously, given S and K, we can check in polynomial time if there exists an (S, K)-flow on T_{S,K} which saturates all source edges: we just have to compute a maximal flow on the transportation network and can then check in polynomial time the saturation property on the source edges for this flow. If not even a maximal flow can saturate all source edges, no flow exists which does. Since there are many polynomial time algorithms for constructing a maximal flow (see, e. g., [1, 2] for an overview of algorithms), we can for given K and U as in Section 3 check in polynomial time if a coincidence of U with K occurs.

In case only a set U ≠ ∅ is considered as candidate set for coincidences, but K remained unspecified, we can use successively all one-elemental subsets K ⊂ F \ U as sink sets of the transportation networks T_{F \U,K}. As a consequence, the actual algorithm for checking coincidence of the set U with some node k ∉ U has an additional factor of |F \ U| in its runtime. This does not change the polynomial time complexity given U, of course. However, it is not clear if bounds polynomial in the problem size exist for the number of sets U which have to be considered to detect all possible coincidences in this way. Therefore, this approach might not yield a polynomial algorithm to detect all subsets of facilities which coincide. As a consequence, we rather fix the sink k ∈ F and construct a maximal corresponding U.

Consider therefore the following coincidence detection problem: We are in search of sets U ⊆ V, and K = {k}, k ∉ U, such that S = F \ (U ∪ K) is the source set of a source-edge saturating flow on the transportation network T_{S,K}. For practical reasons, the set U should be as large as possible. We also want to identify which nodes in U are connected by edges that remain unsaturated in at least one such flow, in order to detect mandatory coincidences between facilities. The following theorem indicates how to solve this problem.

Theorem 15 Let μ(m, n) be the complexity of a max-flow algorithm on a network with m edges and n nodes. For a given weighted graph G = (F, E) and a given element k ∈ F, it is then possible to compute in O(|E|μ(|E|, |F |)) time the following subsets of V:

1. The subset of nodes W_{1} which coincide with k in any optimal solution of any problem instance of a multifacility location problem with graph G.

2. The subset of nodes W_{2} for which the following statement holds for all problem instances with the graph G: either there exists no solution, or there exists at least one solution such that the set W_{2} coincides with k.

3. The list of subsets (U_{i})_{i} ⊆ W_{2}, such that in any problem instance with the graph G, for every i all nodes of U_{i} mutually coincide in any optimal solution, and coincide with k in at least one optimal solution.

Proof:

For k ∈ F, consider the network T (k) := T_{A\K,K}. We have S = A \ K and U = V \(S∪K). This network has capacity intervals [0, ω_{e}] for e ∈ E(S, U)∪E(U, K) and [−ω_{e}, ω_{e}] for e ∈ E(U, U).

Theorem 4 and the observations following it ensure that we can calculate for this network the set E_{ns} in time O(|E|μ(|F |, |E|)). We also know that some maximal flow φ^{k} exists for which E_{ns} is the set of nonsaturated edges, and that E_{ns} is the largest edge set which can be obtained in this way from some maximal flow.

In the graph (F, E_{ns}) define S̄ ⊂ V as the set of all new facilities connected to some element of S, define W_{1} as the set of new facilities connected to K, and denote the remaining connected components (all contained in U) by (U_{i})_{i}. Finally, denote the union of all these sets by W_{2}.

By the max flow min cut theorem there exists a cut of minimum capacity in the network T (k) which separates S from K, and any maximum flow saturates all edges of this cut, showing that none of these edges belong to E_{ns}, which proves that S̄ is disjoint from W_{1}. Hence we also have

W_{2} := W_{1} ∪ ⋃_{i} U_{i} = V \ S̄.

By direct application of Theorem 8 and Conclusion 14 using the flow φ^{k} we obtain all three claimed properties. □

Looping over all k ∈ F results in an additional factor of |F | in the runtime. Therefore, we have the following corollary.

Corollary 16 The coincidence detection problem can be solved in polynomial time. For a given weighted graph, solving all coincidence detection problems on this graph can be achieved in polynomial time.

Note that this is in strong contrast to the NP-completeness of attraction-tree detection problem [30], which, as shown in Lemma 11 and Example 1, can yield less coincidences than the algorithm outlined above.

An example of an application of the results derived in this paper will be discussed in a forthcoming work [36].

Acknowledgements. We are indebted to an anonymous referee whose remarks allowed us to generalize some results and to simplify many proofs.

References

[1] Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Some Recent Advances in Network Flows. SIAM Review, 33(2):175–219, June 1991. Also published as [2].

[2] Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows; Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs, New Jersey, 1993.

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

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

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

[5] Knud D. Andersen and Edmund Christiansen. A symmetric Primal-Dual Newton method for Minimizing a Sum of Norms. Electronically distributed as

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

[6] Knud D. Andersen, Edmund Christiansen, and Michael L. Overton. Computing limit loads by minimizing a sum of norms. Unpublished, October 17, 1994.

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

[8] P. H. Calamai and A. R. Conn. A stable algorithm for solving the multifacility location problem involving Euclidean distances. SIAM Journal on Scientific and Statistical Computing, 1:512–526, 1980.

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

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

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

[12] Achiya Dax. A note on Optimality Conditions for the Euclidean Multifacility Location Problems. Mathematical Programming, 36:72–80, 1986.

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

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

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

[16] Jörg Fliege. Effiziente Dimensionsreduktion in Multilokationsproblemen. PhD thesis, Universität Dortmund, Fachbereich Mathematik, Universität Dortmund, 44221 Dortmund, June 1997. Shaker Verlag, Aachen. An english translation is available from the author on request.

[17] Jörg Fliege. Nondifferentiability Detection and Dimensionality Reduction in Minisum Multifacility Location Problems. Journal of Optimization Theory and Applications, 94(2):365–380, August 1997.

[18] Jörg Fliege. Coincidence Conditions in Multifacility Location Problems with Positive and Negative Weights. European Journal of Operations Research, 104(2):310–320, January 1998.

[19] 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 Rotterdam, Oostmaaslaan 950–952, 3063 DM Rotterdam, The Netherlands, 1994.

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

[21] D. Gale. A theorem on flows in networks. Pacific Journal of Mathematics, 7:1073–1082, 1957.

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

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

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

[25] O[dile] Lefebvre, C[hristian] Michelot, and F[rank] Plastria. Geometric Interpretation of the Optimality Conditions in Multifacility Location and Applications. Journal of Optimization Theory and Applications, 65(1):85–101, April 1990.

[26] O[dile] Lefebvre, C[hristian] Michelot, and F[rank] Plastria. Errata corrige Geometric Interpretation of the Optimality Conditions in Multifacility Location and Applications. Journal of Optimization Theory and Applications, 68(2):393– 394, February 1991.

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

[28] Robert F. Love, James G. Morris, and George O. Wesolowsky. Facilities Location. Models & Methods. North-Holland, New York 1988.

[29] C[hristian] Michelot and O[dile] Lefebvre. A primal-dual algorithm for the Fermat-Weber problem involving mixed gauges. Mathematical Programming, 39:319–335, 1987.

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

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

[32] Michael L. Overton, A quadratically convergent method for minimizing a sum of euclidean norms. Mathematical Programming, 27:34–63, 1983.

[33] F[rank] Plastria. Solving general continuous single facility location problems by cutting planes. European Journal of Operation Research, 29:98–110, 1987.

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

[35] Frank Plastria. Continuous Location Problems. In Zvi Drezner, editor, Facility Location: A Survey of Applications and Methods, Springer Series in Operations Research, chapter 11, pages 225–262. Springer Verlag, New York, 1995.

[36] Frank Plastria and Jörg Fliege. Centralizing Hubs often pays. Forthcoming. Vrije Universiteit Brussel, 1999.

[37] R. T. Rockafellar. Network Flows and Monotropic Optimization. Jorn Wiley, New York, 1984.

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

[39] B. C. Tansel, R. L. Francis, and T. J. Lowe. Location on Networks: A Survey. Part I: The p-Center and p-Median Problems. Management Science, 29:482– 497, 1983.

[40] B. C. Tansel, R. L. Francis, and T. J. Lowe. Location on Networks: A Survey. Part II: Exploiting the Tree Network Structure. Management Science, 29:498– 511, 1983.

[41] Christoph Witzgall. Optimal Location of a Central Facility, Mathematical Models and Concepts. Report No. 8388, National Bureau of Standards, Applied Mathematics Division, Operations Research Section. June 30, 1964.

[42] P. Wolfe. Convergence theory in nonlinear programming. In J. Abadie, editor, Integer and Nonlinear Programming, chapter 1, pages 1–36. North-Holland Publishing Company, Amsterdam, London, 1970.

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

[44] Guoliang Xue and Yinyu Ye. An Efficient Algorithm for Minimizing a Sum of Euclidean Norms with Applications. SIAM Journal on Optimization, 7(4):1017–1036, November 1997.

[45] Guoliang Xue and Yinyu Ye. An Efficient Algorithm for Minimizing a Sum of P-Norms. SIAM Journal on Optimization Volume 10, Number 2 pp. 551–579