\documentstyle[12pt]{article}
\oddsidemargin=0in
\textwidth=6.5in
\textheight=23cm
\topmargin=-0.5in
\title{Input Format for Multicommodity Flow Problems}
\author{Kimberly L.~Jones \\ Irvin J.~Lustig \\
Program in Statistics and Operations Research \\ Department of Civil
Engineering and Operations Research \\ Princeton, New Jersey 08544\\
EMAIL:   {\tt irv@basie.princeton.edu}}
\date{November, 1992}
\begin{document}
\maketitle
\section{Introduction}
This document describes a proposed input format for the multicommodity
network flow problem.  This format allows for different definitions
of commodities such as products (apples and oranges), trees
(flow into a destination), or origin-destionation pairs, and reduces
the required storage space by eliminating redundancy.  It is
hoped that this input format becomes the standard among
all researchers studying multicommodity network flows and
encourages the accumulation of data sets for benchmark
purposes.  

Since it is believed that the nature of a commodity can affect
the performance of a solution algorithm, problems can be specified
in a number of different ways.  See Jones~{\sl et al}~\cite{JLFP} for
a discussion of these effects with respect to Dantzig-Wolfe decomposition.


The first section uses some notation to define the different
formulations of multicommodity flow problems.  Traditionally,
it was up to the person formulating the problem to label a commodity
as a product, flow into a destination, or as an origin-destination pair.
The format allows all of these formulations.

\newcommand{\ds}{\displaystyle}
% New definitions to be added
\newcommand{\lcdot}{\cdot}
\newcommand{\Ahat}{\hat{A}}
\newcommand{\Bhat}{\hat{B}}
\newcommand{\Ghat}{\hat{G}}
\newcommand{\Ihat}{\hat{I}}
\newcommand{\Nhat}{\hat{N}}
\newcommand{\Shat}{\hat{S}}
\newcommand{\Xhat}{\hat{X}}
\newcommand{\ahat}{\hat{a}}
\newcommand{\bhat}{\hat{b}}
\newcommand{\chat}{\hat{c}}
\newcommand{\dhat}{\hat{d}}
\newcommand{\ghat}{\hat{g}}
\newcommand{\that}{\hat{t}}
\newcommand{\uhat}{\hat{u}}
\newcommand{\xhat}{\hat{x}}
% Definitions to be replaced
\newcommand{\xbar}{\bar{x}}
\newcommand{\shat}{\hat{s}}   
\newcommand{\dbar}{\bar{d}}
\newcommand{\ctilde}{\tilde{c}}
\newcommand{\dtilde}{\tilde{d}}
\newcommand{\gtilde}{\tilde{g}}
\newcommand{\xtilde}{\tilde{x}}
\newcommand{\That}{\hat{T}}

\newtheorem{assump}{Assumption}
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newcommand{\pref}[1]{(\ref{#1})}

\section{Problem Formulation} \label{notation}

Consider the following linear program:
\begin{equation} \label{lp:gen}
\begin{array}{lll}
    \mbox{\bf (MCNF):} & \mbox{minimize} \qquad 
    \ds{\sum_{\kappa=1}^{\cal K}} (c^\kappa)^T x^\kappa & \\
    \mbox{subject to} & & \\
     & \begin{array}{rcll}
	        B^\kappa x^\kappa & = & d^\kappa
	        & \begin{array}[t]{l}
	              \kappa \in {\cal K}, 
	          \end{array} \\
& & & \\
	        \ds{\sum_{\kappa=1}^{\cal K}} x_{ij}^\kappa & \leq & u_{ij},
	        & \begin{array}[t]{l}
	              \forall (i,j) \in A, 
	          \end{array} \\
& & & \\
	        x_{ij}^\kappa & \geq & 0,
	        & \begin{array}[t]{l}
	              \forall (i,j) \in A, \kappa \in {\cal K}. 
	          \end{array} \\
       \end{array} &
\end{array} 
\end{equation}
The linear program in \pref{lp:gen} is a generic
formulation for a MCNF problem where 
\begin{itemize}
	\item[]
        ${\cal K}$ is the set of commodities;
	\item[]
        $B^\kappa$ is the node-arc incidence matrix over the network
              $G = (N, A)$ for commodity $\kappa$;
	\item[]
        $x^\kappa$ is a vector of arc flows for commodity $\kappa$;
	\item[]
        $d^\kappa$ is a vector of  supply/demand requirements for 
	commodity $\kappa$; and,
	\item[]
        $u_{ij}$ is the upper bound on arc $(i,j)$ over the 
                commodities $\kappa$.
\end{itemize}
The linear program in \pref{lp:gen} displays the typical
block-angular 
structure of a MCNF problem in that
the first set of constraints are the 
network flow conservation constraints for
each commodity and the second set of constraints are 
the mutual capacity, or {\sl bundle} constraints over
the commodities. 
For ease of discussion, only models without individual capacity
constraints on each $x_{ij}^\kappa$ are considered. 

We discuss three formulations of the MCNF problem where in each 
a commodity is defined in a unique way. 
In the first formulation, we define a commodity as a product that 
travels between a specific origin and a
specific destination. This problem is termed the {\em origin-destination
problem} (ODP) where $\kappa$ represents the triplet $(k,s,t)$ such that 
$k$ is the product, $s$ is the specific origin, and $t$ is 
the specific destination.  
The (ODP) is representative of a crew scheduling 
problem, where the identity of a
crew member $k$  must be maintained while satisfying
origin and destination constraints.
In the second formulation,  we define a commodity as a product that travels
to a specific destination from multiple origins, or vice versa, from
a specific origin to multiple destinations.
This problem is termed the {\em destination specific problem} (DSP)
where the commodity $\kappa$ is the pair $(k,t)$ that identifies the
product $k$ with the specific destination $t$.
The (DSP) is typically seen in the
traffic assignment problem, where vehicles $k$ must be routed through
a network from multiple origins to a common destination $t$.
Finally, in the third formulation, we define a commodity as a product that must travel through
a network from multiple origins to multiple destinations.  This problem
is termed the {\em product specific problem} (PSP), where the commodity $\kappa$
represents the singleton $k$ as the product. 
The (PSP) is representative of the multi-fleet allocation
problem where a specific equipment type $k$ must handle a set of transportation
services.  The (PSP) is the formulation that is traditionally indicated
when referring to a MCNF problem.  

Note that the constraint matrix for all three formulations is of the form
\begin{eqnarray} \label{blockform}
\left( 
        \begin{array}{cccc}
         B^1 &   &           &   \\
           & B^2 &           &   \\
           &   & \ddots    &   \\
           &   &           & B^{|{\cal K}|} \\
         I & I & \cdots   & I \\
        \end{array}
\right),
\end{eqnarray}
where
\begin{equation} \label{calK}
{\cal K} = \left\{ \begin{array}{ll}
	\{(k,s,t):d^\kappa = d_{st}^k \ne 0 \} = {\cal K}(ODP) & \mbox{for (ODP)}, \\
	\{(k,t):d^\kappa = d_{t}^k \ne 0 \} = {\cal K}(DSP) & \mbox{for (DSP)}, \\
	\{k:d^\kappa = d^k \ne 0 \} = {\cal K}(PSP) & \mbox{for (PSP)}.
		\end{array}
	\right.
\end{equation}
The differences among the formulations are the number of {\em primary blocks}
$|{\cal K}|$ and the density of the right-hand side vector $d^\kappa$.
The differences in $|{\cal K}|$ are noted in \pref{calK} where the (ODP)
has potentially many more primary blocks than (DSP) and (PSP) due to
the combinatorial aspects of all the products, origins, and destinations
in the problem.  If we assume that the underlying network
is identical for all commodities and identical for each of the three formulations,
then the node-arc incidence matrix $B^\kappa = B$ for all $\kappa \in {\cal K}$.
Hence, the number of constraints in each primary block is the same for each of the three 
formulations, but the number of primary blocks varies according to $|{\cal K}|$.

The right-hand side vector $d^\kappa$ varies significantly among the 
formulations. This is seen by investigating the number of non-zeros in 
each $d^\kappa$ for the three formulations.
For the (ODP) and a given triplet $(k,s,t)$ corresponding to commodity 
$\kappa$, there are only two nonzeros in each $d^\kappa = d_{st}^k$ 
that correspond to the origin $s$ and the destination $t$. 
For the (DSP) and a given pair $(k,t)$ corresponding to commodity $\kappa$, 
each $d^\kappa = d_t^k$ contains multiple nonzeros for the supply
constraints at the multiple origins and a 
single nonzero for the demand constraint at the specific
destination $t$.
Finally, for the (PSP) and a given product $k$ corresponding to
commodity $\kappa$, $d^\kappa = d^k$
contains multiple nonzeros for the supply/demand constraints at the
multiple origins and multiple destinations. 
Hence, the (ODP) has potentially
many more primary blocks than (DSP) or (PSP)
in the linear programming formulation, but $d^\kappa$
is significantly sparser than in the other two formulations.
This is an important concept in the formulation of the MCNF problem and
plays a significant role in a decomposition procedure.

\section {Input Format Overview}

The following input format is proposed.  The data
will be split into 4 sections:  a node file for general
information about the network, a link file,  a supply/demand
file, and a mutual capacity file.   The naming conventions for
a problem with name {\tt xxx} are to name the 4 files
{\tt xxx.nod}, {\tt xxx.arc}, {\tt xxx.sup} and {\tt xxx.mut},
respectively.
Each of these files will be
detailed in this report along with examples as to how it will
be general enough to handle all different types of multicommodity
network flow problems and how it should significantly condense the amount
of redundant information.
\section{Node File \label{node}}
The node file contains four integers  
specified in the following order: {\em number of
products, number of nodes, number of links, and the
number of bundled
links}.  Note that for typical problems of type (DSP) and (ODP), the 
number of products will typically be 1.  In this case, the number
of commodities (either number of destinations or number of origin-destination
pairs) would be inferred from the supply/demand file (See Section~\ref{sup}).
The following example
states that the multicommodity network has 4 products, 48 nodes,
and 150 links, of which  80 are bundled.
\begin{center}
\begin{tabular}{|c|}
\hline Node Input Format \\ \hline \hline
4 \\ \hline
48 \\ \hline
150 \\ \hline
80 \\ \hline
\end{tabular}
\end{center}
\section{Link File \label{link}}
The link file is specified in the following order:
{\em fromnode, tonode, product, cost, individual capacity, origin,
destination, and mutual capacity pointer}.  The mutual capacity pointer
is an integer specifying the instance of the bundled link.  The 
mutual capacity upperbounds are found in the {\em mutual capactiy
file} which is described in section \ref{mut}.
To indicate that the information in a specific column is to be
replicated over all possible values for that column or is not
applicable to the problem, the value of $-1$ is placed in the
column. This will be further explained in the 2 examples below. 

The first example lists the information for 2 links
in a 4 commodity network where a commodity is specified to be a product, such
as apples or oranges.  Since origin-destination pairs are not
applicable to this problem, there is a $-1$ in every instance for
these 2 columns.  The link $1 \rightarrow 47$ is not bundled which
is indicated by a $0$ in the column for mutual capacties.  This
link is duplicated 4 times since the cost on the link is
different for all  commodities. The
second link, $2 \rightarrow 48$, is the first bundled link and has
a cost of $-300$ for all 4 commodities. 

\noindent The second example is an origin-destination specific
problem where a commodity is a specific origin-destination pair.
For this example, a $-1$ is in every instance of the product
column indicating that this information is irrevalent.  However,
if the OD pairs were decomposed from a different type of formulation,
this information might still be relevent and thus the column would
be useful. The link $1 \rightarrow 47$ is a link which is not bundled
and has a cost of $98$ and an individual capacity of $40$ for all OD
pairs.  The link $3 \rightarrow 30$ is not bundled and has a cost
of $20$ for all OD pairs that have a destination of node $47$.  Lastly,
the link $3 \rightarrow 31$ is the first bundled link for this network
and has a cost of $-340$ for all OD pairs that have a destination of
node $48$.

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
\multicolumn{8}{|c|}{\bf Link File Input Format} \\ \hline
\multicolumn{8}{c}{} \\
\hline \multicolumn{8}{|c|}{\bf Product Specific} \\ \hline \hline
& & & & \multicolumn{1}{c|}{Ind} & & &\multicolumn{1}{c|}{Mut} \\ 
\multicolumn{1}{|c|}{From} & \multicolumn{1}{c|}{To}
& \multicolumn{1}{c|}{Prod} & \multicolumn{1}{c|}{Cost}
& \multicolumn{1}{c|}{Cap}
& \multicolumn{1}{c|}{Origin} & \multicolumn{1}{c|}{Dest}
& \multicolumn{1}{c|}{Ptr} \\ \hline \hline
1 & 47 & 1 & 98 & 40 & -1 & -1 & 0 \\ \hline
1 & 47 & 2 & 110 & 50 & -1 & -1 & 0 \\ \hline
1 & 47 & 3& 60 & 46 & -1 & -1 & 0 \\ \hline
1 & 47 & 4 & 45 & 49 & -1 & -1 & 0 \\ \hline
2 & 48 & -1 & -300 & -1 & -1 & -1 & 1 \\ \hline
\multicolumn{8}{c}{} \\
\multicolumn{8}{c}{} \\
\hline
\multicolumn{8}{|c|}{\bf Origin-Destination Specific} \\ \hline \hline
& & & & \multicolumn{1}{c|}{Ind} & & &\multicolumn{1}{c|}{Mut} \\ 
\multicolumn{1}{|c|}{From} & \multicolumn{1}{c|}{To}
& \multicolumn{1}{c|}{Prod} & \multicolumn{1}{c|}{Cost}
& \multicolumn{1}{c|}{Cap}
& \multicolumn{1}{c|}{Origin} & \multicolumn{1}{c|}{Dest}
& \multicolumn{1}{c|}{Ptr} \\ \hline \hline
1 & 47 & -1 & 98 & 40 & -1 & -1 & 0 \\ \hline
3 & 30 & -1 & 20 & -1 & -1 & 47 & 0 \\ \hline
3 & 31 & -1 & -340 & -1 & -1 & 48 & 1 \\ \hline
\end{tabular}
\end{center}
\section{Supply/Demand File \label{sup}}
The supply/demand file is specified in the following order:
{\em origin, destination, product, and flow}. 
This type of input format is able to handle whether the
commodities are apples
and oranges (products), flow into a destination or out of
an origin (trees), or origin-destination pairs (paths). 
For the cases where commodities are products or trees, 
the placement of a -1 in the origin or destination column
indicates whether a node is a supply or demand node. 
The usual way of indicating a demand is to place
a negative value in the flow column.  However, if we
require all values in the flow column to be positive,
a -1 in the
origin column will indicate that it is a demand.  This enables
us to always expect positive elements in the final column,
as would be the case if it were an origin-destination
problem. A -1 in the product column has the same meaning
as in the arc file: to duplicate over all possible values or
the information is not applicable.
In the case of the (ODP) formulation,
when both the origin and destination columns have positive
elements, there may be a -1 in the product column indicating
that this is not relevant information.  But if there is
a positive element, it may mean that the OD pair is also
tagged by a product or tree commodity. 

The following examples below show how the supply/demand
file for all three definitions of a commodity can be used
in an identical format.
First, we give the example of a 2 commodity (product)
network with 2 supply nodes and 2 demand nodes.
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline \multicolumn{4}{|c|}{Supply/Demand Input File for Product Formulation} 
\\ \hline \hline
Origin & Destination & Product & Flow \\ \hline \hline
1 & -1 & 1 & 25 \\ \hline
1 & -1 & 2 & 50 \\ \hline
2 & -1 & 1 & 15 \\ \hline
2 & -1 & 2 & 30 \\ \hline
-1 & 3 & 1 & 15 \\ \hline
-1 & 3 & 2 & 60 \\ \hline
-1 & 4 & 1 & 25 \\ \hline
-1 & 4 & 2 & 20 \\ \hline
\end{tabular}
\end{center}

The next example is that for the tree formulation where a commodity
is flow into a destination.  This example has is a 2 commodity
network with 2 destinations.
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline \multicolumn{4}{|c|}{Supply/Demand Input File for Tree Formulation} 
\\ \hline \hline
Origin & Destination & Product & Flow \\ \hline \hline
1 & -1 & 1 & 25 \\ \hline
2 & -1 & 1 & 15 \\ \hline
3 & -1 & 1 & 10 \\ \hline
-1 & 5 & 1 & 50 \\ \hline
1 & -1 & 2 & 10 \\ \hline
2 & -1 & 2 & 30 \\ \hline
3 & -1 & 2 & 10 \\ \hline
-1 & 6 & 2 & 50 \\ \hline
\end{tabular}
\end{center}

The final example is for an 6 commodity OD formulation, 
where the product
column is not applicable so a -1 is present
in every instance of that column. 
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline \multicolumn{4}{|c|}{Supply/Demand Input File for OD Formulation} 
\\ \hline \hline
Origin & Destination & Product & Flow \\ \hline \hline
1 & 5 & -1 & 25 \\ \hline
2 & 5 & -1 & 15 \\ \hline
3 & 5 & -1 & 10 \\ \hline
1 & 6 & -1 & 50 \\ \hline
2 & 6 & -1 & 40 \\ \hline
3 & 6 & -1 & 10 \\ \hline
\end{tabular}
\end{center}

\section{Mutual Capacity File \label{mut}}
The file for the mutual capacities contain 2 columns in the
following order:  {\em mutual capacity pointer, and upper bound}.  The
pointer values are listed in sequential order from $1$ to
the number of bundled links in the network.  These bundled
links are referenced from the links file, as outlined in
section \ref{link}.  Below is an example of a mutual capacity
file that has 5 bundled links.
\begin{center}
\begin{tabular}{|c|c|}
\hline
\multicolumn{2}{|c|}{\bf Mutual Capacity Input Format}
\\ \hline \hline
\multicolumn{1}{|c|}{Pointer} & \multicolumn{1}{c|}{Bound} \\ 
\hline \hline
1 & 200 \\ \hline
2 & 159 \\ \hline
3 & 249 \\ \hline
4 & 100 \\ \hline
5 & 218 \\ \hline
\end{tabular}
\end{center}
\begin{thebibliography}{99}
\bibitem{JLFP} {\sc K.~L. Jones, I.~J. Lustig, J.~M. Farvolden, and 
W.~B. Powell}, {\em Multicommodity network flows: The impact of formulation
on decomposition}, Tech. Rep. SOR 91-23, Princeton University, Department
of Civil Engineering and Operations Research, Princeton, NJ, 1991.
\end{thebibliography}
\end{document}

