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.
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
Click here to access these files