OR-Library

J E Beasley

OR-Library is a collection of test data sets for a variety of OR problems.

A full list of the test data sets available in OR-Library can be found here.

Capacitated minimal spanning tree

There are two data files

The files capmst1 and capmst2 include symmetric cost matrices
for the capacitated minimum spanning tree problem (CMST).

Approximate file sizes:
capmst1: 275Kb
capmst2: 850Kb

The cm problems (non-unit weights, see below) were communicated
by Yazid Sharaiha (y.sharaiha@ic.ac.uk) and the tc, te problems
(unit weights, see below) were communicated by Luis Gouveia
(sgouveia@skull.cc.fc.ul.pt).

(1)  capmst1
------------------------------------------------------------------------

This file contains tc (central depot) and te data (end depot)
for the CMST with unit demands.

L. Gouveia, A comparison of directed formulations for the
capacitated minimal spanning tree problem, Telecommunication
Systems vol 1, 1993, 51-76.

Each vertex i (i=1,...n) has unit weight and each subtree connected to the
depot N (N=n+1) in the final solution should have a total weight of less than
or equal to Q.

For each problem type (tc,te), there are 10 problems each, 5 of size n=40
and 5 of size n=80.  Note that the depot is vertex number 41 and 81
respectively.

For size n=40 (N=41) : tc40-*.txt and te40-*.txt (*=1,...,5)
capacity Q can take three values: Q=3, 5, or 10.
Total number of problems = 2*5*3 = 30 (15 type tc and 15 type te).

For size n=80 (N=81) : tc80-*.txt and te80-*.txt (*=1,...,5)
capacity Q can take three values: Q=5, 10, or 20.
Total number of problems = 2*5*3 = 30 (15 type tc and 15 type te).

The format of the file is as follows:

problem name
problem size n
edge costs c(i,j), i=1,N, j=1,N

(Note c(i,i) is taken as a large number)

(2) capmst2
-----------------------------------------------------------------------

Whereas the tc and te problems satisfy the triangle inequality,
the cm problems contained in capmst2 do not.
Moreover, the problems are not of unit weight.

There are three problem sizes N=50,100, 200
(Note that n=49, 99, 199 respectively, with the depot located
at vertex N).

For each problem size, there are 5 problems each.

For each problem cm**_r*.data (**=50,100,200, *=1,...5), there
is a weight file called priz**_r.dat containing the weight of each
vertex q(i), i=1,...,n.

a- The capmst2 file contains:
name of the weight file
vertex weights q(i), i=1,n (N-1)
-------------------------------
b- name of the problem
size of the problem given by N
edge costs c(i,j), i=1,N, j=1,N
--------------------------------
Part b is repeated for the same problem size (starting with N=50)
then part a re-appears for the next problem size (ie, N=100)
and so on for N=200.

(Note that c(i,i) here is given a zero value)

For all problem sizes, Q can take three values:
Q=200, 400 or 800

Total number of problems = 3*5*3 = 45
-----------------------------------
Update: 25th September 2003
Ricardo Fukasawa (rfukasawa@axiomaopt.com.br) has pointed
out that the tc/te 80 files appear to be flawed, in that
they should correspond to symmetric cost matrices, and they are not
symmetric.
He has supplied what are believed to be correct versions of these files,
together with a number of other data files - these are all available
in the zipped file capmstnew.zip