Series "Grid"

The networks were obtained using a modification of generator RMFGEN, see [1]. It produces a given number of two-dimensional grids with arcs connecting a random permutation of nodes in b adjacent planar grids of size a × a. Arcs of the grids have capacities 3600, while the capacities of arcs connecting the grids are chosen uniformly at random from 1 to 100. Origins and destinations are randomly chosen.

In the presented instances, a = 6, parameter b is given in the table, the number of commodities is 15. The demands were assigned as in [1] so that there is a feasible flow with the maximum arc congestion λ, where λ is set to 0.6 or 1. The instances in GAMS format (www.gams.com) can be downloaded as a zip archive grid.zip. Each file corresponds to one instance and contains bandwidths denoted by d(⋅,⋅) and commodity (traffic) demands denoted by tr(⋅,⋅).

Instance	b	λ	| E |	Total demand	Upper bound (for L = 9)	Known solution (for L = 9)
rmfgen.lam-060.d-6-2-15	2	0.6	276	3245	3245	3245*
rmfgen.lam-060.d-6-4-15	4	0.6	588	2072	2072	2072*
rmfgen.lam-060.d-6-6-15	6	0.6	900	4010	4010	3933
rmfgen.lam-060.d-6-8-15	8	0.6	1212	2874	2639	2580
rmfgen.lam-100.d-6-2-15	2	1	276	5415	5415	5270
rmfgen.lam-100.d-6-4-15	4	1	588	3461	3461	3284
rmfgen.lam-100.d-6-6-15	6	1	900	6688	6317	6228
rmfgen.lam-100.d-6-8-15	8	1	1212	4798	4091	4004

References

[1] A.V. Goldberg, A.D. Oldham, S. Plotkin, and C. Stein, An implementation of an approximation algorithm for minimum-cost multicommodity flows, Proceedings of the 6-th Integer Programming and Combinatorial Optimization, LNCS Vol. 1412, Berlin, Springer, 1998, pp. 338-352.

Series "Real"

The "Real" instances model a possible real telecommunication network consisting of satellites and ground stations. The original input data is not the same as for the considered LBMCF1 problem: the ground station can consist of several internet gateways, and the bandwidth for communications between stations is defined not for the particular edges, but for the nodes corresponding to the gateways. The instances r1-r5 and r7 reflect different approaches to represent this structure in a form of LBMCF1. Note that only r1 gives an exact representation, all the others are approximate.

In r1, each gateway is represented by its own "main" node and in addition has two artificial nodes for incoming and outgoing traffic. The gateway bandwidth is assigned to the arcs from the main node to these artificial nodes. The traffic between gateways is passed only throung the artificial nodes. In r2, each gateway is represented by one node and is connected with one artificial "central" node. Instance r3 is r2 with doubled bandwidths. In r4, all gateways of the same station are united in one node. Instance r5 is r4 with doubled bandwidths. In r6, all the stations are removed, only the satellites are given. Instance r7 is build analogously to r1, but all the gateways of one station are united in one gateway having their totals bandwidth.

The instances in GAMS format (www.gams.com) can be downloaded as a zip archive real.zip. Each file corresponds to one instance and contains bandwidths denoted by d(⋅,⋅) and commodity (traffic) demands denoted by tr(⋅,⋅). In the table given below, k stands for the number of commodities.

Instance	| V |	| E |	k	Total demand	Upper bound (for L = 9)	Known solution (for L = 9)
r1	534	19474	12373	2246.346787	2246.346787	2237,356904
r2	272	1292	12373	2246.346787	2190.589905	2171.136082
r3	272	1292	12373	2246.346787	2246.346787	2332751300
r4	197	992	12373	2246.346787	2187.728882	2163.453351
r5	197	992	12373	2246.346787	2246.346787	2218.533812
r6	135	750	743	13894.940185	13894.940185	12352.480202
r7	318	4652	245481	2246.346787	2246.346787	2233.596834

Series "Modified Real"

The "Modified Real" series consisit of 300 instances that model the telecommunication network analogously to Instance r7 of the "Real" series but in different time-frames. Different satellite positions in these time-frames lead to different arcs between satellites and between satellites and ground stations. The bandwidth of the arcs varies as well. The demands on the commodities are the same for all instances, the number of commodities is 12481, the total demand is 2244.717.

The instances in GAMS format (www.gams.com) can be downloaded as a zip archive modified_real.zip. Each file corresponds to one instance and contains bandwidths denoted by d(⋅,⋅). The demands are denoted by tr(⋅,⋅). and are given in the separate file demand.gms.