Capacitated network design problem data

This page contains data for the capacitated network design problem. The optimization model is described in the following articles.

Kaj Holmberg and Di Yuan: A Lagrangian heuristic based branch-and-bound approach for the capacitated network design problem. Operations Research, vol 48, 2000, pp 461-481.
Kaj Holmberg and Di Yuan. A Lagrangean Approach to Network Design Problems. International Transactions in Operational Research, vol 5, 1998, pp 529-539.

In short it is a problem of designing a capacitated network for a demand consisting of several single origin - single destination demands (commodities). There are fixed costs for using links and linear costs for the flow (or capacity used). In general (Holmberg and Yuan, 1998) the fixed costs can be staircase formed (with individual sizes of the steps), but in this data (as in Holmberg and Yuan, 2000) there is only one fixed cost and one capacity for each link. For some links the fixed cost is zero, and the linear cost is very large. The links and the demands are directed.

More information about the structures of problems is given in Holmberg and Yuan (2000) (although there are some small differences between the data used in that article and the data given here).

Any use of these problem data should be accompanied with a reference to the two articles above. You might also want to send me an email.

Data is given in two lists, one for the links and one for the demands, each ending with a row of zeros.

Data format:

For each link the following is given:
Starting node, ending node, linear cost coefficient, free capacity, number of capacity steps. For each capacity step of the link: Fixed cost, capacity.
The list ends with five zeros.

For each demand pair of nodes:
Demand number, origin, destination, demand amount.
The list ends with four zeros.

Example:

   1  2  10000  50  0
   2  3  10  0  1
   400  60
   0  0  0  0  0
   1  1  3  13
   0  0  0  0

The link from node 1 to node 2 has high linear cost (10000), free capacity 50 and no fixed cost. The link from node 2 to node 3 has linear cost coefficient 10, no free capacity and one capacity step, with fixed cost 400 and capacity 60. Commodity 1 has origin at node 1, destination at node 3 and demand of 13 units.

In file 00index1 characteristics of each problem is given. On each line: Problem name, number of nodes, number of links, number of demand pairs, maximal number of capacity steps, number of links with nonzero fixed cost, total number of capacity steps, sum of all fixed costs, average fixed cost, sum of all linear cost coefficients, average linear cost coefficient, total demand, average demand.

Download all problem data in a zip-file.

Last update 28-Mar-2002.
Kaj Holmberg, email: kaj.holmberg@liu.se, homepage: http://users.mai.liu.se/kajho48.
Division of Optimization, Department of Mathematics, Linköping Institute of Technology, SE-581 83 Linköping, SWEDEN.