\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}