429.mcf
SPEC CPU2006 Benchmark Description

Benchmark Name

429.mcf


Benchmark Author

Andreas Löbel

Dr. Andreas Löbel
Konrad-Zuse-Zentrum Berlin (ZIB)
Takustr. 7
D-14195 Berlin, Germany

E-mail:    loebel [at] zib.de
Phone:     +49 (0)30 841 85 - 239
Fax:                        - 269
Secretary:                  - 208

SPEC Project Leader

Dr. Reinhold Weicker
Retired, company address was:
   Fujitsu Siemens Computers
   EP XS BMC
   Heinz-Nixdorf-Ring 1
   33100 Paderborn
   Germany
   reinhold.weicker [at] fujitsu-siemens.com 

Home: reinhold.weicker [at] t-online.de (home)

Benchmark Program General Category

Combinatorial optimization / Single-depot vehicle scheduling


Benchmark Description

429.mcf is a benchmark which is derived from MCF, a program used for single-depot 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 single-depot 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, so-called timetabled trips with fixed departure/arrival locations and times are derived. Each of these timetabled trips has to be serviced by exactly one vehicle. The links between these trips are so-called dead-head trips. In addition, there are pull-out and pull-in trips for leaving and entering the depot.

Cost coefficients are given for all dead-head, pull-out, and pull-in trips. It is the task to schedule all timetabled trips to so-called 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 pull-out and pull-in trip is defined implicitly with a duration of 15 minutes and a cost coefficient of 15.

For the considered single-depot case, the problem can be formulated as a large-scale minimum-cost flow problem that we solve with a network simplex algorithm accelerated with a column generation. The core of the benchmark 429.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.

Because there have been no significant errors or changes during the years 2000 - 2004, most of the source code of the CPU2000 benchmark 181.mcf was not changed in the transition to CPU2006 benchmark 429.mcf. However, several central type definitions were changed for the CPU2006 version by the author:

Input Description

The input file contains line by line

Worst case execution time is pseudo-polynomial in the number timetabled and dead-head trips and in the amount of the maximal cost coefficient. The expected execution time, however, is in the order of a low-order polynomial.

In the version for CPU2006 (429.mcf), new input files were defined for test, train, and ref, with the goal of longer execution times. The heap data size, and with it the overall memory footprint, increased accordingly.

Memory Requirements

429.mcf requires about 860 and 1700 megabyte for a 32 and a 64 bit data model, respectively.

Output Description

The benchmark writes to two output files, inp.out and mcf.out.

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 via the parameter file 429.mcf/Spec/object.pm, line

$bench_cflags='-DWANT_STDC_PROTO';

This line, controlling compilations performed within the SPEC tool harness, 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 Resource

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 www.zib.de/loebel or at ftp://ftp.zib.de/pub/zib-publications/books/Loebel.disser.ps.

The work horse in the benchmark 429.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. Information about MCF is available in http://typo.zib.de/opt-long_projects/Software/Mcf/

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", Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1993.

MCF had originally been developed for application in the public transportation systems of Hamburg and Berlin (BVG). For BVG, bus scheduling was optimized in 1998 on the basis of MCF; BVG also owns usage rights to the software that has been integrated into their planning system BERTA.

The MCF method for vehicle scheduling later has been integrated, into the vehicle and personel planning system MICROBUS. This system in now marketed by IVU Traffic Technologies AG (http://www.ivu.de) to public transportation companies; the bus service divions of the German and the Austrian railway companies are among the licencees.

Compared with the original and the commercial versions, the benchmark version has been simplified in the I/O area, to keep the I/O content small. The main algorithmic part, however, has been retained.


Last updated: $Date: 2011-08-16 18:23:17 -0400 (Tue, 16 Aug 2011) $