# NAG CL Interfaceh03abc (transportation)

## 1Purpose

h03abc solves the classical transportation (‘Hitchcock’) problem.

## 2Specification

 #include
 void h03abc (const double cost[], Integer tdcost, const double avail[], Integer navail, const double req[], Integer nreq, Integer maxit, Integer *numit, double optq[], Integer source[], Integer dest[], double *optcost, double unitcost[], NagError *fail)
The function may be called by the names: h03abc, nag_mip_transportation or nag_transport.

## 3Description

h03abc solves the transportation problem by minimizing
 $z = ∑ i m a ∑ j m b c ij x ij .$
subject to the constraints
 $∑ j m b x ij = A i availabilities ∑ i m a x ij = B j requirements$
where the ${x}_{\mathit{i}\mathit{j}}$ can be interpreted as quantities of goods sent from source $\mathit{i}$ to destination $\mathit{j}$, for $\mathit{i}=1,2,\dots ,{m}_{a}$ and $\mathit{j}=1,2,\dots ,{m}_{b}$, at a cost of ${c}_{ij}$ per unit, and it is assumed that ${\sum }_{i}^{{m}_{a}}{A}_{i}={\sum }_{j}^{{m}_{b}}{B}_{j}$ and ${x}_{ij}\ge 0$.
h03abc uses the ‘stepping stone’ method, modified to accept degenerate cases.

## 5Arguments

1: $\mathbf{cost}\left[{\mathbf{navail}}×{\mathbf{tdcost}}\right]$const double Input
On entry: ${\mathbf{cost}}\left[\left(\mathit{i}-1\right)×{\mathbf{tdcost}}+\mathit{j}-1\right]$ contains the coefficients ${c}_{\mathit{i}\mathit{j}}$, for $\mathit{i}=1,2,\dots ,{m}_{a}$ and $\mathit{j}=1,2,\dots ,{m}_{b}$.
2: $\mathbf{tdcost}$Integer Input
On entry: the stride separating matrix column elements in the array cost.
Constraint: ${\mathbf{tdcost}}\ge {\mathbf{nreq}}$.
3: $\mathbf{avail}\left[{\mathbf{navail}}\right]$const double Input
On entry: ${\mathbf{avail}}\left[\mathit{i}-1\right]$ must be set to the availabilities ${A}_{\mathit{i}}$, for $\mathit{i}=1,2,\dots ,{m}_{a}$;
On entry: the number of sources, ${m}_{a}$.
Constraint: ${\mathbf{navail}}\ge 1$.
5: $\mathbf{req}\left[{\mathbf{nreq}}\right]$const double Input
On entry: ${\mathbf{req}}\left[\mathit{j}-1\right]$ must be set to the requirements ${B}_{\mathit{j}}$, for $\mathit{j}=1,2,\dots ,{m}_{b}$.
6: $\mathbf{nreq}$Integer Input
On entry: the number of destinations, ${m}_{b}$.
Constraint: ${\mathbf{nreq}}\ge 1$.
7: $\mathbf{maxit}$Integer Input
On entry: the maximum number of iterations allowed.
Constraint: ${\mathbf{maxit}}\ge 1$.
8: $\mathbf{numit}$Integer * Output
On exit: the number of iterations performed.
9: $\mathbf{optq}\left[{\mathbf{navail}}+{\mathbf{nreq}}\right]$double Output
On exit: ${\mathbf{optq}}\left[\mathit{k}-1\right]$, for $\mathit{k}=1,2,\dots ,{m}_{a}+{m}_{b}-1$, contains the optimal quantities ${x}_{ij}$ which, when sent from source $i={\mathbf{source}}\left[k-1\right]$ to destination $j={\mathbf{dest}}\left[k-1\right]$, minimize $z$.
10: $\mathbf{source}\left[{\mathbf{navail}}+{\mathbf{nreq}}\right]$Integer Output
On exit: ${\mathbf{source}}\left[\mathit{k}-1\right]$, for $\mathit{k}=1,2,\dots ,{m}_{a}+{m}_{b}-1$, contains the source indices of the optimal solution (see optq above).
11: $\mathbf{dest}\left[{\mathbf{navail}}+{\mathbf{nreq}}\right]$Integer Output
On exit: ${\mathbf{dest}}\left[\mathit{k}-1\right]$, for $\mathit{k}=1,2,\dots ,{m}_{a}+{m}_{b}-1$, contains the destination indices of the optimal solution (see optq above).
12: $\mathbf{optcost}$double * Output
On exit: the value of the minimized total cost.
13: $\mathbf{unitcost}\left[{\mathbf{navail}}+{\mathbf{nreq}}\right]$double Output
On exit: ${\mathbf{unitcost}}\left[\mathit{k}-1\right]$, for $\mathit{k}=1,2,\dots ,{m}_{a}+{m}_{b}-1$, contains the unit cost ${c}_{ij}$ associated with the route from source $i={\mathbf{source}}\left[k-1\right]$ to destination $j={\mathbf{dest}}\left[k-1\right]$.
14: $\mathbf{fail}$NagError * Input/Output
The NAG error argument (see Section 7 in the Introduction to the NAG Library CL Interface).

## 6Error Indicators and Warnings

NE_2_INT_ARG_LT
On entry, ${\mathbf{tdcost}}=〈\mathit{\text{value}}〉$ while ${\mathbf{nreq}}=〈\mathit{\text{value}}〉$. These arguments must satisfy ${\mathbf{tdcost}}\ge {\mathbf{nreq}}$.
NE_ALLOC_FAIL
Dynamic memory allocation failed.
NE_INT_ARG_LT
On entry, ${\mathbf{maxit}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{maxit}}\ge 1$.
On entry, ${\mathbf{navail}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{navail}}\ge 1$.
On entry, ${\mathbf{nreq}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{nreq}}\ge 1$.
NE_REQ_AVAIL
The relative difference between the sum of availabilities and the sum of requirements is greater than machine precision. relative difference $\text{}=〈\mathit{\text{value}}〉$, .
NE_TOO_MANY
Too many iterations ($〈\mathit{\text{value}}〉$)

## 7Accuracy

The computations are stable.

## 8Parallelism and Performance

h03abc is not threaded in any implementation.

An a priori estimate of the run time for a particular problem is difficult to obtain.

## 10Example

A company has three warehouses and three stores. The warehouses have a surplus of 12 units of a given commodity divided between them as follows:
 Warehouse Surplus 1 1 2 5 3 6
The stores altogether need 12 units of commodity, with the following requirements:
 Store Requirement 1 4 2 4 3 4
Costs of shipping one unit of the commodity from warehouse $i$ to store $j$ are displayed in the following matrix:
 Store 1 2 3 1 8 8 11 Warehouse 2 5 8 14 3 4 3 10
It is required to find the units of commodity to be moved from the warehouses to the stores, such that the transportation costs are minimized. The maximum number of iterations allowed is 200.

### 10.1Program Text

Program Text (h03abce.c)

None.

### 10.3Program Results

Program Results (h03abce.r)