181.mcf
SPEC CPU2000 Benchmark Description File
Benchmark Name
181.mcf
Benchmark Author
Dr. Andreas Loebel
KonradZuseZentrum Berlin (ZIB)
Takustr. 7
D14195 Berlin, Germany
Email: loebel@zib.de
Phone: +49 (0)30 841 85  239
Fax: +49 (0)30 841 85  269
Secretary: +49 (0)30 841 85  208
Benchmark Program General Category
Combinatorial optimization / Singledepot vehicle scheduling
Benchmark Description
A benchmark derived from a program used for singledepot vehicle scheduling
in public mass transportation. The program is written in C, the benchmark
version uses almost exclusively integer arithmetic.
The program is designed for the solution of singledepot vehicle scheduling
(sub)problems occurring in the planning process of public transportation
companies. It considers one single depot and a homogeneous vehicle fleet.
Based on a line plan and service frequenciesd, socalled timetabled trips
with fixed departure/arrival locations and times are derived. Each of this
timetabled trip has to be serviced by exactly one vehicle. The links
between these trips are socalled deadhead trips. In addition, there are
pullout and pullin trips for leaving and entering the depot.
Cost coefficients are given for all deadhead, pullout, and pullin trips.
It is the task to schedule all timetabled trips to socalled blocks such
that the number of necessary vehicles is as small as possible and,
subordinate, the operational costs among all minimal fleet solutions are
minimized.
For simplification in the benchmark test, we assume that each pullout and
pullin trip is defined implicitly with a duration of 15 minutes and a cost
coefficient of 15.
For the considered singledepot case, the problem can be formulated as a
largescale minimumcost flow problem that we solve with a network simplex
algorithm accelerated with a column generation. The core of the benchmark
181.mcf is the network simplex code "MCF Version 1.2  A network
simplex implementation", For this benchmark, MCF is embedded in the
column generation process.
The network simplex algorithm is a specialized version of the well known
simplex algorithm for network flow problems. The linear algebra of the
general algorithm is replaced by simple network operations such as finding
cycles or modifying spanning trees that can be performed very quickly. The
main work of our network simplex implementation is pointer and integer
arithmetic.
Input Description
The input file contains line by line

the number of timetabled and deadhead trips (first line),

for each timetabled trip its starting and ending time,

for each deadhead trip its starting and ending timetabled trip and its
cost.
Worst case execution time is pseudopolynomial in the number timetabled and
deadhead trips and in the amount of the maximal cost coefficient. The
expected execution time, however, is in the order of a loworder
polynomial.
The benchmark requires about 100 and 190 megabyte for a 32 and a 64 bit
architecture, respectively.
Output Description
The benchmark writes to two output files, inp.out and mcf.out. inp.out
contains log information and a checksum, mcf.out contains check output
values describing an optimal schedule computed by the program.
Programming Language
ANSI C, mathematical library (libm) required.
Known portability issues
The header source file "prototyp.h", which is (indirectly)
required by all modules, contains the lines
#ifndef _PROTO_
#if defined(__STDC__)  defined(__cplusplus)  defined(WANT_STDC_PROTO)
#define _PROTO_( args ) args
#else
#define _PROTO_( args )
#endif
#endif
All C functions (subroutines) are defined in the original program with and
without function prototypes, e.g.:
/* function defined externally: */
extern long suspend_impl _PROTO_(( network_t *, cost_t, long ));
/* function defined in this module: */
#ifdef _PROTO_
long resize_prob( network_t *net )
#else
long resize_prob( net )
network_t *net;
#endif
In the SPEC version, DWANT_STDC_PROTO is set as a required compilation
flag in the master Makefile 181.mcf/src/Makefile. This has the effect that
all compilers, predefining __STDC__ or not, use ANSI C prototyping. This is
intended for reasons of compatibility and standard adherence.
Other information, WWW Resources
Background information about the vehicle scheduling problem can be found in
the author's Ph.D. thesis "Optimal Vehicle scheduling in public
transit", which is available via WWW at the author's homepage or at ftp://ftp.zib.de/pub/zibpublications/books/Loebel.disser.ps.
The work horse in the benchmark 181.mcf is the code "MCF Version 1.2
 A network simplex implementation", which is available for academic
use free of charge via WWW at www.zib.de.
An excellent text book about the network simplex algorithm and network flow
in general is Ahuja, Magnanti, and Orlin: "Network Flows: Theory,
Algorithms, and Applications", PrenticeHall, Inc., Englewood Cliffs,
New Jersey, 1993.
Last Updated: 14 October 1999