Desktop-Bild

Datensätze für Optimierungsprobleme der diskreten Mathematik

Lehrstuhl II für Mathematik, Lehr- und Forschungsgebiet Diskrete Optimierung
RWTH Aachen University

Übersicht

Auf dieser Website stellen wir zu verschiedenen Problemen der diskreten Mathematik Datensätze zur Verfügung. Die Daten wurden in verschiedenen Forschungswerken in vielfältigen Rechenstudien genutzt. Falls möglich geben wir Hintergundinformationen zu den einzelnen Datensätzen an.

Netzwerkdesign mit Komprimierung (NDPC)

Das Netzwerkdesign Problem mit Komprimierung (NDPC) ist eine Erweiterung des klassischen Netzwerk Design Problems. Für weiterführende Informationen verweisen wir auf die Publikationen:

Extended Cutset Inequalities for the Network Power Consumption Problem, Koster, Phan und Tieves (link).
Design and management of networks with low power consumption, Phan (link).

Die folgenden Datensätze wurden urspünglich für das klassische Netzwerkdesign Problem (NDP) kreiert, siehe:

Cutset Inequalities for Robust Network Design, Koster, Kutschka und Raack (link).

In dieser Forschungsarbeit wurden die Netzwerke "abilene", "geant", "germany17" und "germany50" genutzt. Die zugehörigen Topologien sind der SNDLIB (link) entnommen, dort wird auch deren Format beschrieben. Die Daten können leicht zu vollständigen Datensätzen für NDPC erweitert werden.

Download: Dataset NDP (link).

In der Doktorarbeit von Herrn M. Tieves

Discrete and Robust Optimization Approaches to Network Design with Compression and Virtual Network Embedding, Tieves (to appear),

wurden die Daten zu vollständigen Instanzen für das NDPC Problem erweitert. Die zusätzlichen Daten wurden zufällig erzeugt, wir verweisen auf obigen Link für weitere Informationen diesbezüglich. Die genutzen Daten für das deterministische Problem mit "average" bzw. "peak" Daten finden sich im Folgenden. Die Daten sind in einem für AMPL lesbaren Format.

Download: Dataset "average" (link), Dataset "peak" (link).

Erklärungen/Format:
Knoten: Enthalten in der Menge V.
Kanten: Enthalten in der Menge E.
Kosten: b (Komprimierer) und c (Kantenmodule).
Kantenkapazität: k.
Güter: Menge Q, für q in Q: dest[q,i]=1 wenn Knoten i q's Quelle ist, ..=-1 falls i die Senke von q ist. d[q] Beschreibt den Nachfragewert von q..

In der Doktorarbeit von Herrn M. Tieves wurde auch das robuste NDPC Problem betrachtet. Das zugehörige Datenset ist das Folgende (in AMPL lesbarem Format):

Download: Dataset "robust" (link).

Erklärungen/Format:
Das Format ist das selbe wie im deterministischem Fall. Zusätzlich beschreibt d_nom[..] den nominalen Nachfragewert eines Gutes und d_dev[..] dessen maximale Abweichung. Genauso beschreiben die scal_nom[...] und scal_dev[..] Werte die nominalen Werte der Komprimierungsfaktoren und deren maximale Abweichungen.

Einbettung Virtueller Netze (VNE)

Das Problem der Einbettung Virtueller Netze (VNE) fragt, gegeben ein physikalisches (Substrat-) Netzwerk, wie viele virtuelle Netze auf dem Substrat-Netzwerk realisiert werden können unter gegebenen Knoten und Kanten Resources bzw. Nachfragewerten. Für weiterführende Informationen, verweisen wir auf das VINO Projekt (link) sowie auf die Forschungsarbeiten

Virtual network embedding under uncertainty: Exact and heuristic approaches, Coniglio, Koster und Tieves (link),
Data Uncertainty in Virtual Network Embedding: Robust Optimization and Protection Levels, Coniglio, Koster und Tieves (link),

sowie auf die Doktorarbeit von Herrn M. Tieves:

Discrete and Robust Optimization Approaches to Network Design with Compression and Virtual Network Embedding, Tieves (to appear).

In diesen Arbeiten wurden zwei verschiedene Datensätze genutzt.

Der erste Datensatz enthält kleine bis mittelgrosse Instanzen. Die Substrat-Netze dieser Instanzen wurden der SNDLIB (link) entnommen und entsprechen den (gerichteten) Topologieen "abilene", "atlanta", "nobel-us" und "polska". Die zugehörigen virtuellen Netze (5 - 32 Netze, Kennzeichnung "-r5-" bis "-r32" in den zugehörigen Dateinamen) enthalten jeweils 12 Knoten, die Nachfragewerte bzw. deren Topologien wurde zufällig erzeugt. Die Daten sind in einem für AMPL lesbaren Format.

Der zweite Datensatz enthält große Instanzen. Die Substrat-Netze dieser Instanzen wurden dem Internet Topology Zoo (link) entnommen und entsprechen den (gerichteten) Topologieen "bellsouth, "cernet", "cogentco", "deltacom", "digex", "fatman", "intellifiber" und "redbestel". Die zugehörigen virtuellen Netze (8 - 50 Netze, Kennzeichnung "-r8-" bis "-r50" in den zugehörigen Dateinamen) enthalten jeweils 12 Knoten, die Nachfragewerte bzw. deren Topologieen wurde zufällig erzeugt. Die Daten sind in einem für AMPL lesbaren Format.

Download: Datensatz I (link) 24 Mb, Datensatz II (link) 100 Mb.

Erklärungen/Format:
Substart-Netz Knoten (param V): "Knoten, Kapazität"
Substart-Netz Kanten (param A): "Knoten, Knoten, Kapazität"
Anzahl Virtueller Netze: "r = ..."
Anzahl historischer Datensätze: "t= ..."
Virtuelles Netz "i" Knoten: "vn[i]:= ..."
Virtuelles Netz "i" Profit: "p[i]:= ..."
Virtuelles Netz "i" Topologie: "an[i,j,k]:= 1" (Kante (j,k) existiert für das virt. Netz i.
Virtualles Netz "i", Locality Bedingungen für Knoten j: V_local[i,j] := ... (enthält die Knoten auf die j eingebettet werden darf)
Virtuelles Netz "i" Historischer Demand zum Zeitpunkt t für die virt. Kante (j,k): "d_historical[i,t,j,k]:= ...".
Virtuelles Netz "i" Historischer Demand zum Zeitpunkt t für den virt. Knoten k: "w_historical[i,t,k]:= ...".
d_nominal und w_nominal bescheiben die durchschnittlichen Nachfragewerte bezüglich der historischen Werte, d_deviation und w_deviation die maximal auftretende Abweichung zu den Nominalwerten. Sämtliche anderen Eintragungen wurden in den o.g. Publikationen nicht genutzt.

Equitable Graphenfärbung

Wir verweisen auf die Projektwebsite (link).
letzte Änderung: 12.01.2017 - 15:30