%% A LateX file for a 26 page document
\documentclass[12pt]{article}
\textwidth 6.2in
\textheight 8.5in
\topmargin 0pt
\oddsidemargin 0in
\evensidemargin 0in
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics \textbf{7} (2000), \#R42\hfill}
\thispagestyle{empty}
\usepackage{amsfonts}
\newtheorem{Theo}{Theorem}
\newtheorem{Lem}{Lemma}
\newtheorem{Cor}{Corollary}
\newcommand{\xfd}{x_{ij}^k+x_{i\bar{j}}^k+x_{\bar{i}j}^k+x_{\bar{i}\bar{j}}^k}
\newcommand{\HpM}{Hamiltonian $p$--median }
\begin{document}
\begin{titlepage}
\title{\bf The Hamiltonian p--median problem
\thanks{Both authors thank the German Ministry for education and science for
supporting this project under the name {\it Combinatorial optimization
problems in the leather industry}. The content of this paper forms
part of the first author's doctoral thesis.}}
\author{Holger Glaab\\
Institute for Mathematics\\
University of Augsburg\\
86135 Augsburg\\
{\small\texttt{glaab@math.uni-augsburg.de}}
\and
Alexander Pott\\
Institute for Algebra and Geometry\\
University of Magdeburg\\
39016 Magdeburg\\
{\small\texttt{alexander.pott@mathematik.uni-magdeburg.de}}
}
\date{Submitted: February 16, 1999; Accepted: April 25, 2000}
\end{titlepage}
\maketitle
\begin{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.
\end{abstract}
\section{Introduction}
In the last decade, the class of so--called {\em 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 {\em 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 {\em Hamiltonian p--median
problem (HpMP)}. This problem has been introduced by Branco and Coelho
\cite{BC}. The investigation is motivated
by a practical application, the so--called laser multi--scanner problem (LMSP),
see \cite{GLP} and \cite{Loe},
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.
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 \cite{JRR} or \cite{PR} for the symmetric TSP,
\cite{FT} for the asymmetric TSP and \cite{AJR} 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\mapsto {\mathbb R} \]
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,\ldots$ 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
{\it 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
\[ {\cal C}_p:=\{(C^1,\ldots,C^p)|\:C^i=(V_i,A_i)\:\mbox{circuit in}\: D,\, V_i\cap V_j=\emptyset
\mbox{\ for }i\neq j,\,\bigcup\limits_{i=1}^p V_i=V\}\]
denote the set of all {\it Hamiltonian p--medians}.
% Alternatively, the
% Hamiltonian $p$--median problem can be viewed as a special variant of
% an assignment problem, where each feasible solution must consist of
% exactly $p$ connectivity components.
As most interesting
combinatorial optimization problems, the HpMP has been proven to be
NP-complete \cite{Ce}.
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 {\cite{BC}} and which induces a polyhedral description of
the problem. The formulation in \cite{BC} 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.
\section{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 \cite{BC}. 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 \cite{BC}. We have
two classes of binary variables: The variable $y_{i}^k\in\{0,1\}$ with
$\{i,k\}\in V\times\{1,\ldots,p\}$ indicates whether node $i$ belongs
to the Hamiltonian circuit $C^k$ or not. A second class of variables
$x_{ij}^k\in\{0,1\}$ with $\{i,j,k\}\in {V\times
V\times\{1,\ldots,p\}}$ is $1$ if and only if node $i$ precedes node
$j$ in circuit $C^k$:
\begin{equation}\label{inz_vek}x_{ij}^k=\left\{\begin{array}{c@{\quad:\quad}c}
1 & ij\in{C^k}\\ 0 & ij\not\in{C^k}.\end{array}\right.
\end{equation}
Then the existence of more than $p$ circuits is
prevented by the constraints\\
\[ \sum\limits_{i,j\in S}x_{ij}^k\le|S|-1
\]
for all $S\subset R_k:=\{i:y_{i}^k=1\}$ with $|S|\ge 1$ and
$k=1,\ldots,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 $p$-median 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 ({\it integer linear
programming}) formulation lies in the description of the partition of
$V$ into $p$ disjoint subtours. Therefore, we introduce the term of
{\it $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.
\begin{equation}\label{2}
P_m:=\{(S_1,\ldots,S_m):\:S_i\subset V\:,S_i\cap S_j=\emptyset\mbox{\ for }i\neq
j ,\:\bigcup\limits_{i=1}^m V_i=V\}.
\end{equation}
Moreover, for each element $(S_1,\ldots,S_m)\in P_m$ let
\begin{equation}
A(S_1,\ldots,S_m):=\{ij\in A:i\in S_k,j\in S_l,1\le k2p$.
It suffices to consider $F^1$.
Let $Z^1\subset (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
\[\sum\limits_i x_{ij}=\sum\limits_k x_{jk} \]
for all nodes $j=1,\ldots,N$, we have
\[ \langle Z^1\rangle\subset \{x\in{\mathbb R}^{N(N-1)}:\sum\limits_i x_{ij}=\sum\limits_k x_{jk},
\ j=1,\ldots,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 \cite{Ju}).
In our case, $z=1$. Thus we obtain
\[ dim(cs(F^1))\le N(N-1)-N+1=(N-1)^2 \]
where {\it 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\in A:1\le i\le N-1,j\neq i\}=A\setminus\delta^+(\{N\}).\]
Note that $\delta^+(\{i\})$, resp. $\delta^-(\{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,\ldots,N\}$ of cardinality $2$ and the
$(N-1)(N-2)$ circuits
$C_{jk}:=\{(1,j,k,1):j,k\in V\setminus\{1\},j\neq k\}$. To prove the linear independence
of the columns indexed by $I$,
we look at the system of linear equations
$$\sum\limits_{ij\in I}\lambda_{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}$:
\begin{eqnarray}
\lambda_{1j}+\lambda_{j1} & = & 0\quad(j=2,\ldots,N-1)\label{pairs}\\
\lambda_{1N} & =& 0 \label{sing}\\
\lambda_{1j}+\lambda_{jN} & = & 0\quad (j=2,\ldots,N-1)\label{spair2}\\
\lambda_{1N}+\lambda_{j1} & = & 0\quad(j=2,\ldots,N-1)\label{spair1}\\
\lambda_{1j}+\lambda_{jk}+\lambda_{k1} & = & 0\quad j,k\in V\setminus\{1,N\}\label{trip}
\end{eqnarray}
This shows $\lambda_{ij}=0$ for all arcs $ij\in I$, hence the columns are linearly
independent.
\hfill$\diamond$ \\
We can also conclude from Lemma~\ref{dim_scc} that a basis of each
column space is given by the columns corresponding to the arc set $A\setminus\delta^+(\{v\})$
as well as $A\setminus\delta^-(\{v\})$ for each node $v\in V$.
Let
\[ (F^1|F^2|\ldots|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\le k\le p-1$.
Before we state this {\it 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,\ldots,C^p)$, we
associate its {\it characteristics} $(|C^1|,\ldots,|C^p|)$. Then
we can divide the rows of $F^{N,p}$
into ${N-p-1 \choose p-1}$ different {\it row complexes} according to
their characteristics. Similarly, we speak about
{\it partial characteristics} and {\it partial row complexes} if the lengths of
only some circuits are fixed.
\begin{Lem}
\label{nt_int}
Let $N> 2p$.
If
\[dim(cs(F^{\underline{k}})\cap cs(F^{l}))\neq 0 \]
for some $1\le kk$, let
\[ R(C^l):=\{(C^1,\ldots,C^k):\ (C^1,\ldots,C^k,\ldots,C^l,\ldots,C^p)\in {\cal C}_p\}\]
denote the set of all Hamiltonian $k$-medians which can be extended,
together with the circuit $C^l$, to
a \HpM. Now we distinguish two cases concerning the node sets of $C^l$ and $C'^l$.
In the first case, let $|C^l|+|C'^l|\le 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)\cap R(C'^l)\neq\emptyset$.
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)\cap R(C'^l)|\ge 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
$\sum_{k=2}^{N-2(p-1)}{N\choose k}$
vertices where each element in $V_C$ corresponds to a circuit. Two vertices (circuits)
$C^l,C'^l\in V_C$
are joined by an edge if and only if
\[|R(C^l)\cap R(C'^l)|\geq 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\subseteq C'^l$ is trivial):\\
\noindent {\bf (A)}\quad$|C^l\setminus C'^l|\ge 2$ or $|C'^l\setminus C^l|\ge 2$.\\
Let $C^l$ and $C'^l$ be two circuits with (w.l.o.g.) $|C^l\setminus C'^l|\ge 2$.
Let $U^l$ be a circuit in $C^l\setminus 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:
\begin{eqnarray*}
R(C'^l)\cap R(U^l)\neq\emptyset &\Longrightarrow & w(C'^l)=w(U^l) \\
R(U^l)\cap R(C^l)\neq\emptyset &\Longrightarrow & w(U^l)=w(C^l).
\end{eqnarray*}
\noindent{\bf (B)}\quad$|C^l\setminus C'^l|=1$ and $|C'^l\setminus C^l|=1$.\\
In this case, there exist $v,w\in V$ such that $v,w\not\in C^l\cup C'^l$
(note that $|C^l\cup C'^l|\leq N-2$ since there is at least one column
complex whose index is not in $\{1,2,\ldots, k, l\}$.
Similar to ({\bf A}) we conclude:
\begin{eqnarray*}
R(C^l)\cap R(C'^l\setminus C^l\cup\{v\})\neq\emptyset &\Longrightarrow & w(C^l)=w(C'^l\setminus C^l\cup\{v\}) \\
R(C'^l\setminus C^l\cup\{v\})\cap R(C^l\setminus C'^l\cup\{w\})\neq\emptyset &\Longrightarrow & w(C^l\setminus C'^l\cup\{v\})=w(C'^l\setminus C^l\cup\{w\})\\
R(C^l\setminus C'^l\cup\{w\})\cap R(C'^l)\neq\emptyset &\Longrightarrow & w(C^l\setminus C'^l\cup\{w\})=w(C'^l).
\end{eqnarray*}\hfill $\diamond$
Now we can prove the ``constant dimension lemma'':
\begin{Lem}[constant dimension lemma]
\label{consdim}
Let $p\ge 3$ and $1\le k\le p-2,k2p$.
\end{enumerate}
\end{Lem}
\noindent{\bf Proof}. First, we consider case (i):
Adding all the columns of one column complex yields the
vector $2\cdot {\bf 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
\[ {\bf 1}\in cs(F^{\underline{k}})\cap cs(F^l).\]
We are now going to show that the all-one-vector ${\bf 1}$ and its
multiples are the only vectors in the intersection
$cs(F^{\underline{k}})\cap 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,\ldots,b_{\frac{N(N-1)}{2}}^h\}$, which is formed by the columns
corresponding to the arc set $A_{iv>2k$. Then (\ref{isc}) yields the following linear equations:
\begin{equation}
\label{eqs}
\lambda_{12}^1+\lambda_{34}^2+\ldots+\lambda_{2k-1,2k}^k=\mu_{vw}^l\quad
\mbox{for all } (v,w)\mbox{\ with }2k2p$.
Due to Lemma~\ref{nt_int} it suffices to show that ${\bf 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,\ldots, N(N-1)k$ such that the first $N(N-1)$ rows
are the rows of the first column complex. We put
\begin{equation}\label{nonex}
\sum_{i=1}^{N(N-1)k} f_i\lambda_i={\bf 1}.
\end{equation}
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,\ldots,n_k)$ with
$\sum_{i=1}^k n_i=2k$ and $\sum_{i=1}^k n_i=2k+1$.
In the first case, $n_i=2$ for $i=1,\ldots, 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
(\ref{nonex}) 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.
$\sum_{i=1}^k n_i=2k$) is
\begin{equation}
\label{alltwo}
\prod\limits_{h=0}^{k-1}{N-2h \choose 2}=\frac{N!}{(N-2k)!2^k}\ .
\end{equation}
The sum of these yield
\begin{equation}
\label{alltwoeq}
\sum\limits_{i=1}^{N(N-1)k}\frac{(N-2)!}{2^{k-1}(N-2k)!}\lambda_i=\frac{N!}{(N-2k)!2^k}\ .
\end{equation}
We put
$$
\lambda=\sum_{i=1}^{N(N-1)k}\lambda_i,
$$
therefore we can write (\ref{alltwoeq})
\begin{equation}
\label{alltwoeq*}
\lambda\cdot \frac{(N-2)!}{2^{k-1}(N-2k)!} = \frac{N!}{(N-2k)!2^k}\ .
\end{equation}
Now let $(3,2,2,\ldots,2)$ denote the partial characteristics of a
row complex with precisely one entry $3$ and all the other entries $2$.
There are
\begin{equation}
\label{onethr}
2{N\choose 3}\prod_{h=0}^{k-2}{N-3-2h\choose 2}=\frac{N!}{3\cdot 2^{k-1}(N-2k-1)!}
\end{equation}
different rows of $F^{\underline{k}}$ with characteristics
$(3,2,\ldots,2)$. Summation yields
\begin{eqnarray}
\label{onethreq}
\sum\limits_{i=1}^{N(N-1)}\frac{(N-2)!}{2^{k-1}(N-2k-1)!}\lambda_i+
\sum\limits_{i=N(N-1)+1}^{N(N-1)k}\frac{(N-2)!}{3\cdot 2^{k-2}(N-2k-1)!}\lambda_i= & & \nonumber \\
= \frac{N!}{3\cdot 2^{k-1}(N-2k-1)!}. & &
\end{eqnarray}
Iterating this argument for all possible choices of the ``exceptional" circuit
with $3$ nodes and
adding the respective $k$ equalities (\ref{onethreq}), we obtain
\begin{displaymath}
\sum\limits_{i=1}^{N(N-1)k}\left(\frac{(N-2)!}{2^{k-1}(N-2k-1)!}
+\frac{(k-1)(N-2)!}{3\cdot 2^{k-2}(N-2k-1)!}\right)\lambda_i
= \frac{N!k}{3\cdot 2^{k-1}(N-2k-1)!}
\end{displaymath}
or
\begin{equation}
\label{sonethreq*}
\lambda\cdot\frac{(N-2)!(2k+1)}{3\cdot 2^{k-1}(N-2k-1)!}
= \frac{N!k}{3\cdot 2^{k-1}(N-2k-1)!}.
\end{equation}
It is easy to see that the two equations (\ref{alltwoeq*}) and
(\ref{sonethreq*}) cannot be solved simultaneously. This proves (ii).\hfill$\diamond$ \\
Finally, we consider the intersection of
$cs(F^{\underline{p-1}})$ and $F^p$:
\begin{Lem}
\label{exc_dim}
\begin{enumerate}
\item[(i)] $\qquad dim(cs(F^{\underline{p-1}})\cap cs(F^p))=N\mbox{\ for } N=2p.$
\item[(ii)] $\qquad dim(cs(F^{\underline{p-1}})\cap cs(F^p))=N-1\mbox{\ for } N>2p$.
\end{enumerate}
\end{Lem}
\noindent{\bf Proof}. In both cases we will prove the assertion by explicitly constructing
a basis of the intersection
\begin{equation}
\label{ast}
cs(F^{\underline{p-1}})\cap cs(F^p).
\end{equation}
(i) As in the proof of Lemma~\ref{consdim}, let $B(F^k)$ denote the basis
of the column space of $F^k$, $k=1,\ldots,p$, induced by the arc set $A_{iv_i$ as edges $\{v_i,v_j\}$ of the underlying undirected graph.
It is not difficult to see that (\ref{iseq})
is satisfied by
\begin{eqnarray*}
\lambda_{\{ij\}}^k &=& -\frac{p-2}{p-1}, \quad j=1,\ldots,N;\ j\neq i;\ k=1,\ldots,p-1\\
\lambda_{\{jh\}}^k & = &\frac{1}{p-1}, \quad j,h=1,\ldots,N;\ j,h\neq i;\ j\neq i;\
k=1,\ldots,p-1.
\end{eqnarray*}
Thus, the column sum vectors $sc(i)$ are contained in the columnspace of $F^{\underline{p-1}}$.\\
\noindent Additionally, we have to show that
\begin{itemize}
\item[(a)] the $N$ column sum vectors $sc(i),i=1,\ldots,N$ are linearly independent,
\item[(b)] the vectors $sc(i)$ generate the intersection (\ref{ast}).
\end{itemize}
To prove (a), we look at the matrix whose columns are $sc(1),\ldots,sc(N)$.
The submatrix of it consisting of the rows indexed by the circuits
$(1,N,1), (2,N,2),\ldots,(N-1,N,N-1)$ and $(N-2,N-1,N-2)$ is
\[\left(\begin{array}{llccrr}
1 & 0 & \cdots & \cdots & 0 & 1\\
0 & 1 & 0 & \cdots & \vdots & 1\\
\vdots & 0 & \ddots & \ddots & \vdots & \vdots \\
\vdots & \vdots & \ddots & \ddots & \vdots & \vdots\\
0 & \cdots & \cdots & 0 & 1 & 1\\
0 & \cdots & \cdots & 1 & 1 & 0\\
\end{array}\right)\]
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),\ldots,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\le j\le N-1\}\cup\{ij:2\le i < j\le 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),\ldots,sc(N)$ form a basis of the
column space generated by $F^p$. Moreover, we have to check
$$
cs(F^{\underline{p-1}})\cap cs(F^p)=\langle sc(1),\ldots,sc(N) \rangle .
$$
Both assertions follow from
\begin{equation}\label{inter}
cs(F^{\underline{p-1}})\cap \langle f_{ij}^p \rangle_{ij\in I}=\{\bf{0}\}
\end{equation}
which we are now going to prove. But first we note that
(\ref{inter}) really implies that the columns of $F^p$ indexed by
$I$ form a basis complement of $sc(1),\ldots,sc(N)$: We know already
that $\langle sc(1),\ldots,sc(N) \rangle \subseteq cs(F^{\underline{p}})$,
therefore (\ref{inter}) implies
$$
\langle f_{ij}^p \rangle_{ij\in I} \cap \langle sc(1),\ldots,sc(N) \rangle
= \{\bf{0}\}.
$$
In order to prove (\ref{inter}), we check that
the system of linear equations
\[ \sum\limits_{h=1}^{p-1}\sum\limits_{1\le i2p$ by analogously
applying the above lemmata and the dimension formula for the intersection of vector spaces:
\begin{eqnarray*}
\lefteqn{dim({\cal 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}}) \cap cs(F^{p}))-1= \\
& & = (p-1)(N-1)^2+(N-1)^2-(N-1)-1 = \\
& & =p(N-1)^2-N.
\end{eqnarray*}
\hfill $\diamond$\\
We make some remarks concerning this theorem and its rather long proof.
\begin{enumerate}
\item[(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
${\cal P}^{N,p}$ is given by the linearly independent equations
\begin{eqnarray*}
\sum\limits_{k=1}^p \sum\limits_{i=1,i\neq j}^N x_{ij}^k& = &1 \quad (j=1,\ldots,N)\\[1mm]
x_{ij}^k-x_{ji}^k & = & 0 \quad (1\le i2p$.
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,\ldots,N\}$ having cardinality 2 and all circuits
$C_{jk}:=\{(1,j,k,1):j,k\in V\setminus\{1\},j\neq 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(\pi(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(\pi(F^{k}))$ and $cs(\pi(F^{\underline{k}}))$
in order to check the dimensions of the intersections $$cs(\pi(F^{\underline{k}}))
\cap cs(\pi(F^k)).$$ It turns out that
$$
dim(cs(\pi(F^{\underline{k-1}}))\cap
cs(\pi(F^k)))=dim(cs(F^{\underline{k-1}})\cap cs(F^k)) \quad\mbox{for }k=2,\ldots, p.
$$
This proves that (\ref{fac}) define facets.
To prove the second statement we subtract from the number of all
Hamiltonian\break
$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)!\sum\limits_{(n_1,\ldots,n_p)\in K^{N,p}_2}
\frac{1}{\prod\limits_{i=1\atop i\neq k}^p n_i}\]
which yields the desired result.
\hfill $\diamond$\\
As for the asymmetric traveling salesman problem one can check that
the trivial inequalities $x_{ij}^k\le 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 (\ref{cec}) 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\neq k$) are
at most $(N-1)^2$.
It is possible to show that the subtour number constraints (\ref{ssec}) (which are
of interest only if $N\geq 2p+2$) are not facet--defining for $N=2p+2$.
Numerical data indicates that they are also not facet--defining for $N>2p+2$.
\section{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 \HpM polytope.
In order to solve ``real-world'' problems related to the Hamiltonian
$p$-median problem (see \cite{GLP}, 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 \cite{GlPo2}. Parts of these
results will be published in a forthcoming paper. In particular, one can show that the
linear ordering constraints
$$
\sum_{i=2}^N\sum_{j=1}^{i-1} x_{ij}^k \geq 1
$$
are facet defining.
In the case $p=1$ the asymmetric \HpM problem is equivalent to the asymmetric TSP.
It is not clear whether there are relations between the \HpM and the ATSP
for $p\ge 2$. Further investigations in \cite{GlPo2}
indicate that for $p\ge 2$ there is a closer relationship
between the \HpM polytope and the length--restricted circuit polytope which can be derived
from ${\cal P}^{N,p}$ by a projection from ${\mathbb R}^{N(N-1)p}$ into ${\mathbb R}^{N(N-1)}$
whose kernel consists of $p-1$ column complexes.
Moreover, it is not clear whether the asymmetric \HpM can be efficiently transformed into the
asymmetric $m$-TSP by introducing one artificial
depot node $\{0\}$, see \cite{Rei}. 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\cup\{0\},A\cup\{(0,v),(v,0):v\in 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)=\left\{\begin{array}{ccc}
\frac{c(l_1)+c(l_2)}{2} & \mbox{if} & l_1,l_2\in A(L)\\[0.2cm]
\frac{c(l_1)}{2} & \mbox{if} & l_1\in A(L),l_2\in\delta^-(\{0\})\\[0.2cm]
\frac{c(l_2)}{2} & \mbox{if} & l_2\in A(L),l_1\in\delta^+(\{0\})\\[0.2cm]
c_{vw} & \mbox{if} & l_1=(v,0),l_2=(0,w),
\end{array}\right.\]
then each \HpM 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 \cite{Hel}.
\begin{thebibliography}{10}
\bibitem{AJR}
{\sc N.~Ascheuer, M.~J\"unger, and G.~Reinelt}, {\em A branch \& cut algorithm
for the asymmetric traveling salesman problem with precedence constraints},
Comput.~Math.~Appl., 17 (2000), pp.~61--84.
\bibitem{BC}
{\sc I.~M. Branco and J.~D. Coelho}, {\em The {H}amiltonian $p$-median
problem}, Eur.~J.~Oper.~Res., 47 (1990), pp.~86--95.
\bibitem{Ce}
{\sc J.~O. Cerdeira}, {\em The {H}amiltonian $k$-median problem for any given
$k$ is {NP}-complete}, Tech. Rep.~14, Centro de Estatistica e Aplicaos, 1986.
\bibitem{FT}
{\sc M.~Fischetti and P.~Toth}, {\em A polyhedral approach to the asymmetric
traveling salesman problem}, Management Science, 43 (1997), pp.~1520--1536.
\bibitem{GlPo2}
{\sc H.~Glaab}, {\em Eine {V}ariante des {T}ravelling {S}alesman {P}roblems mit
mehreren {H}andlungsreisenden: {M}odelle, {A}lgorithmen und {A}nwendungen},
PhD thesis, Universit\"at Augsburg, 2000.
\bibitem{GLP}
{\sc H.~Glaab, S.~L\"offlad, and A.~Pott}, {\em Rundreiseprobleme beim
halb\-automatischen {L}ederzuschnitt}, in Operations Research Proceedings
1997, P.~Kischka, H.-W. Lorenz, U.~Derigs, W.~Domschke, P.~Kleinschmidt, and
R.~M\"ohring, eds., Springer, 1998, pp.~86--101.
\bibitem{Groe}
{\sc M.~Gr\"otschel}, {\em Polyedrische Charakterisierungen kombinatorischer
Optimierungsprobleme}, vol.~36 of Mathematical Systems in Economics, Verlag
Anton Hain, Meisenheim am Glan, 1977.
\bibitem{Hel}
{\sc C.~Helmberg}, {\em 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.
\bibitem{JRR}
{\sc M.~J\"unger, G.~Reinelt, and G.~Rinaldi}, {\em 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.
\bibitem{Ju}
{\sc D.~Jungnickel}, {\em Graphs, networks and algorithms}, vol.~5 of
Algorithms and Computation in Mathematics, Springer, 1999.
\bibitem{LLRS}
{\sc E.~L. Lawler, J.~K. Lenstra, A.~H.~G. {Rinnooy Kan}, and D.~B. Shmoys},
eds., {\em The traveling salesman problem. A guided tour of combinatorial
optimization}, Wiley-Interscience Series in Discrete Mathematics, Wiley,
1985.
\bibitem{Loe}
{\sc S.~L\"offlad}, {\em Eine industrielle {A}nwendung des {T}ravelling
{S}alesman {P}roblems},\break Master's thesis, Universit\"at Augsburg, 1996.
\bibitem{PR}
{\sc M.~Padberg and G.~Rinaldi}, {\em A branch-and-cut algorithm for the
resolution of large-scale symmetric traveling salesman problems}, SIAM Rev.,
33 (1991), pp.~60--100.
\bibitem{Rei}
{\sc G.~Reinelt}, {\em The traveling salesman}, vol.~840 of Lect. Notes Comput.
Sci., Springer, Berlin, 1994.
\end{thebibliography}
\end{document}