Topology Design
Overview
The Topology Design problem seeks to construct graphs with optimal communication properties given structural constraints. This problem has applications in network design, where minimizing communication latency (diameter) while limiting connection costs (degree) is crucial.
External Resources:
- http://research.nii.ac.jp/graphgolf/
- https://research.nii.ac.jp/graphgolf/problem.html
Problem Description
Given:
- A target number of nodes $n$
- A maximum degree constraint $\Delta$
Objective: Find a graph $G = (V,E)$ with $|V| = n$ and maximum degree $\Delta(G) \leq \Delta$ that minimizes the diameter.
Diameter: The diameter of a graph is the maximum shortest path distance between any pair of vertices: $$ \text{diam}(G) = \max_{u,v \in V} d(u,v) $$
Note: We do not use average shortest path length as a tiebreaker.
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.
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.
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.
Runtime scaling with instance size
Fastest feasible runtime (log scale) per instance versus Nodes — shows how each group scales.
Submissions
(3)
| Method | Submitter | Type | Date | Instances |
|---|---|---|---|---|
| MIP-Seidel-Quadratic | Maximilian Schicker | Classical | 2024-12-06 | 16 |
| MIP-Seidel-Linear | Maximilian Schicker | Classical | 2024-12-06 | 16 |
| MIP-Flow | Maximilian Schicker | Classical | 2024-12-06 | 16 |