\documentstyle[11pt]{article}
\setlength{\topmargin}{-.5in}
\addtolength{\textheight}{1.5in}
\addtolength{\textwidth}{\evensidemargin}
\addtolength{\textwidth}{\oddsidemargin}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\addtolength{\textwidth}{-1.0\oddsidemargin}
\addtolength{\textwidth}{-1.0\evensidemargin}
\begin{document}
\setlength{\baselineskip}{14pt}

\title{\Large The First DIMACS International \\
Algorithm Implementation Challenge: \\ The Core Experiments}
\author{}
\date{{\small \today}}
\maketitle

\section{Introduction} 
The final phase of the First DIMACS Implementation Challenge begins.
Participants are invited to perform a set of ``core'' experiments
described in this document and to report their results at the DIMACS
Workshop to be held in October 1991.

We expect that much more extensive and thorough experiments have been
carried out during the Spring and Summer of 1991, and we encourage
Challenge participants to investigate a variety of experimental
problem areas.  The projects listed below should represent only a part
of the total experimental study for each participant.  Indeed, there
is {\em no requirement} that the core experiments be carried out at
all; we request that participants do so in order to maximize the
comparability of experimental results.  Participants are of course
invited to extend or augment the set of core tasks as desired.

\section{The Challenge Workshop} 

DIMACS will sponsor a three-day workshop beginning October 15th 1991
for Challenge participants to meet and discuss their experimental
results.  The workshop will be organized into sessions, each centered
around a particular problem class.  Each session will include: an
introductory survey talk; presentations of experimental results by
Challenge participants; and a panel discussion to evaluate the results
and to discuss future goals.  Additional sessions will be scheduled
for informal competition among the participants, using local Sun
systems and/or remote facilities.

The number of slots available for research presentations is limited.
Participants are invited to submit 10-page extended abstracts
describing the experimental study and the (perhaps preliminary)
results, by August, 13th 1991.  Speaker slots will be awarded based
upon evaluation of the abstracts.

Each abstract should thoroughly describe the experimental methodology
and research questions addressed in the project, discuss the most
interesting experimental results so far, and sketch the problems to be
addressed in the future.  It is not necessary that all planned
experiments be completed by August 13th; a summary of partial or
preliminary results is acceptable for the abstract as long as there is
some indication that significant work has been done.

Before the start of the workshop, all abstracts for a given session
will be sent to session participants and to the presenter of the
survey talk.  The abstracts, introductory surveys, transcripts of the
panel discussions, and a directory of contributed programs available
from DIMACS, will be collected and published as workshop proceedings.
Best Paper awards will be presented based upon the quality of the
experimental work and the significance of experimental results as
presented in the abstracts.  In addition, workshop participants are
invited to submit full papers for a refereed volume to be published at
a later date.

We expect to be able to provide at least partial travel and lodging
support to all Challenge participants who need it; priority will be
given to those invited to make presentations and to graduate students.
Participants from other countries can receive support for lodging and
for travel {\em within} the United States.

Important Challenge and Workshop dates are listed below.

\vspace{.2in} 

\begin{tabular}{ll}\hline 
August 13 & Workshop submission deadline for extended abstracts. \\
August 31 & Announcement of session presenters and workshop schedule.
\\ October 14-15-16 & DIMACS Challenge Workshop at Rutgers
University.\\ January 15, 1992 & Submission deadline for full papers.
\\ \hline
\end{tabular}

\section{The Experiments}

This section describes the basic experiments to be carried out by
Challenge participants.  Later sections describe problem-specific
details and give further guidelines.  We begin with some general
definitions and conventions for program testing.

\begin{itemize} 
\item Throughout this document, the {\bf problem size} refers to $n$, the 
number of vertices in the network (or graph) for a given input class.

\item The {\bf running time} is defined as the CPU time taken 
by the program to find an to report a single integer solution (such as
total flow cost or total matching weight) for a given input instance.

The total solution time---including time to input and to output a full
solution---is also of interest, but this should be a reported
separately.  If the program accepts an input format that is different
from the DIMACS format, it is not necessary to report the time
required for translation.

For implementations on parallel architectures, the {\bf parallel
speedup} should also be reported: how does running time improve as the
number of processors increases?

\item Strive to produce a {\bf fair test} of each program being
studied.  Any program can be fine-tuned to give improved performance
for a restricted class of inputs; many programs have input parameters
to allow users to make adjustments based upon {\em a priori} knowledge
of input structure.  Is it more ``fair'' to compare implementations
using untuned code or using the best-known strategy for each?

This is of course a difficult question in general.  For the purposes
of the DIMACS Challenge, any technique or strategy for tuning a
program is acceptable in a fair test {\em as long as the use of that
technique could (in theory) be automated.} That is, the implementor
must able to write down the ``rules'' for applying the technique
clearly enough that a decision routine (or a reader unfamiliar with
program details) could replicate the strategy and produce identical
test results based on easily-computed properties of the input
instance.

Note that some of the questions below may be more easily answered if
program parameters are left unchanged throughout a run of experiments.

\end{itemize} 

\subsection{Experiments using Random Inputs} 

The network generators and input families available from DIMACS are
described later in the problem-specific sections.  Each {\em input
family} corresponds to an input property that may have a significant
effect on program performance.  Each family includes a small number of
{\em input classes} which have specific parameter settings.  Read the
guidelines and select {\em at least one input family} for testing in
your home environment.

It is expected that the following tasks will be performed for each
input class and each program being tested.

\paragraph{Designing the Experiment.} 
\begin{enumerate} 
\item  A particular input class together with a specific problem size
represents a {\em sample point}.  Determine the number of random {\em
trials} (each with a different random seed) that are required to
obtain a good estimate of mean running time at each sample point.

A simple evaluation procedure is outlined below; participants are
welcome to apply more sophisticated analyses.
\begin{enumerate}  %sample point 
\item  For a given input class and a moderately large problem size, 
set $t=10$.  Find the mean CPU time over $t$ random trials (each with
a different random number seed).  Do this 4 times to obtain 4 means
(using $4t$ independent trials).

\item  If the 4 means vary from one another by less than 
10 percent, then $t$ is probably adequate.  If there is large
variation among the 4 values, then $t$ should be increased. In
general, variance in the means is proportional to $1/t$.

\item An alternative test is to compare 4 means at the given
problem size to 4 means with the problem size doubled.  Find a $t$
such that variation {\em between} the two sets of numbers is
significantly larger than variation {\em within} each set.

\item Iterate the above steps until a satisfactory value for 
$t$ is found.
\end{enumerate} %sample point 

\item  Considering $t$ and properties of the input class 
(such as network density), determine the largest problem size
$n_{max}$ that can be tested.  Suggested lower bounds for the smallest
problem size $n_{min}$ are given in the problem-specific sections.

Choose $k$ values of $n$ within the range $n_{min} \ldots n_{max}$,
where $k$ is between 4 and 10.  The values should be powers of 2: for
example, $2^{10}, 2^{12}, \ldots 2^{20}$.  Fractional powers are also
acceptable, rounded to the nearest integer when necessary.  For
example $2^{10}=1024, 2^{10.5}=1448, 2^{11}=2048$.  (If $n_{max} \leq
50 n_{min}$, choose values evenly spaced within their range.)
\end{enumerate} 

\paragraph{Testing the Programs and Reporting the Results.} 

Some references which give guidelines for performing computational
experiments, analyzing functional relationships and distributional
properties, and reporting the results, are listed below.
\begin{description}

\item Box, Hunter, and Hunter, {\em Statistics for Experimenters,} 
Wiley and Sons 1978.

\item Chambers, Cleveland, Kleiner, and Tukey, {\em Graphical Methods
for Data Analysis}, Wadsworth International Group/Duxbury Press,
Boston, 1983.

\item Crowder, Dembo, and Mulvey, ``Reporting computational experiments
in Mathematical Programming,'' {\em Mathematical Programming} 15
(1978), pp 316--329.

\item H. Greenberg, ``Computational testing: why, how, and how much,''
ORSA Journal of Computing 2 (1990), pp 94--97.

\item J. Tukey, {\em Exploratory Data Analysis}, Addison-Wesley 1977. 

\end{description} 

The following topics should be addressed when reporting the results of
the core experiments.
\begin{enumerate} 
\item  Measure program running time for each input class: this will 
require $tk$ executions of each program.  Report the mean running time
for each program at each sample point.

Some generators will (with low probability) produce non-feasible
inputs. If the program detects and reports an infeasible input, that
trial should not be included in the tallying of average solution time:
generate extra instances to obtain $t$ random trials.

\item  Find a {\em functional} relationship between
mean running time and problem size.  The easiest way to do this is to
use a data-analysis package available on your local system.  Much can
be done without sophisticated tools, however: some simple procedures
which require minimal computational aids are listed below. Let $x$
denote the problem size and let $y$ denote the mean running time.
\begin{itemize}

\item {\bf Growth Analysis.}  What happens to $y$ as $x$ doubles?  
If $y$ doubles, then $y$ is growing linearly with $x$. If $y$
quadruples each time, then $y$ is growing as the square of $x$.

\item {\bf The Power Law.} 
Take the (base-2) logarithm of both $x$ and $y$, and plot the
transformed data.  If the points are approximately linear, find the
slope, $m$, of a line through the points.  Growth in (the original)
$y$ is proportional to $x^{m}$.  If the points are not linear, use
this technique to find powers of $x$ which ``bracket'' growth in $y$.

\item {\bf Checking Residuals.}  Guess a functional fit to the data, 
say $y' = x \log x$.  Subtract each function value $y'$ from the
observed value $y$ and plot the differences (the residuals) against
$x$.  If the residuals are curving upwards, then the functional guess
is too low: try again with (say) $y' = x (\log x)^2$.  If the
residuals now form a line with slope $m$, try $y' = x (\log x)^2 +
mx$.  Stop when the residuals are horizontal and near zero.

\item See the references cited above for more advanced 
methods for analyzing functional relationships in data.
\end{itemize}

\item  Identify the most important combinatorial quantities in 
the implementation---the ones which are the best predictors of program
running time.  Find a functional relationship between problem size and
these combinatorial quantities.

For our purposes, a ``combinatorial quantity'' is any component of the
program that can be counted: calls to procedures, main loop
iterations, number of heap-insertions, number of preflow-pushes, et
cetera.

Finding the desired functional relationship may be quite difficult.
At the very least, characterize which program elements tend to
dominate the running time as problem size increases.  For example, is
the running time dominated by data-structure updates?  For parallel
implementations, is there a communication bottleneck that becomes
increasingly significant?  Suppose Procedure X tends to dominate the
running time as $n$ grows: is this because the number of procedure
calls increases, because the time spent in each call increases, or a
combination of both?

\item  Select at least 2 sample points 
from among the total set (perhaps a large and a medium-sized problem)
for detailed study of factors other than the mean.  For each sample
point, describe the range and distribution of running times.

For example, what are the worst and best running times, the median
running time, and the quartiles?  (The median splits the data in half;
the quartiles split each half in half.)  Are the times symmetric
around their mean, or do points trail off toward the high end?  Is the
data bimodal?  Do outliers (unusually large or small running times)
appear?  What input properties are associated with unusually large
running times?

\end{enumerate} %reporting 

\subsection{A Machine Calibration Experiment.}

A directory containing programs, input instances, and instructions for
their use, is available from DIMACS through anonymous ftp (or from a
netlib server---See the Challenge General Information document for
instructions on obtaining files from DIMACS). The pathname of the
directory is {\bf pub/netflow/benchmarks}.

Compile and run the programs them in your local environment(s) using
the input instances provided.

\begin{enumerate}
\item  Report the {\em total} running time---from input to 
output---required on your local system to run each program using each
input instance.

\item  How much variation in running time can you observe 
across runs with identical input instances?

For example, how much does reported running time vary in subsequent
runs using the same inputs?  How much does running time depend upon
the time of day or the number of users on the system?  How much
variation can be observed from changes in factors such as compiler
version or optimization level?
\end{enumerate} 

The results of this test will be collected for a comparative study of
the diverse programming environments used by Challenge participants
and of sources of variation in runtime experiments.

\subsection{Tests On Real Problems.}

Time will be allocated at the workshop for informal competitions in
which participants will solve problem instances from real
applications.  Workshop participants should plan to bring along their
hardest instances and their fastest codes for testing on DIMACS
machines (Sun SPARCstations---those with Telnet capabilities can run
their tests remotely).

One component of this competition will be to assess how useful
randomly-generated input classes are in predicting program performance
on real instances.

\section{How to Find Files and Programs.} 

Random instance generators and related programs are available from
{\bf dimacs.rutgers.edu} via anonymous ftp or through the netlib
server.  (See the General Information document for further information
on obtaining files from DIMACS.)  They are located in the directory
{\bf pub/netflow/generators},

Some of the generators require a collection of related files to
operate; look at the {\bf readme} file in each subdirectory for
further documentation and instructions on using the programs.

\subsection{System Compatibility}

The programs listed in this document are all executable on SUN Unix
systems.  The Pascal programs provided by Gary Waissi are also
available in Turbo versions.  

It may be necessary to make small modifications to achieve
compilability on other systems.  In particular, the calls to system
random number generators will probably need to be replaced with
locally-compatible system calls.  Some participants may prefer to use
{\bf universal.c}, which contains a stand-alone random
generator that produces integers uniformly distributed within the
range $[0, 10^9]$.  This generator has the remarkable property of
being completely portable: for a given seed it will produce an
identical sequence of integers on any architecture that can represent
30-bit integers, regardless of the internal integer representation,
maximum word size, or other machine-dependent factors.

\subsection{The Instance Generators}

The generators and related programs named in this document are listed
below along with the path names of their home directories.

Note that more generators are available than are mentioned here, and
that some of the named generators have more options than are
described.  The file {\bf pub/netflow/recursive.ls} contains a
recursive listing, updated weekly, of all directories pertaining to
the DIMACS Challenge.  See the {\bf readme} file in a particular
subdirectory for further documentation.

\begin{tabular}{ll} \hline 
ac-max.p & pub/netflow/generators/network/waissi \\ asnmat.a &
pub/netflow/generators/matching \\ asnmin.a & pub/netflow/generators
\\ assign.c & pub/netflow/generators \\ dcube.c &
pub/netflow/generators/matching \\ fractals.c &
pub/netflow/generators/matching/fractals \\ genrmf.c &
pub/netflow/generators/network/genrmf \\ maxmin.a &
pub/netflow/generators \\ mesh.c & pub/netflow/generators/network/mesh
\\ neighbor.c & pub/netflow/generators/matching \\ netgen.c &
pub/netflow/generators/netgen \\ netgen.f &
pub/netflow/generators/netgen/fortran \\ ra-max.p &
pub/netflow/generators/network/waissi \\ random.c &
pub/netflow/generators/matching \\ tr2-max.p &
pub/netflow/generators/network/waissi \\ universal.c &
pub/netflow/generators \\ washington.c &
pub/netflow/generators/network/washington \\ \hline
\end{tabular} 

\section{Maximum Flows}

Input instances for maximum flow algorithms run on on sequential
architectures should have at least $n_{min} = 256 = 2^{8} $ vertices.
On parallel architectures the instances should have at least $n_{min}
= 1024 = 2^{10}$ vertices.

\subsection{The Network-Width Family.}

Each network in this family has a ``length'' parameter which
corresponds roughly to the length of paths from the source to the
sink, and a ``width'' parameter which corresponds to the number of
paths across a cut separating the source from the sink.  The input
classes represent a range of length/width ratios.  Other factors such
as network structure, density, and capacity ranges remain fixed.  Four
input classes for this family are defined; two are wide and two
are long.  

\paragraph{ } 

Use {\bf washington.c} with {\bf function}$=2$ to obtain a Random
Leveled Graph.  This network has vertices arranged in {\bf arg1} rows
and {\bf arg2} columns.  Each vertex in column $i$ has exactly three
arcs to randomly-chosen vertices in the next column.  Set the maximum
arc capacity to {\bf arg3}$=10^4$.

Networks generated by {\bf genrmf.c} have vertices in {\bf b}
grid-like frames, each of size {\bf a}$\times${\bf a}.  The source
node is in a corner of the first frame, and the sink node is in a
corner of the last frame.  Each vertex is connected to its grid
neighbors within the frame, and to one vertex randomly chosen from the
next frame.  There are about $6n$ arcs in the network. 
Arc capacities within a frame are {\bf c2}$\times${\bf
a}$\times${\bf a}.  Capacities for arcs between frames are chosen
uniformly from the range [{\bf c1}, {\bf c2}]. Set {\bf c1}$=1$ and
{\bf c2}$=10^4$.  

\begin{itemize}   
\item {\bf Washington-RLG-Wide}. 
To generate a wide network with $n = 2^x$ vertices, set {\bf
arg1}$=2^{x-6}$ and {\bf arg2}$=64$.  For these networks, width grows
with problem size and length is fixed at 64.

\item {\bf Washington-RLG-Long.}  To generate a long network with $n=2^x$ 
vertices, set {\bf arg1}$=64$ and {\bf arg2}$=2^{x-6}$.  Here width is
fixed at 64 and length grows with problem size.

\item {\bf Genrmf-Long.} 
To produce a network with $n= 2^{x}$ vertices, let $y = x/4$, and set
{\bf a} $= 2^{y}$ and {\bf b}$ = 2^{2y}$.  These networks are twice as
long as they are wide.

\item {\bf Genrmf-Wide.}  To produce a network with $n=2^x$ vertices, 
let $y = x/5$, and set {\bf a}$ = 2^{2y}$ and {\bf b}$ = 2^{y}$.
These networks are twice as wide as they are long.
\end{itemize} 

\subsection{The Network Density Family} 

The networks in this family represent variations in network density.
There are 5 input classes: two are sparse, two are moderately dense,
and one is very dense.  All of these networks are acyclic.

\paragraph{ } 
Use {\bf washington.c} with {\bf function}$=5$ to generate a Square
Mesh.  Vertices in this network form a square grid with {\bf arg1}
vertices on a side.  To generate a network with $n=2^x$ vertices, set
{\bf arg1}$=2^{x/2}$.  Each 
vertex has {\bf arg2} arcs to (fixed, not random) vertices in the next
column.  The maximum arc capacity is determined by {\bf arg3}: set
{\bf arg3}$=10^6$.

Use {\bf washington.c} with {\bf function}$=6$ to generate a Basic
Line Network.  Vertices are numbered 1 through ({\bf arg1}$\times${\bf
arg2}).  The vertex degree is specified by {\bf arg3}.  Each vertex
$i$ has arcs to vertices chosen randomly from the range $[i+1, i+({\bf
arg2}\cdot {\bf arg3})]$.  Maximum arc capacity is set internally at
$10^6$.

Use {\bf ac-max.p} generate a dense acyclic network.  This
network is similar to Washington-Line, but the generator is much more
efficient for dense networks.  Vertex $i$ has an arc to every vertex
numbered $i+1$ through $n$.

\begin{itemize} 
\item {\bf Washington-Square-Sparse.} 
Set {\bf arg2}$=4$.  Every vertex has arcs to 4 vertices in the next
column.

\item{\bf Washington-Square-Moderate.} To generate a moderately-dense 
network set {\bf arg2}$ equal to ${\bf arg1/4}.  Each vertex in 
column $i$ has $\sqrt{n}/4$ arcs to vertices in column $i+1$.

\item {\bf Washington-Line-Sparse.}  To generate a problem of size
$n = 2^x$, set {\bf arg1}$=2^{x-2}$ and {\bf arg2}$=4$.  Set {\bf
arg3}$=4$.  Every vertex $i$ has 4 arcs to vertices chosen randomly
from $[i+1, i+16]$.

\item {\bf Washington-Line-Moderate.}  To generate a problem of
size $n = 2^x$, set {\bf arg1}$=2^{x-2}$ and {\bf arg2}=$4$.  Set {\bf
arg3}$=2^{(x/2) - 2} = \sqrt{n}/4$.  Every vertex has $\sqrt{n}/4$
arcs to vertices chosen randomly from $[i+1, i+\sqrt{n}]$.

\item {\bf Acyclic-Dense.}  
Use {\bf ac-max.p} with the options Fully Dense (type {\bf f} at the
prompt) and Random Capacities (type {\bf n} when asked about special
capacities).  Set the maximum capacity to $10^6$.
\end{itemize}
 
\subsection{The Capacity-Scale Family.} 
 
Networks in this family represent variations in the maximum number of
bits required to specify capacity.  Four input classes are given: two
use a small number of bits and two use a large number of bits.

\paragraph{ }

Use generator {\bf tr2-max.p} to produce networks with vertices in a
square grid (with an extra partial column if $n$ is not a square
number).  Every vertex has an arc to its grid neighbors. 

Use {\bf washington.c} with {\bf function}$=3$ to generate a Random
2-Leveled Graph.  Vertices in this graph are arranged in a grid with
{\bf arg1} rows and {\bf arg2} columns.  Each vertex in column $i$ has
exactly three arcs to vertices chosen randomly from columns $i+1$ and
$i+2$.  To generate a problem of size $n=2^{x}$, take $y=x/2$ and set
{\bf arg1}$= 2^y$ and {\bf arg2}$=2^y$.

\begin{itemize} 
\item {\bf Transit2-Lo-Cap}.  At the prompt, set the maximum
capacity to 100.

\item {\bf Transit2-Hi-Cap}. At the prompt, set the maximum 
capacity to $10^8$.

\item {\bf Washington-RLG2-Lo-Cap}. Set the maximum arc 
capacity {\bf arg3} to 100.

\item {\bf Washington-RLG2-Hi-Cap}. Set the maximum arc capacity 
{\bf arg3} to $10^8$.
\end{itemize} 

\section{The Assignment Problem}

This section describes input families for programs which solve the
assignment problem.  For implementations on sequential machines, the
smallest problem size tested should be at least $n_{min} = 2^8 = 256$.
For parallel machines, the smallest problem size should be at least
$n_{min} = 1024 = 2^{10}$.

\paragraph{ } 
All of the input families use the same instance generator, {\bf
assign.c}, to generate bipartite networks for the assignment problem.
The following command keywords are accepted on standard input.

\vspace{.2in} 
\begin{tabular}{ll} \hline
{\bf nodes x} & Specifies x nodes in the network. \\ {\bf sources x} &
Specifies that y of the nodes are supply nodes. \\ {\bf maxcost x} &
Upper bound on arc costs (uniformly distributed). \\ {\bf complete} &
Specifies a complete bipartite graph with an arc from \\ & each supply
node to each demand node. \\ {\bf degree x} & Node degree for each
supply node (can't be used together \\ & with {\bf complete}). \\ {\bf
seed x} & (optional) Gives a random number seed. \\ \hline
\end{tabular} 

\subsection{The Supply/Demand Ratio Family} 

Networks in this family vary in the ratio of the number of supply
nodes to the number of demand nodes in the network.  The vertex degree
is held constant across the range of input classes.  For each instance
class below set {\bf maxcost}$=10^5$ and {\bf degree}$=n/16$.

\begin{itemize}
\item {\bf Assign-Lo-Supply.}  For a network with $n$ vertices, 
set {\bf sources}$=n/8$.

\item {\bf Assign-Eq-Supply.} For a network with $n$ vertices let 
{\bf sources}$=n/2$.

\item {\bf Assign-Hi-Supply.}  For a network with $n$ vertices,
set {\bf sources}$=7n/8$.

\end{itemize} 

\subsection{The Cost Scale Family.}

Networks in this family vary in the number of bits required to specify
maximum arc cost.  To generate a network of $n$ vertices, set {\bf
sources}$=n/2$ and {\bf degree}$=n/4$.

\begin{itemize}
\item {\bf Assign-Lo-Cost.} Set {\bf maxcost}$=10^2$

\item {\bf Assign-Med-Cost.} Set {\bf maxcost}$=10^5$.

\item {\bf Assign-Hi-Cost.}  Set {\bf maxcost}$=10^8$. 
\end{itemize} 

\subsection{The Density Family.}
Networks in this family vary in the vertex degree of the supply
vertices.  For a network with $n$ vertices, let {\bf sources}$ = n/2$
and let {\bf maxcost}$=10^5$.

\begin{itemize} 
\item {\bf Assign-Lo-Degree}  Set {\bf degree}$=8$.  This network 
contains $4n$ arcs.

\item {\bf Assign-Med-Degree.}  Set {\bf degree}$= \log_2 n$.  This network 
contains $(n \log_2 n) /2$ arcs.

\item {\bf Assign-Hi-Degree.}  Set {\bf degree}$=n/8$.  This network
contains $(n^2/16)$ arcs.

\item {\bf Assign-Xhi-Degree.}  Do not use the {\bf degree} command. Instead,
use {\bf complete} to generate a network with all $n^2/4$ arcs
present.

\end{itemize} 

\section{Minimum Cost Flows}

This section describes problem families for testing minimum
cost flow programs.

Implementations on sequential machines should solve problems of size
at least $n_{min} = 128 = 2^{7}$.  Implementations for parallel
architectures should have $n_{min}= 1024 = 2^{10}$.

\subsection{Maximum Flow Problems.}

The input families defined for maximum flow problems can be used to
study variations in network {\bf depth}, {\bf density}, and {\bf
capacity-scale} for minimum cost flows.

Use the awk program {\bf maxmin.a} to convert instances in the maximum
flow format to instances in the minimum cost flow format.  Note that
the maximum flow problems are converted into circulation problems: all
nodes are transhipment nodes with demands equal to zero.

\subsection{Assignment Problems.} 

The input families defined for assignment problems can be used to
study variations in {\bf cost scale} and {\bf vertex degree}.  Use the
awk  program {\bf asnmin.a} to convert instances in the
assignment format to instances in the minimum-cost flow format.  Note
that the conversion program assigns {\bf supply}$=1$ to all source
nodes in the bipartite network, and {\bf demand}$=-1$ to all sink
nodes.  Therefore total-supply will equal total-demand (implying the
existence of a feasible solution) only for networks where {\bf
sources} = {\bf nodes}$/2$.

\subsection{NETGEN}
DIMACS has available two versions of the well-known NETGEN Generator.
The file {\bf netgen.f} contains a NETGEN program written in Fortran;
input and output files must be in standard NETGEN format.

The file {\bf netgen.c} contains a C-language version of NETGEN.  This
program has compiler switches to provide a standard Fortran subroutine
interface (allowing the code to be called from Fortran programs),
to generate output instances compatible with the DIMACS format, and
to provide a program trace for debugging purposes.

The NETGEN generator accepts a sequence of 15 integers interpreted as
follows.
\vspace{.2in}

\begin{tabular}{rll} \hline 
1 & {\bf seed} & Random number seed (a large integer). \\ 2 & {\bf
problem} & Problem number (for output documentation.) \\ 3 & {\bf
nodes} & Number of nodes. \\ 4 & {\bf sources} & Number of sinks
(including transshipment). \\ 5 & {\bf sinks} & Number of sinks
(including transshipment). \\ 6 & {\bf density} & Number of
(requested) arcs. \\ 7 & {\bf mincost} & Minimum arc cost. \\ 8 & {\bf
maxcost} & Maximum arc cost. \\ 9 & {\bf supply} & Total supply. \\ 10
& {\bf tsources} & Transhipment sources. \\ 11 & {\bf tsinks } &
Transshipment sinks. \\ 12 & {\bf hicost } & Percent of skeleton arcs
given max cost. \\ 13 & {\bf capacitated} & Percent of arcs to be
capacitated. \\ 14 & {\bf mincap} & Minimum capacity of capacitated
arcs. \\ 15 & {\bf maxcap} & Maximum capacity of capacitated arcs. \\
\hline
\end{tabular} 

\subsection{The Supply/Demand Ratio Family.}

Networks in this family may be used to study the effect of changing
the ratio of supply nodes to demand nodes.  Use {\bf netgen.c} with
the values for parameters 1 through 15 as given below.  The notation
$X$ means ``your choice.''

\vspace{.2in} 
\begin{tabular}{|l|rrrrr|} \hline
1---5 & X & X & $n$ & (sources) & (sinks) \\ 
6---10 & $8n$ & 1 & 1000 & $10^5$ & 0 \\ 
11---15 & 0 & 0 & 0 & 0 & 0 \\ \hline
\end{tabular}

\begin{itemize}
\item {\bf NETGEN-Lo-Lo.}  Let {\bf sources}$=n/8$ and let 
{\bf sinks}$=n/8$.

\item {\bf NETGEN-Lo-Hi.}  Let {\bf sources}$=n/8$ and let 
{\bf sinks}$=n/2$.

\item {\bf NETGEN-Hi-Lo.}  Let {\bf sources}$=n/2$ and let
{\bf sinks}$=n/8$.

\item {\bf NETGEN-Hi-Hi.} Let {\bf sources}$=n/2$ and let 
{\bf sinks}$=n/2$.
\end{itemize}

\subsection{The Total-Supply Family.}

Networks in this family can be used to assess the effect of the total
network supply on program running time.  These are uncapacitated
transportation problems.  Use {\bf netgen.c} with the following 15
parameter settings to generate a network with $n$ nodes.  The notation
$X$ means ``your choice.''

\vspace{.2in} 
\begin{tabular}{|l|rrrrr|} \hline
1---5 & X & X & $n$ & $n/2$ & $n/2$ \\ 
6---10 & $8n $ & 1 & 1000 & (supply) & 0 \\ 
11---15 & 0 & 0 & 0 & 0 & 0 \\ \hline
\end{tabular}

\begin{itemize}
\item{\bf Netgen-Lo-Supply.}  Let {\bf supply}$= 100$. 
\item {\bf Netgen-Med-Supply.} Let {\bf supply}$= 10^5$. 
\item {\bf Netgen-Hi-Supply.} Let {\bf supply}$= 10^8$.  
\end{itemize} 

\section{Geometric Matching Problems.}

This section describes input families for matching programs which take
geometric input instances.  For sequential implementations the minimum
problem size should be $n_{min} = 128 = 2^7$.  For parallel implementations
the minimum problem size should be $n_{min} = 512 = 2^9$.  

\subsection{The Dimension Family}
The graphs in this family vary in the number of 
dimensions containing the point space.

\paragraph{ } 
Use the {\bf dcube.c} generator to produce $n$ points distributed
uniformly in a d-dimensional cube.  For this input family let the
maximum point coordinate value be {\bf maxloc}$=10^6$.

\begin{itemize}
\item {\bf Geom-Lo-D.}  Set {\bf dimension}$=2$.
\item {\bf Geom-Med-D.}  Set {\bf dimension}$=4$.
\item {\bf Geom-Hi-D.}  Set {\bf dimension}$=8$. 
\end{itemize} 

\subsection{The Locality Family} 

Graphs in this family vary in the degree of ``locality'' 
in the graph.  Use the {\bf fractals.c} generator 
with the input files named below. 
This generator produces images which are ``recursively self-similar.''

\begin{itemize}
\item { \bf Geom-Lo-Locality.}  Use the input file {\bf box1.in} 

\item { \bf Geom-Med-Locality.} Use the input file {\bf box2.in}

\item {\bf Geom-Hi-Locality.}  Use the input file {\bf box3.in} 
\end{itemize} 

\section{Graphs in Edge-List Format.}

This section gives input families for weighted matching problems which
are presented in the edge-list format.  Most of these graphs are suitable
for testing either weighted or unweighted problems; some exceptions 
are noted below. 

\subsection{Assignment Problems.}

The assignment problem is a maximum weighted matching problem defined
for bipartite graphs.  The input families defined earlier for
assignment problems can be used study performance of general matching
algorithms with respect to variations in {\bf graph density}, the 
{\bf size of the bipartite partition}, and the {\bf number of bits} 
needed to specify edge costs.  (The last one is
not suitable for studying unweighted matching algorithms.) 
Use the awk program {\bf asnmat.a} to convert instances in {\bf .asn}
format to instances in {\bf .edge} format.

\subsection{Generators for Matching Problems.} 

Use the generation program {\bf random.c} to produce a random graph of
$n$ nodes and $m$ edges.  Edges are drawn randomly without
replacement from the set of $n(n-1)/2$ possible edges.  Edge costs are
uniform and have a specified maximum value.  

The program {\bf neighbor.c} accepts a graph in {\bf .geom} format on
standard input, plus a command-line argument {\bf k}.  It produces a
graph in {\bf .edge} format having approximately $kn$ edges.  Vertex
$i$ has an edge to vertices $[i-k, i-1]$ (with fewer edges for the
extremal vertices).   The edge cost for a pair of connected
vertices corresponds to their distance in the geometric graph,
computed according to the $L_1$ (Manhattan) norm.

Equivalently, if Manhattan distances in the original geometric graph
are represented as the lower diagonal of a matrix, the parameter {\bf
k} specifies edges from {\bf k} rows adjacent to the main
diagonal.  Setting {\bf k}$=${\bf n} will produce a complete graph in
edge-list format.  Note that graph structure is fixed for a given $n$
and $k$: for cardinality-matching algorithms it is not necessary 
to run several ``random'' trials at each problem size.  

\subsection{A Graph Density Family.}

This family represents a range of graph densities for two 
types of graphs.  For the first
two, use {\bf random.c} with the following default settings. 

\begin{tabular}{ll}
{\bf nodes} & $n$ 
\\ {\bf edges} & (see below) 
\\ {\bf maxcost} &
100000 \\
\end{tabular} 

\vspace{.2in} 
The generation program {\bf dcube.c} (described in the previous 
section) generates a graph in the {\bf .geom} format. 
Use the following commands to generate geometric
graphs of $n$ nodes.

\begin{tabular}{ll}
{\bf nodes } & n \\ 
{\bf dimension} & 2 \\ 
{\bf maxloc} & $10^5$ \\
\end{tabular} 

Convert the output of {\bf dcube.c}  to {\bf .edge} format 
using {\bf neighbors.c} with the settings listed below. 
Note that for unweighted matching problems the two Hi-Density graphs are
identical. 

\begin{itemize}
\item {\bf Random-Lo-Density.} Use {\bf random.c} with 
{\bf edges}$= 2n \log_2 n$.

\item {\bf Random-Hi-Density.} Use {\bf random.c} with
{\bf edges}$=n(n-1)/2$.  This will give a complete graph with uniform
edge costs.

\item {\bf Man-Lo-Density.} Use {\bf dcube.c} and
{\bf neighbor.c} with {\bf k}$= 2 \log_2 n$.

\item {\bf Man-Hi-Density.} Use {\bf dcube.c} and
{\bf neighbor.c} with {\bf k}$=n$. This will give a complete graph
with edge weights induced by the Manhattan metric on random points.

\end{itemize} 

\subsection{The Cost-Scaling Family.} 

This family of graphs varies in the number of bits required to specify
the edge costs.  This family would not give an interesting test of
cardinality-matching problems.  Use {\bf random.c} with {\bf edges}$=2
n \log_2 n$ for these input classes.

\begin{itemize}
\item {\bf Random-Lo-Cost.} Set {\bf maxcost}=$10^2$. 

\item {\bf Random-Med-Cost.} Set {\bf maxcost}$=10^5$. 

\item {\bf Random-Hi-Cost.} Set {\bf maxcost}$=10^8$. 

\end{itemize} 

\subsection{A Hard Cardinality Problem.} 

The program {\bf hardcard.f} generates fixed (not random) instances
which are worst-case for Edmond's cardinality matching algorithm.
Note that instances can be used for unweighted or 
weighted matching problems (edge costs are set to 1).  

\begin{itemize}

\item {\bf Card-Hard.}  To generate a problem with approximately 
$n=2^x$ vertices, set $k = n/6$ (rounded to the nearest integer)
in the program PARAMETER statement.  This graph will have $6k$
vertices and $8k^2$ (about $2n^2 / 9$) edges.  All edge costs are set to 1.

\item {\bf Card-Random.} Use {\bf random.c} with {\bf edges}$=n^2/4$. 
Set {\bf maxcost}$=10$. 

\item {\bf Card-Neighbors.}  Use {\bf dcube.c} with {\bf dimension}$=8$
and {\bf maxloc} = $10$.  To obtain a graph in {\bf .edge} format,
use {\bf neighbor.c } with command line value $n/4$.  

\end{itemize} 

\end{document}

