Серия "Grid"

Примеры построены с помощью модификации генератора RMFGEN из [1]. Генератор строит заданное количество двумерных решеток с дугами, соединяющими случайные перестановки вершин в решетках размера a × a. Дуги внутри решеток имеют пропускные способности равные 3600, для дуг, соединяющих решетки, пропускные способности назначаются случайно из чисел от 1 да 100. Источники и стоки также выбираются случайно.

В представленных примерах a = 6, количество решеток b указано в таблице, количество продуктов равно 15. Требуемые объемы пересылки были назначены каак в [1] так, чтобы существовал допустимый поток c максимальным насыщением дуг λ, где λ равняется 0.6 или 1. Примеры в формате GAMS (www.gams.com) доступны в виде zip архива grid.zip. Каждый файл соответствует одному примеру и содержит пропускные способности дуг, обозначенные by d(⋅,⋅) и требуемые объемы продукта (трафика) обозначенные 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

Литература

[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.

Серия "Real"

Примеры серии "Real" моделируют возможную конфигурацию сети передачи данных, состоющей из спутников и наземных станций. Изначальный вид модели такой сети не совпадает с постановкой рассматриваемой задачи LBMCF1: наземная станция может состоять из нескольких интернет шлюзов, и пропускные способности задаются не для каждой дуги в отдельности, а для всего шлюза в совокупности. Примеры r1-r5 и r7 отражают различные подходы к представлению этой структуры в виде LBMCF1. Заметим, что только r1 является точным представлением, тогда как остальные - только приближенные.

В примере r1 каждый шлюз представлен своим "главным" узлом, а также двумя фиктивными узлами для входящего и исходящего трафика. Пропускная способность шлюза назначается дугам между главным узлом и фиктивными. Трафик между разными шлюзами проходит только через фиктивные узлы. В r2 каждый шлюз представлен одним узлом, все шлюзы соединены с одним фиктивным "центральным" узлом. Пример r3 является вариантом r2 с удвоенными пропускными способностями. В r4, все шлюзы одной станции объединяются в один узел. Пример r5 является вариантом r4 с удвоенными пропускными способностями. В r6 представлены данные долько для спутников, наземные станции удалены. Пример r7 построен аналогично r1, только все шлюзы одной и той же станции объединены в один с суммарной пропускной способностью.

Примеры в формате GAMS доступны в виде zip архива real.zip. Каждый файл соответствует одному примеру и содержит пропускные способности дуг, обозначенные by d(⋅,⋅) и требуемые объемы продукта (трафика) обозначенные tr(⋅,⋅).

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

Серия "Modified Real"

Серия "Modified Real" состоит из 300 примеров, моделирующих сеть передачи данных аналогично примеру r7 серии "Real" но в разные интервалы времени. Различное положение спутников в разное время приводит к тому что наличие и отсутствие связей спутник-спутник и спутник-станция в разных примерых неодинаковы, как и пропускные способности. Требуемый объем трафика одинаков для всех примеров, количество сессий (продуктов в терминах LBMCF1) - 12481, суммарный объем - 2244.717.

Примеры в формате GAMS доступны в виде zip архива modified_real.zip. Каждый файл соответствует одному примеру и содержит пропускные способности дуг, обозначенные by d(⋅,⋅). Требуемые объемы продукта (трафика) обозначенные tr(⋅,⋅). заданы в отдельном файле demand.gms.