The Hamiltonian p–median problem ^{∗}

Holger Glaab Institute for Mathematics University of Augsburg

86135 Augsburg

   glaab@math.uni-augsburg.de

Alexander Pott Institute for Algebra and Geometry University of Magdeburg 39016 Magdeburg

                                  alexander.pott@mathematik.uni-magdeburg.de

Submitted: February 16, 1999; Accepted: April 25, 2000

Abstract

We deal, from a theoretical point of view, with the asymmetric Hamiltonian p–median problem. This problem, which has many applications, can be viewed as a mixed routing location problem. An ILP-formulation based on a new class of inequalities (subtour number constraints) is presented. The associated Hamiltonian p–median polytope is examined, in particular its dimension and its affine hull. We determine which of the defining inequalities induce facets.

1 Introduction

In the last decade, the class of so–called mixed routing location problems attracted a lot of research interest. Many different problem variants have been developed. This is due to its practical relevance in many real world situations and the breakthroughs in solving the related problem, the traveling salesman problem (TSP). These new methods provided the necessary framework for investigating more complicated combinatorial optimization problems.

This paper deals with a special case of combined routing location problems, the Hamiltonian p–median problem (HpMP). This problem has been introduced by Branco and Coelho [2]. The investigation is motivated by a practical application, the so–called laser multi–scanner problem (LMSP), see [6] and [12], which can be modelled as an asymmetric Hamiltonian p–median problem with an additional class of side constraints. The HpMP itself arises in its own or as an embedded problem in a wide range of practical applications like school location, depot location, multi-depot vehicle routing or industrial process scheduling.

∗Both authors thank the German Ministry for education and science for supporting this project under the name Combinatorial optimization problems in the leather industry. The content of this paper forms part of the first author’s doctoral thesis.

Up to know, for the HpMP as well as for the LMSP, no exact solution approaches are known. Since one of the most promising approach for an exact solution of a hard combinatorial optimization problem is the cutting plane method, (see [9] or [13] for the symmetric TSP, [4] for the asymmetric TSP and [1] for the precedence–constrained ATSP) we investigate an ILP–formulation of the HpMP and the associated Hamiltonian p–median polytope. Even if it is not possible to solve the HpMP exactly, polyhedral investigations can be used in a branch & cut–algorithm in order to produce good lower bounds by using cutting planes.

We assume that the reader is familiar with the basic notion of graph theory and combinatorial optimization.

Let D = (V, A) be a complete directed graph on N = |V | vertices and let

c : A ↦ ℝ

be a cost function associated with the set of arcs A. We may assume that the graph contains loops. Throughout this paper we denote the vertices by lower case letters i, j, … and the arc from vertex i to vertex j by ij or (i, j). Loops are arcs of the type (i, i). In the context of the Hamiltonian p–median problem, the set of vertices can be interpreted as the locations of customers and of (putative) depots. The cost c(a) describes the distribution costs if arc a is used in order to serve a customer. Each customer has to be served by one and only one depot. Then the Hamiltonian p–median problem (HpMP) consists of selecting p depots from V and assigning each customer to exactly one depot, such that the total distribution costs are minimal. Note that each depot also coincides with one customer since the vertices of the graph D denote customers and depots. It is clear that each vertex of a subtour can be chosen as a depot. In order to minimize the total distribution costs, we have to solve a TSP on the subgraphs induced by the customers assigned to the same depot.

In graph–theoretic terms, the HpMP is equivalent to determining p pairwise disjoint cycles (with respect to some objective function) covering the vertex set V. In this context, let

C_{p} := {(C^{1}, …, C^{p})| C^{i} = (V_{i}, A_{i}) circuit in D, V_{i} ∩ V_{j} = ∅ for i ≠ j, ⋃_{i=1}^{p} V_{i} = V }

denote the set of all Hamiltonian p–medians. As most interesting combinatorial optimization problems, the HpMP has been proven to be NP-complete [3].

The paper is organized as follows: In Section 2, we provide a new ILP–formulation for the HpMP, which uses less variables than those proposed in [2] and which induces a polyhedral description of the problem. The formulation in [2] is not exactly an ILP– formulation since it provides no explicit description of the associated polytope. In Section 3, we obtain several results about the associated HpM–polytope in the asymmetric as well as the symmetric case. A preview on a forthcoming paper and some conclusions are contained in the last section of this paper.

2 A polyhedral ILP–formulation for the Hamiltonian p–median problem

In the literature, different formulations for the Hamiltonian p-median problem exist, two of which are given in [2]. One formulation is based on a set partitioning approach, the second one is based on a vehicle routing problem. Both formulations have in common that their descriptions as integer optimization problems are not polyhedral ones: The set of feasible solutions is not described as the set of integral points of some polytope. Let us be more specific. We consider the proposed vehicle routing approach in [2]. We have two classes of binary variables: The variable y_{i}^{k} ∈ {0, 1} with {i, k} ∈ V × {1, …, p} indicates whether node i belongs to the Hamiltonian circuit C^{k} or not. A second class of variables x_{ij}^{k} ∈ {0, 1} with {i, j, k} ∈ V × V × {1, …, p} is 1 if and only if node i precedes node j in circuit C^{k}:

x_{ij}^{k} = \{ \begin{matrix}1 : & ij ∈ C^{k} \\ 0 : & ij ∉ C^{k}. \end{matrix}  (1)

Then the existence of more than p circuits is prevented by the constraints

∑_{i,j∈S} x_{ij}^{k} ≤ |S| − 1

for all S ⊂ R_{k} := {i : y_{i}^{k} = 1} with |S| ≥ 1 and k = 1, …, p. The number of inequalities of this type depends on the variables y_{i}^{k}. Therefore, in this version we do not have a fixed list of linear inequalities that can be used to check whether a certain vector (y, x) describes a Hamiltonian p-median.

In this paper, we will present a polyhedral representation of the Hamiltonian pmedian polytope by inequalities which avoid the variables y_{i}^{k}.

For certain applications it is necessary to permit loops, i.e. circuits which consist of only one point and whose arc set is {(i, i)}. Such a single depot supplies itself and no other customers. But there are also examples where it makes no sense to permit single loops. In such a case, each circuit must contain at least two different vertices. The costs for loops can be viewed as the costs for distributing the goods (transporting the people) within depot i. In this paper, we will discuss only the situation where loops are not allowed. It is not difficult to transform our results into the more general case.

The problem of finding a general polyhedral ILP (integer linear programming) formulation lies in the description of the partition of V into p disjoint subtours. Therefore, we introduce the term of m–partitions P_{m} of V as the set of all partitions of V into m subsets which are pairwise disjoint and which form a cover of V, i.e.

P_{m} := {(S_{1}, …, S_{m}) : S_{i} ⊂ V , S_{i} ∩ S_{j} = ∅ for i ≠ j, ⋃_{i=1}^{m} V_{i} = V }.  (2)

Moreover, for each element (S_{1}, …, S_{m}) ∈ P_{m} let

A(S_{1}, …, S_{m}) := {ij ∈ A : i ∈ S_{k}, j ∈ S_{l}, 1 ≤ k < l ≤ m}  (3)

denote the directed m–cut associated with (S_{1}, …, S_{m}). The existence of nonempty p+1– cuts will guarantee the existence of at most p subtours. We propose an ILP–formulation of the Hamiltonian p–median problem which is based on a separate characterization of each circuit and uses N(N − 1)p variables. (If we allow loops we would need N^{2}p variables.) Our formulation can be applied for several objective functions where it is necessary to know the circuits explicitly. It is possible to find a description of Hamiltonian p–medians which uses just N^{2} variables (indicating whether an arc is contained in the Hamiltonian p–median or not). This reduced description will be described and investigated in a forthcoming paper (see also [5]). But in that case, an objective function where, for instance, the maximum of the cycle lengths has to be minimized, cannot be analyzed.

Let C^{k} be a set of arcs in the graph D, where k = 1, …, p. We define the associated incidence vector x^{(C^{1},...,C^{p})} ∈ {0, 1}^{N(N−1)p} as in (1). The incidence vector x^{(C^{1},...,C^{p})} has length N(N −1)p since we only want to consider the case where loops are not allowed. A vector x^{(C^{1},...,C^{p})} describes a Hamiltonian p-median if and only if the following equations are satisfied:

∑_{k=1}^{p} ∑_{i=1}^{N} x_{ij}^{k} = 1 (j = 1, …, N)  (4)

∑_{k=1}^{p} ∑_{j=1}^{N} x_{ij}^{k} = 1 (i = 1, …, N)  (5)

∑_{i=1}^{N} x_{ij}^{k} − ∑_{l=1}^{N} x_{jl}^{k} = 0 (j = 1, …, N; k = 1, …, p)  (6)

∑_{k=1}^{p} ∑_{ij∈A(S_{1},...,S_{p+1})} x_{ij}^{k} ≥ 1 ((S_{1}, …, S_{p+1}) ∈ P_{p+1})  (7)
∑_{i,j∈V} x_{ij}^{k} ≥ 2 (k = 1, …, p)  (8)
x_{ij}^{k} ∈ {0, 1} (k = 1, …, p; ij ∈ A).  (9)

The equations (4) and (5) ensure that each vertex has exactly one successor and

one predecessor in ⋃_{k=1}^{p} C^{k}, i.e. the C^{k}’s are unions of circuits. Equation (6) guarantees that each vertex is assigned to exactly one of the sets C^{k}. Together with (4) and (5) the last condition also implies that any two subtours are vertex disjoint. The so–called subtour number constraints (SNC) (7) exclude the existence of more than p different circuits. Finally, the inequalities (8) ensure that each circuit consists of at least two arcs. Additionally, (8) in connection with (7) ensure that each feasible solution consists of exactly p circuits or subtours.

We note that the SNC have an equivalent formulation

∑_{k=1}^{p} ∑_{i=1}^{p+1} x^{k}(A(S_{i})) ≤ ∑_{i=1}^{p+1}(|S_{i}|) − 2 = N − 2  (10)

where x^{k}(A(S_{i})) := ∑_{v,w∈S_{i}} x_{vw}^{k} denotes the number of arcs which are contained in the complete subgraph D|S_{i} := (S_{i}, A|(S_{i} × S_{i})). This is just a reformulation of (7) where the intersection size of ⋃_{k=1}^{p} C^{k} with the arc set

{ij ∈ A : i, j ∈ S_{k} for some k ∈ {1, …, p + 1}}

is considered. Some minor modifications are needed if loops are allowed. In this case, the incidence vector x^{(C^{1},...,C^{p})} has length N^{2}p. Moreover, the right-hand-side of (8) has to be changed to 1.

3 The HpM–polytope

We define the Hamiltonian p–median polytope P^{N,p} (HpM-polytope) as the convex hull of the incidence vectors of all Hamiltonian p-medians:

P^{N,p} := conv{x^{(C^{1},...,C^{p})}| (C^{1}, …, C^{p}) ∈ C_{p}, |C^{k}| ≥ 2, k = 1, …, p}.

In the case p = 1, the HpM–polytope coincides with the asymmetric travelling salesman polytope, which has been intensively studied, see [7] and [11], for instance. One can comprehend the complexity of the HpM-polytope by enumerating the number of its vertices:

Lemma 1 The HpM–polytope P consists of

N! ∑_{(n_{1},...,n_{p})∈K^{N,p}} \frac{1}{∏_{k=1}^{p} n_{k}}

vertices, where

K^{N,p} := {(n_{1}, …, n_{p}) : ∑_{k=1}^{p} n_{k} = N, n_{k} ≥ 2}

denotes the number of p–compositions of N with each component being at least 2.

Proof. Let n_{k} := |C^{k}| denote the number of arcs of the k-th circuit for k = 1, …, p. It is well known that the number of different possibilities to assign n_{k} vertices to circuit C^{k} for k = 1, …, p is the multinomial coefficient

\binom{N}{n_{1}, …, n_{p}} = \frac{N!}{∏_{k=1}^{p}(n_{k}!)}.  (11)

We receive an overall number of

\frac{N! ∏_{k=1}^{p}(n_{k} − 1)!}{∏_{k=1}^{p}(n_{k}!)} = \frac{N!}{∏_{k=1}^{p} n_{k}}  (12)

feasible solutions per given p–composition(n_{1}, …, n_{p}) and the proof is complete. ⋄

We obtain another formula for the number of feasible solutions: We define

K^{N,p}(π) := {(n_{1}, …, n_{p}) ∈ K^{N,p}, ∏_{k=1}^{p} n_{k} = π}

as the set of all p–compositions of N with constant product value π. Then we can express the number in (12) by

N! ∑_{π} \frac{|K^{N,p}(π)|}{π}

In this section, our main goal is to determine the dimension of P^{N,p}. We write

P^{(N,p)} := {x ∈ {0, 1}^{(N(N−1)p} : D_{1}x = 1  (13)
D_{2}x = 1  (14)
D_{3}x = 0  (15)
Ax ≤ b }.  (16)

Here D_{1} corresponds to the equality constraints (4), D_{2} to (5) and D_{3} corresponds to the equality constraints (6). Finally, A corresponds to the inequality constraints (7) and (8). By 1_{m}, resp. 0_{m} we denote the all-one-vector, resp. the all-zero-vector of dimension m. Usually, the subscript will be omitted.

The vector x has length N(N − 1)p and its coordinates (hence the columns of D_{1}, D_{2}, D_{3} and A) are indexed by the arcs ij of the graph D = (V, A) and the circuits C^{k}, k = 1, …, p:

x = (x_{ij}^{k})_{ij∈A, k∈{1,...,p}}.

Throughout this paper, we use the following notation and terminology: Let I_{k} denote the index set corresponding to C^{k}, i.e. I_{k} := {(i, j, k) : ij ∈ A}. The columns indexed by I_{k} are sometimes called the ”k–th column complex”. If A is a matrix whose columns are indexed by arcs and circuits, we denote the k-th column complex of A by A_{k}: These are the columns of A indexed by elements from I_{k}.

Note that D′ := \binom{D_{1}}{D_{2}} is just a p-fold copy of a 2N ×N(N −1)-matrix T corresponding to the first column complex. It is well known from the ATSP (see [7]) and also easy to see that the rank of this matrix is 2N − 1 if N ≥ 3 and 2 in case N = 2: If N ≥ 3, the column space generated by T is just the set of vectors (y_{1}, … y_{2N}) satisfying

∑_{i=1}^{N} y_{i} − ∑_{i=N+1}^{2N} y_{i} = 0

where the first N coordinates correspond to the rows of D_{1} and the remaining rows to D_{2}.

Now we consider the third class of equation constraints D_{3} corresponding to (6). We define D := \binom{D′}{D_{3}}. We obtain the following lemma (as mentioned above, (i) is folklore):

Lemma 2 Let N ≥ 3 and p ≤ ⌊N/2⌋. Then

(i) rank(D′) = 2N − 1.

(ii) rank(D_{3}) = p(N − 1).

(iii) rank(D) = p(N − 1) + N.

Proof. (ii) Due to our partition of the columns into column complexes, the matrix D_{3} is block diagonal and consists of p identical diagonal blocks D_{3}^{1}, …, D_{3}^{p}, each of which is an element from {−1, 0, 1}^{N×N(N−1)}. All these matrices have the same rank. It follows directly that

rank(D_{3}) = p · rank(D_{3}^{1}).

We determine the rank of D_{3}^{1} by determining the dimension of the nullspace (kernel) of the linear mapping

M : ℝ^{N} ↦ ℝ^{N(N−1)}, x ↦ xD_{3}^{1}.

As each column of D_{3}^{1} has exactly one entry equal to 1, one entry equal to −1 and N − 2 entries equal to 0, we have 1 ∈ nullspace(M). Obviously, the rank of D_{3}^{1} is at least N − 1, hence rank(D_{3}^{1}) = N − 1 and (ii) holds.

(iii) To prove the second statement, it is sufficient to show that the dimension of the intersection of the rowspaces of D′ and D_{3} equals N − 1. Similar to (ii), we can restrict ourselves to a column complex D^{′r} of size 2N × N(N − 1) and a block diagonal complex D_{3}^{r} of size N × N(N − 1). (It is sufficient to show rowspace(D_{3}^{r}) ⊂ rowspace(D^{′r}) since the matrices D^{′1}, …, D^{′p} are all equal.) This can be seen as follows: The row of D_{3}^{r} corresponding to node i is the difference of the rows of D^{′r} corresponding to the equalities ∑_{k} ∑_{j} x_{ij}^{k} = 1 and ∑_{k} ∑_{j} x_{ji}^{k} = 1 restricted to the r-th column complex. ⋄

For further polyhedral investigations it would be desirable to find an irredundant

representation of Dx = ( \begin{matrix}1_{2N} \\ 0_{Np} \end{matrix} ) where all equations are linearly independent. The

following lemma characterizes such an irredundant representation:

Lemma 3 An irredundant representation of Dx = ( \begin{matrix}1_{2N} \\ 0_{Np} \end{matrix} ) is given by the N +p(N −1)

linearly independent equations

∑_{k=1}^{p} ∑_{i=1}^{N} x_{ij}^{k} = 1 (j = 1, …, N)  (17)

∑_{i=1}^{N} x_{ij}^{k} − ∑_{l=1}^{N} x_{jl}^{k} = 0 (j = 1, …, N − 1; k = 1, …, p).  (18)

Proof. We have to show that the N outdegree constraints (5) and the p disjoint–cycle or flow conservation constraints

∑_{i=1}^{N} x_{iN}^{k} − ∑_{l=1}^{N} x_{Nl}^{k} = 0 k = 1, …, p

are implied by (4) and (18) which also proves the linear independence of the above equations. Given node j ∈ 1, …, N − 1}, we add the disjoint–cycle constraints for k = 1, …, p and get

∑_{k=1}^{p}(∑_{i=1}^{N} x_{ij}^{k} − ∑_{l=1}^{N} x_{jl}^{k}) = 0.

This shows that the outdegree constraints (5) hold for j = 1, …, N − 1. If one finally adds for each k = 1, …, p the N − 1 different disjoint–cycle constraints one obtains

0 = ∑_{j=1}^{N−1}(∑_{i=1}^{N} x_{ij}^{k} − ∑_{l=1}^{N} x_{jl}^{k}) = ∑_{i=1}^{N} x_{iN}^{k} − ∑_{l=1}^{N} x_{Nl}^{k}

which also implies

∑_{k=1}^{p} ∑_{j=1}^{N} x_{Nj}^{k} = 1

and we are done. ⋄

Since

P^{N,p} ⊆ \{x ∈ ℝ^{N(N−1)p}| ( \begin{matrix}D′ \\ D_{3} \end{matrix} ) x = ( \begin{matrix}1 \\ 0 \end{matrix} )\}

it follows that

dim(P^{N,p}) ≤ N(N − 1)p − (N − 1)p − N = pN(N − 2) − N + p = p(N − 1)^{2} − N.

As usual, the dimension of P^{N,p}, denoted by dim(P^{N,p}), is the affine dimension, which equals the affine rank of P minus one. Since in our case the vector 0 is not contained in the affine hull of P^{N,p}, the affine dimension of P^{N,p} is the dimension of the linear span of P^{N,p} minus one.

The next theorem shows that, unless N = 2p, this upper bound is tight. In order to prove this main theorem we will state several technical lemmata which together yield the main theorem: For this reason, we introduce the following notation: F^{N,p} denotes the matrix whose rows are the incidence vectors of all possible Hamiltonian p-medians (where each circuit has length at least 2 since loops are not allowed). Moreover, we divide F^{N,p} = (F^{1}, …, F^{p}) into p different column complexes F^{1}, …, F^{p} each of column size N(N − 1) corresponding to the p circuits C^{1}, …, C^{p}.

The first lemma provides the dimension of a single column complex:

Lemma 4 For k = 1, …, p we have

rank(F^{k}) = \{ \begin{matrix}\frac{N(N−1)}{2} & if N = 2p, N ≥ 4 \\ (N − 1)^{2} & otherwise. \end{matrix}

Proof. First we consider the case N = 2p. Consequently, |C^{k}| = 2 holds for all k = 1, …, p. There are exactly \binom{N}{2} different circuits of length two. Since all these different circuits are pairwise arc–disjoint the associated incidence vectors are linearly independent. But the incidence vectors of these tours are the rows of F^{k}, and the statement is proven. Now let N > 2p. It suffices to consider F^{1}. Let Z^{1} ⊂ (0, 1)^{N(N−1)} denote the set of all incidence vectors of the Hamiltonian p–median restricted to the first circuit. Since every circuit and consequently the associated incidence vectors fulfill the so–called flow– conservation constraint

∑_{i} x_{ij} = ∑_{k} x_{jk}

for all nodes j = 1, …, N, we have

⟨Z^{1}⟩ ⊂ {x ∈ ℝ^{N(N−1)} : ∑_{i} x_{ij} = ∑_{k} x_{jk}, j = 1, …, N}.

But the latter vector space is identical to the vector space of the incidence vectors of all feasible circulations whose dimension is |A|−|V |+z where z is the number of connectivity components of the underlying digraph (see [10]). In our case, z = 1. Thus we obtain

dim(cs(F^{1})) ≤ N(N − 1) − N + 1 = (N − 1)^{2}

where cs denotes the columnspace of a matrix. If we can construct (N − 1)^{2} linearly independent columns, we are done. For this reason, we consider the (N − 1)^{2} columns of F^{1} indexed by the arc set

I := {ij ∈ A : 1 ≤ i ≤ N − 1, j ≠ i} = A \ δ^{+}({N}).

Note that δ^{+}({i}), resp. δ^{−}({i}) denotes all arcs having tail i (resp. head N). Moreover, we consider the (N − 1)^{2} rows of F_{1} which are associated with the N − 1 circuits C_{k} := {(1, k, 1) : k = 2, …, N} of cardinality 2 and the (N − 1)(N − 2) circuits C_{jk} := {(1, j, k, 1) : j, k ∈ V \ {1}, j ≠ k}. To prove the linear independence of the columns indexed by I, we look at the system of linear equations

∑_{ij∈I} λ_{ij}f_{ij}^{1} = 0

where f_{ij}^{1} denotes the column of F^{1} corresponding to arc ij. More generally, f_{ij}^{l} denotes the respective column in F^{l}. The nonexistence of a nontrivial solution is verified by considering the (N − 1)^{2} rows corresponding to the circuits C^{k} and C^{jk}:

λ_{1j} + λ_{j1} = 0 (j = 2, …, N − 1)  (19)
λ_{1N} = 0  (20)
λ_{1j} + λ_{jN} = 0 (j = 2, …, N − 1)  (21)
λ_{1N} + λ_{j1} = 0 (j = 2, …, N − 1)  (22)
λ_{1j} + λ_{jk} + λ_{k1} = 0 j, k ∈ V \ {1, N}  (23)

This shows λ_{ij} = 0 for all arcs ij ∈ I, hence the columns are linearly independent. ⋄

We can also conclude from Lemma 4 that a basis of each column space is given by the columns corresponding to the arc set A \ δ^{+}({v}) as well as A \ δ^{−}({v}) for each node v ∈ V. Let

(F^{1}|F^{2}| … |F^{k}) =: F \underline{k}

denote the matrix formed by the first k column complexes of F^{N,p}. In order to determine the rank of F \underline{k} we recursively calculate the dimension of the intersection of cs(F \underline{k−1}) and cs(F^{k}). We will see that the dimensions of these intersections are always equal for 2 ≤ k ≤ p − 1.

Before we state this constant dimension lemma we state another lemma which we will need for the case N > 2p. But first, let us introduce another bit of notation. With every Hamiltonian p–median (C^{1}, …, C^{p}), we associate its characteristics (|C^{1}|, …, |C^{p}|). Then we can divide the rows of F^{N,p} into \binom{N−p−1}{p−1} different row complexes according to their characteristics. Similarly, we speak about partial characteristics and partial row complexes if the lengths of only some circuits are fixed.

Lemma 5 Let N > 2p. If

dim(cs(F \underline{k}) ∩ cs(F^{l})) ≠ 0

for some 1 ≤ k < l ≤ p − 1, then 1 ∈ F \underline{k}.

Proof. We can assume that p ≥ 3 holds, otherwise nothing has to be shown. If the intersection of the column spaces of F \underline{k} and F^{l} is nontrivial, then the system of equations

∑_{h=1}^{k} ∑_{ij∈A} f_{ij}^{h}λ_{ij}^{h} = ∑_{ij∈A} f_{ij}^{l}μ_{ij}  (24)

has a nontrivial solution. As usual, we select some appropriate equations: Let (C^{1}, …, C^{k}, C^{l}) denote a Hamiltonian (k + 1)–median which can be extended to a Hamiltonian p–median. This simply means that the (k+1)–median contains at most N −2p+2(k+1) nodes. The rows of the system (24) can be labelled by these (k + 1)–medians. The important observation is that the left-hand side of (24) depends only on the circuits in the first k column complexes, whereas the right-hand side depends only on column complex l. We denote the right-hand side of (24) corresponding to circuit C^{l} by w(C^{l}).

Now it suffices to show that, in case of a nontrivial intersection of cs(F \underline{k}) and cs(F^{l}), any two different circuits C^{l} and C^{′l} have the same value w(C^{l}) = w(C^{′l}). This argument shows F \underline{k} ∩ F^{l} = ⟨1⟩ if the intersection is nontrivial. However, this stronger statement is uninteresting since we are going to show that the intersection is actually trivial! In order to prove w(C^{l}) = w(C^{′l}) for any circuits C^{l} and C^{′l}, we need another bit of notation: For a fixed circuit C^{l}, l > k, let

R(C^{l}) := {(C^{1}, …, C^{k}) : (C^{1}, …, C^{k}, …, C^{l}, …, C^{p}) ∈ C_{p}}

denote the set of all Hamiltonian k-medians which can be extended, together with the circuit C^{l}, to a Hamiltonian p–median . Now we distinguish two cases concerning the node sets of C^{l} and C^{′l}. In the first case, let |C^{l}| + |C^{′l}| ≤ N − 2k (by abuse of notation, in this context the set C^{l} is just the vertex set of the circuit C^{l}). It is easy to see that, in this case, R(C^{l}) ∩ R(C^{′l}) ≠ ∅. But this immediately implies w(C^{l}) = w(C^{′l}).

The second case |C^{′l}| + |C^{l}| > N − 2k is more involved. In this situation, |R(C^{l}) ∩ R(C^{′l})| ≥ 1 does not hold any more. Thus we have to apply more sophisticated arguments. We introduce the so–called (undirected) compatibility–graph G_{C} := (V_{C}, A_{C}) on ∑_{k=2}^{N−2(p−1)} \binom{N}{k} vertices where each element in V_{C} corresponds to a circuit. Two vertices (circuits) C^{l}, C^{′l} ∈ V_{C} are joined by an edge if and only if

|R(C^{l}) ∩ R(C^{′l})| ≥ 1.

We will show that this graph is connected (actually, the diameter of G_{C} is three, i.e. any two vertices can be joined by a path of length at most three). The connectivity immediately shows (as above) w(C^{l}) = w(C^{′l}) for all circuits C^{l} and C^{′l}.

In order to show connectivity we must distinguish two cases (note that the case C^{l} ⊆ C^{′l} is trivial):

(A) |C^{l} \ C^{′l}| ≥ 2 or |C^{′l} \ C^{l}| ≥ 2. Let C^{l} and C^{′l} be two circuits with (w.l.o.g.) |C^{l} \C^{′l}| ≥ 2. Let U^{l} be a circuit in C^{l} \C^{′l} with a length of at most N − 2k − |C^{′l}| (best choice is |U^{l}| = 2). We obtain a path of length two by the following two edges:

R(C^{′l}) ∩ R(U^{l}) ≠ ∅ ⟹ w(C^{′l}) = w(U^{l})
R(U^{l}) ∩ R(C^{l}) ≠ ∅ ⟹ w(U^{l}) = w(C^{l}).

(B) |C^{l} \ C^{′l}| = 1 and |C^{′l} \ C^{l}| = 1. In this case, there exist v, w ∈ V such that v, w ∉ C^{l} ∪ C^{′l} (note that |C^{l} ∪ C^{′l}| ≤ N − 2 since there is at least one column complex whose index is not in {1, 2, …, k, l}. Similar to (A) we conclude:

R(C^{l}) ∩ R(C^{′l} \ C^{l} ∪ {v}) ≠ ∅ ⟹ w(C^{l}) = w(C^{′l} \ C^{l} ∪ {v})
R(C^{′l} \ C^{l} ∪ {v}) ∩ R(C^{l} \ C^{′l} ∪ {w}) ≠ ∅ ⟹ w(C^{l} \ C^{′l} ∪ {v}) = w(C^{′l} \ C^{l} ∪ {w})
R(C^{l} \ C^{′l} ∪ {w}) ∩ R(C^{′l}) ≠ ∅ ⟹ w(C^{l} \ C^{′l} ∪ {w}) = w(C^{′l}).
⋄

Now we can prove the “constant dimension lemma”:

Lemma 6 (constant dimension lemma) Let p ≥ 3 and 1 ≤ k ≤ p − 2, k < l ≤ p. Then

(i) dim(cs(F \underline{k}) ∩ cs(F^{l})) = 1 for N = 2p.

(ii) dim(cs(F \underline{k}) ∩ cs(F^{l})) = 0 for N > 2p.

Proof. First, we consider case (i): Adding all the columns of one column complex yields the vector 2 · 1. The reason is simply that each row of a column complex consists of two entries equal to one and all other entries are zeros (since N = 2p). Hence we obtain

1 ∈ cs(F \underline{k}) ∩ cs(F^{l}).

We are now going to show that the all-one-vector 1 and its multiples are the only vectors in the intersection cs(F \underline{k}) ∩ cs(F^{l}) with l > k. In order to do this, we use a little trick that will be used several times in the remainder of this paper.

In each column complex F^{h}, we choose an N(N − 1)/2–dimensional basis B(F^{h}) := \{b_{1}^{h}, …, bh_{\frac{N(N−1)}{2}} \}, which is formed by the columns corresponding to the arc set A_{i<j} :=

{ij ∈ A : 1 ≤ i < j ≤ N}. We can also think of A_{i<j} as the set of undirected arcs. We will use the set of unordered pairs {i, j} as index set for the basis B(F_{h}). Let x be an arbitrary vector in cs(F \underline{k}) ∩ cs(F^{l}). Then there exist

(λ_{1}^{1}, …, λ1_{\frac{(N−1)N}{2}} , λ_{1}^{2}, …, λk_{\frac{(N−1)N}{2}} ) ∈ ℝ^{\frac{kN(N−1)}{2}} and (μ_{1}^{l}, …, μl_{\frac{(N−1)N}{2}} ) ∈ ℝ^{\frac{N(N−1)}{2}}

such that

∑_{h=1}^{k} ∑_{i=1}^{N(N−1)/2} λ_{i}^{h}b_{i}^{h} = x = ∑_{j=1}^{N(N−1)/2} μ_{j}b_{j}^{l}  (25)

holds. Given x, the μ_{j}’s are unique, but not the λ_{i}’s. Now we consider the Hamiltonian p–medians (C^{1}, …, C^{p}) where C^{h} consists of the node pairs {2h−1, 2h} for h = 1, …, k. The circuit C^{l} is defined by the node pair {v, w}, w > v > 2k. Then (25) yields the following linear equations:

λ_{12}^{1} + λ_{34}^{2} + … + λ_{2k−1,2k}^{k} = μ_{vw}^{l} for all (v, w) with 2k < v < w ≤ N.  (26)

We see that the right-hand-side of (26) is independent from the left-hand-side. Therefore, removing the special role of the nodes 1, … k, we obtain the following: For each subset T ⊂ V with |T | = 2k we have μ_{vw}^{l} = μ_{v′w′}^{l} for all v, w, v′, w′ ∈ V \ T, v < w and v′ < w′. In other words: If k < p − 1, the coefficients of the basis representation of x with respect to the basis B(F^{l}) are pairwise equal. This argument shows that μ_{vw}^{l} = μ_{v′w′}^{l} for all v, w, v′, w′ with v < w and v′ < w′. (Note that this reasoning fails for k = p − 1.) But this is equivalent to x ∈ ⟨1⟩ and the statement is proven.

Now we consider the more complicated case N > 2p. Due to Lemma 5 it suffices to show that 1 is not contained in cs(F \underline{k}). In order to show this, we label the columns of F \underline{k} by i = 1, …, N(N − 1)k such that the first N(N − 1) rows are the rows of the first column complex. We put

∑_{i=1}^{N(N−1)k} f_{i}λ_{i} = 1.  (27)

where f_{i} denotes the i-th column of F \underline{k}. We will obtain a contradiction by looking at those rows which have the “partial characteristics” (n_{1}, …, n_{k}) with ∑_{i=1}^{k} n_{i} = 2k and ∑_{i=1}^{k} n_{i} = 2k + 1. In the first case, n_{i} = 2 for i = 1, …, k; the latter case describes all rows where exactly one of the first k circuits has a cardinality of three and the other consist of two nodes.

We are now going to sum all the entries of the vectors on the left-hand side of (27) corresponding to certain “partial” characteristics as well as the corresponding entries on the right-hand side. This will yield a contradiction: The number of rows with a partial characteristics of all two’s (i.e. ∑_{i=1}^{k} n_{i} = 2k) is

∏_{h=0}^{k−1} \binom{N − 2h}{2} = \frac{N!}{(N − 2k)!2^{k}} .  (28)

The sum of these yield

∑_{i=1}^{N(N−1)k} \frac{(N − 2)!}{2^{k−1}(N − 2k)!}λ_{i} = \frac{N!}{(N − 2k)!2^{k}} .  (29)

We put

λ = ∑_{i=1}^{N(N−1)k} λ_{i},

therefore we can write (29)

λ · \frac{(N − 2)!}{2^{k−1}(N − 2k)!} = \frac{N!}{(N − 2k)!2^{k}} .  (30)

Now let (3, 2, 2, …, 2) denote the partial characteristics of a row complex with precisely one entry 3 and all the other entries 2. There are

2\binom{N}{3} ∏_{h=0}^{k−2} \binom{N − 3 − 2h}{2} = \frac{N!}{3 · 2^{k−1}(N − 2k − 1)!}  (31)

different rows of F \underline{k} with characteristics (3, 2, …, 2). Summation yields

∑_{i=1}^{N(N−1)} \frac{(N − 2)!}{2^{k−1}(N − 2k − 1)!}λ_{i} + ∑_{i=N(N−1)+1}^{N(N−1)k} \frac{(N − 2)!}{3 · 2^{k−2}(N − 2k − 1)!}λ_{i} =

= \frac{N!}{3 · 2^{k−1}(N − 2k − 1)!}.  (32)

Iterating this argument for all possible choices of the “exceptional” circuit with 3 nodes and adding the respective k equalities (32), we obtain

∑_{i=1}^{N(N−1)k} (\frac{(N − 2)!}{2^{k−1}(N − 2k − 1)!} + \frac{(k − 1)(N − 2)!}{3 · 2^{k−2}(N − 2k − 1)!}) λ_{i} = \frac{N!k}{3 · 2^{k−1}(N − 2k − 1)!}

or

λ · \frac{(N − 2)!(2k + 1)}{3 · 2^{k−1}(N − 2k − 1)!} = \frac{N!k}{3 · 2^{k−1}(N − 2k − 1)!}.  (33)

It is easy to see that the two equations (30) and (33) cannot be solved simultaneously. This proves (ii). ⋄

Finally, we consider the intersection of cs(F \underline{p−1}) and F^{p}:

Lemma 7 (i) dim(cs(F \underline{p−1}) ∩ cs(F^{p})) = N for N = 2p.

(ii) dim(cs(F \underline{p−1}) ∩ cs(F^{p})) = N − 1 for N > 2p.

Proof. In both cases we will prove the assertion by explicitly constructing a basis of the intersection

cs(F \underline{p−1}) ∩ cs(F^{p}).  (34)

(i) As in the proof of Lemma 6, let B(F^{k}) denote the basis of the column space of F^{k}, k = 1, …, p, induced by the arc set A_{i<j}. We will prove that, for i = 1, …, N, the sum of all columns of F^{p} indexed by the arc set A(δ^{+}({i}) := {ij : j = 1, …, N, j ≠ i} is in the intersection of the two vector spaces in (34). We call this sum sc(i). Note that the components of sc(i) are 1 if i ∈ C^{p} and 0 otherwise. In order to represent sc(i) as a linear combination of the basis of F^{1}, …, F^{p−1}, the following linear system of equations has to be satisfied (here v_{1}, … v_{2p−2} is a set of v_{2p−2} distinct vertices):

λ_{{v_{1}v_{2}}}^{1} + λ_{{v_{3}v_{4}}}^{2} + … + λ_{{v_{2p−3}v_{2p−2}}}^{p−1} = ϵ.  (35)

Here ϵ = 0 if i ∈ {v_{1}, …, v_{2p−2}} and 1 otherwise. As mentioned in Lemma 6, we can think of the arcs v_{i}v_{j} with v_{j} > v_{i} as edges {v_{i}, v_{j}} of the underlying undirected graph. It is not difficult to see that (35) is satisfied by

λ_{\{ij\}}^{k} = −\frac{p − 2}{p − 1}, j = 1, …, N; j ≠ i; k = 1, …, p − 1
λ_{\{jh\}}^{k} = \frac{1}{p − 1}, j, h = 1, …, N; j, h ≠ i; j ≠ i; k = 1, …, p − 1.

Thus, the column sum vectors sc(i) are contained in the columnspace of F \underline{p−1}.

Additionally, we have to show that

(a) the N column sum vectors sc(i), i = 1, …, N are linearly independent,

(b) the vectors sc(i) generate the intersection (34).

To prove (a), we look at the matrix whose columns are sc(1), …, sc(N). The submatrix of it consisting of the rows indexed by the circuits (1, N, 1), (2, N, 2), …, (N −1, N, N −1) and (N − 2, N − 1, N − 2) is

( \begin{matrix}1 & 0 & ⋯ & ⋯ & 0 & 1 \\ 0 & 1 & 0 & ⋯ & ⋮ & 1 \\ ⋮ & 0 & ... & ... & ⋮ & ⋮ \\ ⋮ & ⋮ & ... & ... & ⋮ & ⋮ \\ 0 & ⋯ & ⋯ & 0 & 1 & 1 \\ 0 & ⋯ & ⋯ & 1 & 1 & 0 \end{matrix} )

This matrix obviously has full rank, which proves the linear independence of the sc(i).

In order to prove part (b), we complete sc(1), …, sc(N) to a basis of F^{p} by adding N(N − 3)/2 columns of F^{p}. We can construct such a basis complement by adding the columns indexed by the arc set

I := {1j : 3 ≤ j ≤ N − 1} ∪ {ij : 2 ≤ i < j ≤ N − 1}.

We have to check that the columns f_{ij}^{p} of F^{p} indexed by the arcs in I together with sc(1), …, sc(N) form a basis of the column space generated by F^{p}. Moreover, we have to check

cs(F \underline{p−1}) ∩ cs(F^{p}) = ⟨sc(1), …, sc(N)⟩.

Both assertions follow from

cs(F \underline{p−1}) ∩ ⟨f_{ij}^{p}⟩_{ij∈I} = \{0\}  (36)

which we are now going to prove. But first we note that (36) really implies that the columns of F^{p} indexed by I form a basis complement of sc(1), …, sc(N): We know already that ⟨sc(1), …, sc(N)⟩ ⊆ cs(F \underline{p}), therefore (36) implies

⟨f_{ij}^{p}⟩_{ij∈I} ∩ ⟨sc(1), …, sc(N)⟩ = {0}.

In order to prove (36), we check that the system of linear equations

∑_{h=1}^{p−1} ∑_{1≤i<j≤N} μ_{ij}^{h}f_{ij}^{h} = ∑_{ij∈I} λ_{ij}f_{ij}^{p}

has only the trivial solution: We will show that each of the variables λ_{ij} must be zero. We check this for the variable λ_{3,4}, the other cases are similar or easier. We consider those rows of the system of linear equations where the circuits in the column complexes F^{3}, …, F^{p−1} are fixed. Then we still have six different nodes for the remaining three column complexes F_{1}, F_{2} and F_{p}. Without loss of generality, we can assume that the node set V_{6} = {1, 2, 3, 4, 5, N} still has to be assigned. Since the circuits in the column complexes {3, …, p − 1} are fixed in those rows we are interested in, the entries of the vector

∑_{h=3}^{p−1} ∑_{1≤i<j≤N} μ_{ij}^{h}f_{ij}^{h}

corresponding to these rows must have some constant value c. We obtain the following six equations that have to be satisfied simultaneously:

μ_{34}^{1} + μ_{5N}^{2} + c = 0 (C^{1} = (3, 4, 3), C^{2} = (5, N, 5), C^{p} = (1, 2, 1))
μ_{12}^{1} + μ_{5N}^{2} + c = λ_{34} (C^{1} = (1, 2, 1), C^{2} = (5, N, 5), C^{p} = (3, 4, 3))
μ_{12}^{1} + μ_{45}^{2} + c = 0 (C^{1} = (1, 2, 1), C^{2} = (4, 5, 4), C^{p} = (3, N, 3))
μ_{13}^{1} + μ_{45}^{2} + c = 0 (C^{1} = (1, 3, 1), C^{2} = (4, 5, 4), C^{p} = (2, N, 2))
μ_{13}^{1} + μ_{25}^{2} + c = 0 (C^{1} = (1, 3, 1), C^{2} = (2, 5, 2), C^{p} = (4, N, 4))
μ_{34}^{1} + μ_{25}^{2} + c = 0 (C^{1} = (3, 4, 3), C^{2} = (2, 5, 2), C^{p} = (1, N, 1))

These six equations imply μ_{12} = μ_{13} and μ_{13} = μ_{34}, hence μ_{12} = μ_{34} and λ_{34} = 0.

(ii) The proof resembles the proof of (i). We will also explicitly construct a basis of the intersection of the two vector spaces. For this reason, we look at the N − 1 column sum difference vectors sc(i)−sc(i+1), i = 1, …, N −1 of the p-th column complex. For the definition of the vectors sc(i), see the remarks following (34). Each of these vectors is formed by a linear combination of 2(N − 1) columns of F_{p}. First of all we show that the vectors sc(i) − sc(i + 1), i = 1, …, N − 1 are linearly independent. We arrange the N − 1 vectors in a matrix which has the following (N − 1) × (N − 1) submatrix:

( \begin{matrix}0 & 1 & 0 & ⋯ & ⋯ & 0 \\ 1 & −1 & 1 & 0 & ⋯ & ⋮ \\ 1 & 0 & −1 & 1 & 0 & ⋯ \\ ⋮ & ⋮ & 0 & ... & ... & 0 \\ 1 & 0 & ⋯ & ⋯ & −1 & 1 \\ 1 & 0 & ⋯ & ⋯ & 0 & −1 \end{matrix} ) .

The rows correspond to the N − 1 circuits C^{p} = (1, k, 1) of length 2 (k = 2, …, N). Since this matrix has full rank, the vectors sc(i) − sc(i + 1) are linearly independent.

We will now show that the vectors sc(i) − sc(i + 1) are contained in cs(F \underline{p−1}). Note that sc(i) − sc(i + 1) has just three different entries −1, 1 and 0. An entry 1 means that i is contained in C^{p}, but the node i + 1 is not. If the entry is −1 then there exists an arc (i + 1, j) with j ≠ i in C^{p} but no arc incident with i. An entry 0 means that i and i + 1 are either both contained in C^{p} or none of it. By using this “decoding” you can easily check that the following allocation of scalars to the basis vectors of the first p − 1 column complexes yields a representation of sc(i) − sc(i + 1):

λ_{ij}^{k} = −1 j ≠ i; k = 1, …, p − 1
λ_{(i+1)j}^{k} = 1  j ≠ i + 1; k = 1, …, p − 1
λ_{hj}^{k} = 0  h ≠ i, i + 1; j ≠ h; k = 1, …, p − 1.

Now we choose the (N − 1)(N − 2) columns of F^{p} indexed by the arc set I := {ij : 1 ≤ i, j ≤ N − 1, j ≠ i}. We will show that

∑_{h=1}^{p−1} ∑_{{1≤i≤N−1 \atop j≠i}} μ_{ij}^{h}f_{ij}^{h} = x = ∑_{ij∈I} λ_{ij}f_{ij}^{p}  (37)

is solvable only if x = 0. (Note that the (N − 1)^{2} columns indexed by the arcs {ij : 1 ≤ i ≤ N − 1, j ≠ i} in some column complex form a basis of the column space of this complex). This will show that the (N − 1)(N − 2) column vectors corresponding to the arcs I form a basis complement of the vectors sc(i) − sc(i + 1) in F^{p}. Moreover, the argument implies

⟨sc(i) − sc(i + 1)⟩_{i=1,...,N−1} = cs(F \underline{p−1}) ∩ cs(F^{p}).

For the remainder of the proof we will assume that p ≥ 3 holds, the case 2 is easier. For this purpose, we will successively fix p − 2 of the first p − 1 circuits. We start by fixing circuits C^{2}, …, C^{p−1}. Again, by abuse of notation, we denote the node set of C^{i} also by C^{i}. Let u, v, w, z, N denote 5 distinct elements ∉ ⋃_{i=2}^{p−1} C^{i}. We denote the expression

∑_{h=2}^{p−1} ∑_{{1≤i≤N−1 \atop j≠i}} μ_{ij}^{h}f_{ij}^{h}

of the corresponding partial row complex (C^{2}, …, C^{p−1}) by c. First we will consider only those rows where the circuits C^{1} and C^{p} fulfill

(|C^{1}| = 2, |C^{p}| = 3 or |C^{1}| = 3, |C^{p}| = 2) \underline{and} N ∈ C^{p}

Since all arcs (i, N) and (N, i) are excluded from I, this restriction will shorten the righthand sides of our equations in (37). We obtain the following system of linear equations for our special allocations of C^{1} and C^{p}:

μ_{uv}^{1} + μ_{vu}^{1} + c = λ_{wz}  (38)
μ_{uv}^{1} + μ_{vu}^{1} + c = λ_{zw}  (39)
μ_{uv}^{1} + μ_{vw}^{1} + μ_{wu}^{1} + c = 0  (40)
μ_{uw}^{1} + μ_{wv}^{1} + μ_{vu}^{1} + c = 0.  (41)

The equations (38) and (39) together imply that

λ_{wz} = λ_{zw}  (42)

holds for all w, x ∈ V \ {N}. Adding (40) and (41) yields

μ_{uv}^{1} + μ_{vw}^{1} + μ_{wu}^{1} + μ_{uw}^{1} + μ_{wv}^{1} + μ_{vu}^{1} + 2c = 0 = λ_{wz} + λ_{uz} + λ_{vz} − c.

Consequently,

λ_{wz} + λ_{uz} + λ_{vz} = c  (43)

holds for all feasible allocations of (u, v, w, z). We obtain the following four equations

λ_{wz} + λ_{uz} + λ_{vz} = c  (44)
λ_{uw} + λ_{vw} + λ_{zw} = c  (45)
λ_{uv} + λ_{wv} + λ_{zv} = c  (46)
λ_{zu} + λ_{wu} + λ_{vu} = c.  (47)

In view of (42), we have actually just six different variables. It is not difficult to see that these four equations imply

λ_{ij} + λ_{jk} + λ_{ki} = c

for all circuits (i, j, k, i) of length 3 with i, j, k ∈ {u, v, w, z} and consequently

λ_{uv} = λ_{wz}
λ_{uw} = λ_{vz}
λ_{vw} = λ_{uz}

holds. However, we can repeat this argument with the four nodes {u, v, w, y} instead of {u, v, w, z}. We obtain

λ_{wz} = λ_{uv} = λ_{wy},

therefore λ_{ij} = λ_{kl} for any four not necessarily different nodes i, j, k, l ≠ N. This shows λ_{ij} = c/3 for any i, j ≠ N.

Now we consider the five fixed nodes u, v, w, z, N and the circuits C^{1} and C^{p} with

(|C^{1}| = 2, |C^{p}| = 3 or |C^{1}| = 3, |C^{p}| = 2) \underline{and} N ∈ C^{1}

again. We obtain the following equations by considering the circuits C^{1} = (u, N, u) and C^{′1} = (u, N, v, u):

μ_{uN}^{1} + c = λ_{vw} + λ_{wz} + λ_{zv} = c
μ_{uN}^{1} + μ_{vu}^{1} + c = λ_{wz} + λ_{zw}.

Hence we can conclude that μ_{uN}^{1} = 0 for all u ∈ V \ {N} and μ_{vu}^{1} = −c/3 holds for all u, v ∈ V \ {N}.

If we successively fix (C^{1}, C^{3}, …, C^{p−1}), …, (C^{1}, …, C^{p−2}) and only permute the five nodes on the two circuits C^{k} and C^{p} for k = 2, …, p − 1 we obtain μ_{uN}^{h} = 0 and μ_{uv}^{h} = −c/3 for all u, v ∈ V \ {N} and h = 1, …, p − 1. But then an Hamiltonian p–median with C^{p} = (u, N, u) and the corresponding equation

−(N − 2)c/3 = 0

shows that c/3 = λ_{uv} = 0 holds for all uv ∈ I and the proof is complete. ⋄

Using the previous four lemmata we can easily prove the following dimension theorem:

Theorem 1 Let P^{N,p} denote the Hamiltonian p–median polytope, and let N ≥ 3, N ≥ 2p. Then we obtain the following dimension formula:

dim(P^{N,p}) = \{ \begin{matrix}5 & if & N = 4, p = 2 \\ \frac{pN(N−1)}{2} − N − p + 1 & if & N = 2p, N ≥ 6 \\ p(N − 1)^{2} − N & & otherwise. \end{matrix}  (48)

Proof. In case (N, p) = (4, 2) the result is trivial since all six possible feasible solutions are arc–disjoint, therefore the corresponding incidence vectors are linearly independent. In the second case, there exist exactly \frac{N!}{2^{p}} feasible solutions, as (n_{1}, …, n_{p}) = (2, …, 2) is the only possible p–composition of 2p (each circuit has length 2). We will show that the rank of F^{2p,p} is \frac{pN(N−1)}{2} − N − p + 2 which proves the assertion.

Applying Lemma 4 and iterating Lemma 6 for k = 1, …, p − 1, we obtain by means of the dimension formula for vector spaces

dim(cs(F \underline{p−1})) = (p − 1)dim(cs(F^{1})) − (p − 2) = (p − 1)N(N − 1)/2 − p + 2.

We obtain the stated dimension for N = 2p by applying Lemma 7 and the dimension formula for the intersection of vector spaces, which says:

dim(P^{N,p}) = dim(cs(F \underline{p})) − 1 = = dim(cs(F \underline{p−1})) + dim(cs(F^{p})) − dim(cs(F \underline{p−1}) ∩ cs(F^{p})) − 1 = = (p − 1)N(N − 1)/2 − p + 2 + N(N − 1)/2 − N − 1 =

= \frac{pN(N − 1)}{2} − N − p + 1.

Similarly, we obtain the dimension of the general case N > 2p by analogously applying the above lemmata and the dimension formula for the intersection of vector spaces:

dim(P^{N,p}) = dim(cs(F \underline{p})) − 1 = = dim(cs(F \underline{p−1})) + dim(cs(F^{p})) − dim(cs(F \underline{p−1}) ∩ cs(F^{p})) − 1 =

= (p − 1)(N − 1)^{2} + (N − 1)^{2} − (N − 1) − 1 =
= p(N − 1)^{2} − N.
⋄

We make some remarks concerning this theorem and its rather long proof.

(i) In case N = 2p, we have an overall number of pN(N − 3)/2 + 2p − 1 implicit equations. It turns out that a minimal system of equations for P^{N,p} is given by the linearly independent equations

∑_{k=1}^{p} ∑_{i=1,i≠j}^{N} x_{ij}^{k} = 1 (j = 1, …, N)
x_{ij}^{k} − x_{ji}^{k} = 0 (1 ≤ i < j ≤ N; 1 ≤ k ≤ p)
x^{k}(A) = 2 (k = 1, …, p−1).

(ii) The general case (N ≠ 2p) is easier: We can determine (by selecting p(N − 1) + N linearly independent rows from D, see Lemma 3) a minimal system of equations satisfied by P^{N,p}. Using Lemma 3 we have

AH(P^{N,p}) = {x ∈ ℝ^{N(N−1)p}| x satisfies (4) and (18)}.

(iii) In the general case, the dimension formula can be written in the form

dim(P^{N,p}) = p|A| − (p + 1)|V | + p.

This shows that for p = 1 the formula yields the dimension of the asymmetric travelling salesman polytope (as expected).

(iv) Of course, the results of this section can also be transferred to the symmetrical version of the Hamiltonian p-median. We will not consider this case in detail but summarize the analogous results in the following theorem:

Theorem 2 Let G = (V, E) denote a complete graph on N = |V | vertices. Let

C_{p}^{s} := {(C^{1}, …, C^{p})| C^{i} = (V_{i}, E_{i}) circuit in G, V_{i} ∩ V_{j} = ∅ for i ≠ j, ⋃_{i=1}^{p} V_{i} = V }

denote the set of all feasible symmetrical Hamiltonian p–medians. The symmetrical Hamiltonian p–median polytope S^{N,p} is the convex hull of the incidence vectors of all feasible symmetrical Hamiltonian p-medians. Then the following holds for S^{N,p}:

(i) The symmetrical Hamiltonian p–median polytope consists of

\frac{N!}{2^{p}} ∑_{(n_{1},...,n_{p})∈K_{3}^{N,p}} \frac{1}{∏_{i=1}^{p} n_{i}}

vertices, where

K_{3}^{N,p} := {(n_{1}, …, n_{p})| ∑_{k=1}^{p} = N, n_{k} ≥ 3, k = 1, …, p}.

(ii) The affine hull AH(S^{N,p}) is contained in

{x ∈ ℝ^{N(N−1)p/2}| ∑_{k+1}^{p} ∑_{i≠j^{i=1}}^{N} x_{ij}^{k} = 2 for all j = 1, …, N}.

Moreover, these equations are linearly independent.

(iii)

dim(S^{N,p}) = \{ \begin{matrix}14 & if & N = 6, p = 2 \\ \frac{p·N(N−1)}{2} − N − p + 1 & if & N = 3p, N ≥ 9 \\ \frac{pN(N−1)}{2} − N & & otherwise. \end{matrix}  (49)

Proof. The proofs are similar to the asymmetric case and therefore omitted. ⋄

The next goal is to find classes of facet–defining–inequalities for P^{N,p}. In [11] it was shown that the nonnegativity constraints x_{ij} ≥ 0 define facets of the asymmetric traveling salesman polytope, provided that the number N of nodes is at least 5. The corresponding inequalities are also facet-defining for the Hamiltonian p–median polytope P^{N,p} as the next theorem shows:

Theorem 3 Let p ≥ 1, N ≥ 4 and (N, p) ≠ (4, 1). Then x_{ij}^{k} ≥ 0 define facets of P^{N,p} for all ij ∈ A and k = 1, …, p. Moreover, the number of vertices which are contained in one of these facets

P^{N,p} ∩ {x ∈ ℝ^{N(N−1)p}|x_{ij}^{k} = 0}  (50)

is

(N − 2)! ∑_{(n_{1},...,n_{p})∈K_{2}^{N,p}} \frac{N(N − 1) − n_{k}}{∏_{i=1}^{p} n_{i}} ,

where

K_{2}^{N,p} := {(n_{1}, …, n_{p})| ∑_{k=1}^{p} = N, n_{k} ≥ 2, k = 1, …, p}.

Proof. We will prove the facet–property of the nonnegativity constraints by the direct method, i.e. we will show that there are dim(P^{N,p}) affinely independent incidence vectors of Hamiltonian p–medians which satisfy x_{N−1,N}^{p} = 0 (we may assume (i, j) = (N − 1, N) and k = p without loss of generality). Let T be a matrix whose rows are indexed by the Hamiltonian p–medians. We delete the rows corresponding to p–medians with x_{N−1,N}^{p} = 0 and call this map π. We have to check

dim(rs(π(F^{N,p}))) = dim(rs(F^{N,p})) − 1,

where rs denotes the rowspace of a matrix. We consider, as in the proof of Theorem 1, the trivial case (N, p) = (4, 2) separately: In this situation, the six possible Hamiltonian p-medians are already linearly and consequently affinely independent: There are five affinely independent p–medians satisfying x_{3,4}^{2} = 0.

In the general case, we note that

dim(rs(π(F^{k}))) = dim(rs(F^{k})) for k = 1, …, p − 1

(which is rather obvious) and

dim(rs(π(F^{p}))) = dim(rs(F^{p})) − 1.

To understand the latter equation we will only consider the more difficult case N > 2p. We have to show that the removal of all rows which contain the arc (N − 1, N) in the p-th circuit reduces the dimension of the row space rs(F^{p}) by one. From the proof of Theorem 1 we know that for some fixed node, say node 1, the incidence vectors of all circuits C_{k} := {(1, k, 1) : k = 2, …, N} having cardinality 2 and all circuits C_{jk} := {(1, j, k, 1) : j, k ∈ V \ {1}, j ≠ k} of cardinality 3 form a basis B of the row space of F^{p}. The only basis vector in B not contained in rs(π(F^{p})) is the row indexed by the circuit C_{N−1,N}. Therefore, the dimension loss of one is obvious.

We can now repeat the proof of Theorem 1 basically verbatim for the column spaces cs(π(F^{k})) and cs(π(F \underline{k})) in order to check the dimensions of the intersections

cs(π(F \underline{k})) ∩ cs(π(F^{k})).

It turns out that

dim(cs(π(F \underline{k−1})) ∩ cs(π(F^{k}))) = dim(cs(F \underline{k−1}) ∩ cs(F^{k})) for k = 2, …, p.

This proves that (50) define facets.

To prove the second statement we subtract from the number of all Hamiltonian p–medians (see Lemma 1) the number of those Hamiltonian p–medians where the arc ij is contained in the k-th circuit. This number is given by (see the proof of Lemma 1)

(N − 2)! ∑_{(n_{1},...,n_{p})∈K_{2}^{N,p}} \frac{1}{∏_{{i=1 \atop i≠k}}^{p} n_{i}}

which yields the desired result. ⋄

As for the asymmetric traveling salesman problem one can check that the trivial inequalities x_{ij}^{k} ≤ 1 are not facet-defining because they are implied by the successor and nonnegativity constraints. From Theorem 1 it is clear that the cycle existence constraints (8) cannot be facet–defining since a restriction of a column complex F^{k} to the rows corresponding to circuits of length 2 only yields a column rank of N(N − 1)/2 instead of (N − 1)^{2}. This dimension is too small in order to find pN(N − 2) − N + p linearly independent Hamiltonian p-medians since the dimensions of the other column complexes F^{i} (i ≠ k) are at most (N − 1)^{2}.

It is possible to show that the subtour number constraints (7) (which are of interest only if N ≥ 2p + 2) are not facet–defining for N = 2p + 2. Numerical data indicates that they are also not facet–defining for N > 2p + 2.

4 Conclusions

In this paper we presented a new ILP–formulation for the asymmetric Hamiltonian p– median problem and investigated the basic properties of the associated Hamiltonian p–median polytope. In order to solve “real-world” problems related to the Hamiltonian p-median problem (see [6], for instance), it is necessary to know a lot more about the corresponding polytope than just the dimension. In particular, it is necessary to know facets of the polytope. But of course, to determine facets, i.e. faces of codimension 1, it is necessary to know the dimension of the polytope. Therefore, one can say that this paper (which is, in our opinion, already long enough) is only a first step towards a deeper understanding of the Hamiltonian p-median polytope.

More classes of valid inequalities are investigated in [5]. Parts of these results will be published in a forthcoming paper. In particular, one can show that the linear ordering constraints

∑_{i=2}^{N} ∑_{j=1}^{i−1} x_{ij}^{k} ≥ 1

are facet defining.

In the case p = 1 the asymmetric Hamiltonian p–median problem is equivalent to the asymmetric TSP. It is not clear whether there are relations between the Hamiltonian p–median and the ATSP for p ≥ 2. Further investigations in [5] indicate that for p ≥ 2 there is a closer relationship between the Hamiltonian p–median polytope and the length–restricted circuit polytope which can be derived from P^{N,p} by a projection from ℝ^{N(N−1)p} into ℝ^{N(N−1)} whose kernel consists of p − 1 column complexes.

Moreover, it is not clear whether the asymmetric Hamiltonian p–median can be efficiently transformed into the asymmetric m-TSP by introducing one artificial depot node {0}, see [14]. We think that this is possible only in a more complicated graph– theoretic model based on the line digraph L of D_{N+1} := (V ∪ {0}, A ∪ {(0, v), (v, 0) : v ∈ V }). The line digraph L has (N + 1)N nodes and N^{2}(N + 1) arcs: Each arc of D_{N+1} corresponds to a node of L and two nodes l_{1} and l_{2} are connected by an arc (l_{1}, l_{2}) if the head of the arc corresponding to l_{1} is the tail of the arc associated to l_{2}. If we define the cost function c′ on the arc set A(L) of L by

c′(l_{1}, l_{2}) = \{ \begin{matrix}\frac{c(l_{1})+c(l_{2})}{2} & if & l_{1}, l_{2} ∈ A(L) \\ \frac{c(l_{1})}{2} & if & l_{1} ∈ A(L), l_{2} ∈ δ^{−}(\{0\}) \\ \frac{c(l_{2})}{2} & if & l_{2} ∈ A(L), l_{1} ∈ δ^{+}(\{0\}) \\ c_{vw} & if & l_{1} = (v, 0), l_{2} = (0, w), \end{matrix}

then each Hamiltonian p–median corresponds to a solution of on asymmetric p–TSP on L with fixed depot node {0} and with the same costs. The drawback of this formulation is that we obtain N^{2}(N + 1) = O(N^{3}) variables and cannot operate on a complete digraph anymore since each node of L is only head and tail of exactly N arcs. To use known polyhedral results on the ATSP–polytope we would also have to transform this m–TSP to the standard ATSP, or try to make use of the few polyhedral results on the similarly defined m–cost TSP, see [8].

References

[1] N. Ascheuer, M. Jünger, and G. Reinelt, A branch & cut algorithm for the asymmetric traveling salesman problem with precedence constraints, Comput. Math. Appl., 17 (2000), pp. 61–84.

[2] I. M. Branco and J. D. Coelho, The Hamiltonian p-median problem, Eur. J. Oper. Res., 47 (1990), pp. 86–95.

[3] J. O. Cerdeira, The Hamiltonian k-median problem for any given k is NPcomplete, Tech. Rep. 14, Centro de Estatistica e Aplicaos, 1986.

[4] M. Fischetti and P. Toth, A polyhedral approach to the asymmetric traveling salesman problem, Management Science, 43 (1997), pp. 1520–1536.

[5] H. Glaab, Eine Variante des Travelling Salesman Problems mit mehreren Handlungsreisenden: Modelle, Algorithmen und Anwendungen, PhD thesis, Universität Augsburg, 2000.

[6] H. Glaab, S. Löfflad, and A. Pott, Rundreiseprobleme beim halbautomatischen Lederzuschnitt, in Operations Research Proceedings 1997, P. Kischka, H.-W. Lorenz, U. Derigs, W. Domschke, P. Kleinschmidt, and R. Möhring, eds., Springer, 1998, pp. 86–101.

[7] M. Grötschel, Polyedrische Charakterisierungen kombinatorischer Optimierungsprobleme, vol. 36 of Mathematical Systems in Economics, Verlag Anton Hain, Meisenheim am Glan, 1977.

[8] C. Helmberg, The m-cost ATSP, in Integer programming and combinatorial optimization. 7th International IPCO conference, Graz (Austria), G. Cornuejols, R. E. Burkard, and G. J. Woeginger, eds., vol. 1610 of Lect. Notes Comput. Sci., Berlin, 1999, Springer, pp. 242–258.

[9] M. Jünger, G. Reinelt, and G. Rinaldi, The traveling salesman problem, in Network models, M. O. Ball, T. L. Magnanti, C. L. Manma, and G. L. Nemhauser, eds., vol. 7 of Handbook of Operations Research and Management Science, Amsterdam, 1995, North-Holland, pp. 225–330.

[10] D. Jungnickel, Graphs, networks and algorithms, vol. 5 of Algorithms and Computation in Mathematics, Springer, 1999.

[11] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, eds., The traveling salesman problem. A guided tour of combinatorial optimization, Wiley-Interscience Series in Discrete Mathematics, Wiley, 1985.

[12] S. Löfflad, Eine industrielle Anwendung des Travelling Salesman Problems, Master’s thesis, Universität Augsburg, 1996.

[13] M. Padberg and G. Rinaldi, A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Rev., 33 (1991), pp. 60– 100.

[14] G. Reinelt, The traveling salesman, vol. 840 of Lect. Notes Comput. Sci., Springer, Berlin, 1994.