Network Design

Telecommunications Network Planning

Binary ILP / QUBO network telecommunications NP-hard

Instances 20

Optimally solved 6 / 20

Variable range 101–13,249

Objective minimize

Overview

The Network Design problem involves constructing a cost-efficient communication network that can handle specified traffic demands while maintaining degree constraints. This problem is relevant for telecommunications, data center design, and logistics networks.

Problem Description

Given an $n \times n$ demand matrix $T$ (where $t_{ij}$ represents traffic from node $i$ to node $j$) and an integer $p > 0$:

1. Construct a simple directed graph $D$ with node set $\{1,\ldots,n\}$ where each node has in-degree and out-degree equal to $p$ 2. Route $t_{ij}$ units of flow from $i$ to $j$ for all $1 \leq i, j \leq n$ with $i \neq j$ 3. Minimize the maximum aggregate flow on any edge of $D$

Instance Parameters:

$p = 2$ (each node has 2 incoming and 2 outgoing connections)
$n \in \{5, \ldots, 24\}$ nodes
Demand matrix entries: $t_{ij} \in \{0\} \cup [16, 100]$

Performance

Runtime to reach best-known objective

Sorted instances vs total runtime. A point (x, y) means x instances were solved within y seconds. Solid line + filled circle = proven exact; dashed line + open diamond = heuristic. Lower-right is better.

Classical (6 · 5 exact, 1 heuristic)

Time-to-solution (TTS) to reach best-known objective

Same as the runtime cactus but uses the reported Time-to-Solution rather than total runtime. Solid = exact, dashed = heuristic.

Classical (6 · 5 exact, 1 heuristic)

Solution quality (performance profile)

Share of instances each group brings within a given optimality gap of the best-known objective. Higher is better; the value at “best” is the share solved exactly.

Classical (19)

Runtime scaling with instance size

Fastest feasible runtime (log scale) per instance versus Variables — shows how each group scales.

Classical (19)

Submissions (1)

Method	Submitter	Type	Date	Instances
MIP	Maximilian Schicker	Classical	2024-12-06	20

Instances (20)

20 of 20

Name	Variables	Constraints	Best objective	Source	Status	Download
network05	101	130	65,500	Reference solution	Optimal	↓ raw
network06	181	222	101,000	Reference solution	Optimal	↓ raw
network07	295	350	142,400	Reference solution	Optimal	↓ raw
network08	449	520	170,231	Reference solution	Optimal	↓ raw
network09	649	738	196,750	Reference solution	Optimal	↓ raw
network10	901	1,010	210,800	Reference solution	Optimal	↓ raw
network11	1,211	1,342	238,334	Reference solution	Best known	↓ raw
network12	1,585	1,740	276,474	Reference solution	Best known	↓ raw
network13	2,029	2,210	304,116	Reference solution	Best known	↓ raw
network14	2,549	2,758	350,173	Reference solution	Best known	↓ raw
network15	3,151	3,390	383,000	Reference solution	Best known	↓ raw
network16	3,841	4,112	409,067	Reference solution	Best known	↓ raw
network17	4,625	4,930	460,182	Reference solution	Best known	↓ raw
network18	5,509	5,850	481,950	Reference solution	Best known	↓ raw
network19	6,499	6,878	514,625	Reference solution	Best known	↓ raw
network20	7,601	8,020	548,536	Reference solution	Best known	↓ raw
network21	8,821	9,282	593,000	Reference solution	Best known	↓ raw
network22	10,165	10,670	647,594	Reference solution	Best known	↓ raw
network23	11,639	12,190	686,453	Reference solution	Best known	↓ raw
network24	13,249	13,848	663,688	Reference solution	Best known	↓ raw

View on GitHub ↗ View Leaderboard Browse All Instances