Algorithms and Complexity Group
  • People
  • Research
  • Courses
  • Talks
  • Jobs
  • Contact

Problem Instances

Contents

Graph Burning Problem

Contact: Enrico Iurlano and/or Günther Raidl

Computational results referred to in the preprint [Iurlano, Raidl, and Djukanovic 2025] can be found here.
A description of the instance format can be found here here.

Interactive Job Scheduling Problem

Contact: Johannes Varga and/or Günther Raidl

The IJSP instance set can be found here.
The instance set with real-world availabilities can be found here.

A description of the instance format can be found here.

The samples for the Bayesian Learning can be found here.
Their format is described here.

Roman Domination Problem

Instance sets for different graph classes can be found here.
Experimental results for the instance sets can be found here.
A description of the instance format can be found here.

1 result
2024
[1]A Simulated Annealing Based Approach for the Roman Domination Problem
Jakob Greilhuber, Sophia Schober, Enrico Iurlano, Günther R. Raidl
Metaheuristics and Nature Inspired Computing (Bernabé Dorronsoro, Rachid Ellaia, El-Ghazali Talbi, eds.), pages 28–43, 2024, Springer.
[bibtex] [pdf] [doi]

Contact: Enrico Iurlano and/or Günther Raidl

EV Fleet Charging and Allocation Problem

Contact: Johannes Varga and/or Günther Raidl

The EVFCAP instance set can be found here.
The reduced EVFCAP instance set can be found here.

A description of the instance format can be found here.

EV charging scheduling problem with SOC-dependent maximum charging power

Contact: Thomas Jatschka and/or Günther Raidl

Individual EVS-SOC instances can be found here.
Rolling horizon EVS-SOC instances can be found here.

A description of the instance format can be found here.

Searching for Stable Fixed-Edge Graphs - Instances and Source Code

Contact: Benedikt Klocker and/or Günther Raidl
Instance Set 1 (3-connected 3-regular planar graphs with minimum degree three) can be found here.
Instance Set 2 (after inserting some random degree two vertices into 3-connected 3-regular planar graphs with minimum degree three) can be found here.
Instance Set 3 (random potential candidate graphs for minimal counter example, grouped by number of faces) can be found here.

All instance files are in g6-format see here for a description of the format.

The source code for the program to check if a graph contains a SFE-cycle can be found here.

Snarks which do not contain perfect pseudo-matching whose contraction leads to planar/K5-minor-free/SUD-K5-minor-free graphs

In the following we will provide a collection of all snarks with up to 32 vertices that do not contain a planarizing perfect pseudo-matching. For the definition of this property and also the terminology which will be used in the following see [1]. The algorithm used to check the properties is described in [2]. Furthermore, a collection of all snarks with up to 32 vertices provided by the House of Graphs was used.

The following table lists for each snark size (number of vertices) from 26 to 32 the total number of such snarks, the number of snarks which do not have a planarizing perfect pseudo-matching but do have a perfect pseudo-matching whose contraction leads to a K5-minor-free graph [no pppm], the number of snarks which do not have a perfect pseudo matching whose contraction leads to a K5-minor-free graph but have one whose contraction leads to a SUD-K5-minor-free graph [no k5mfppm], and the number of snarks which do not have a perfect pseudo matching whose contraction leads to a SUD-K5-minor-free graph but have one whose contraction leads to a graph containing a compatible circuit decomposition [no sk5mfppm].

You can download the list of all such snarks by pressing on the link of the appropriate cell. The graphs are listed one per line in the graph6 format, see Brendan McKay's website for a formal definition.

Every snark with up to 24 vertices contains a planarizing perfect pseudo-matching. Furthermore, all snarks with up to 32 vertices contain a perfect pseudo-matching whose contraction leads to a graph containinga compatible circuit decomposition.

size total number of snarks no pppm no k5mfppm no sk5mfppm
26 1297 2 0 0
28 12517 45 15 0
30 139854 933 578 33
32 1764950 24268 18537 1062
3 results
2019
[3]A Lower Bound for the Smallest Uniquely Hamiltonian Planar Graph with Minimum Degree Three
Benedikt Klocker, Herbert Fleischner, Günther R. Raidl
2019, Technical report AC-TR-19-007, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
2018
[2]A SAT Approach for Finding Sup-Transition-Minors
Benedikt Klocker, Herbert Fleischner, Günther Raidl
2018, Technical report AC-TR-18-010, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[1]A Model for Finding Transition-Minors
Benedikt Klocker, Herbert Fleischner, Günther Raidl
2018, Technical report AC-TR-18-009, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]

Anytime Algorithms For Solving the Longest Common Palindromic Subsequence Problem (LCPS):

Contact: Marko Djukanovic and/or Günther Raidl
Instances for the 2-LCPS problem can be found here.
The supplementary file of this research can be found here.

Battery Swapping Station Location Problem (BSSLP)

Contact: Thomas Jatschka, Günther Raidl
Instances for the EVTeC 2023 can be found here.

Service Point Distribution Problem (SPDP)

Contact: Thomas Jatschka, Günther Raidl
Instances for the EvoCOP 2019 can be found here.
Instances for the LOD 2019 are available here.
GPSPDP instances are available here.

Prize-Collecting Job Sequencing with One Common and Multiple Secondary Resources (PC-JSOCMSR)

Contact: Matthias Horn, Johannes Maschler, Günther Raidl
Instances for the PC-JSOCMSR problem can be found here. For details on the instance format see the included description. The following publications consider these benchmark instances: 6 results

2021
[6]Multivalued Decision Diagrams for Prize-Collecting Job Sequencing with One Common and Multiple Secondary Resources
Johannes Maschler, Günther R. Raidl
Annals of Operations Research, volume 302, pages 407–531, 2021.
[bibtex] [pdf]
[5]A*-based Construction of Decision Diagrams for a Prize-Collecting Scheduling Problem
Matthias Horn, Johannes Maschler, Günther R. Raidl, Elina Rönnberg
Computers & Operations Research, volume 126, number 105125, 2021.
Note: previous technical report version at https://www.ac.tuwien.ac.at/files/tr/ac-tr-18-011a.pdf
[bibtex] [doi]
[4]A* Search for Prize-Collecting Job Sequencing with One Common and Multiple Secondary Resources
Matthias Horn, Günther R. Raidl, Elina Rönnberg
Annals of Operations Research, volume 302, pages 477–501, 2021.
Note: previous technical report version at https://www.ac.tuwien.ac.at/files/tr/ac-tr-19-002.pdf
[bibtex] [pdf] [doi]
2019
[3]Multivalued Decision Diagrams for Prize-Collecting Job Sequencing with One Common and Multiple Secondary Resources
Johannes Maschler, Günther Raidl
2019, Technical report AC-TR-19-003, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
2018
[2]Multivalued Decision Diagrams for a Prize-Collecting Sequencing Problem
Johannes Maschler, Günther R. Raidl
PATAT 2018: Proceedings of the 12th International Conference of the Practice and Theory of Automated Timetabling, pages 375–397, 2018.
[bibtex] [pdf]
[1]An A* Algorithm for Solving a Prize-Collecting Sequencing Problem with One Common and Multiple Secondary Resources and Time Windows
Matthias Horn, Günther R. Raidl, Elina Rönnberg
PATAT 2018: Proceedings of the 12th International Conference of the Practice and Theory of Automated Timetabling, pages 235–256, 2018.
[bibtex] [pdf]

String Problems

The Longest Common Subsequence Problem (LCSP)

Contact: Marc Huber and/or Günther Raidl
Instances for LCSP (LOD 2021) can be found here.

The Longest Common Palindromic Subsequence Problem (LCPSP)

Contact: Marko Djukanovic and/or Günther Raidl
Instances for LCPSP (provided by Christian Blum ) can be found here.

The Constraint Longest Common Subsequence Problem (CLCSP)

Contact: Marc Huber and/or Günther Raidl
Instances for CLCSP (LOD 2021) can be found here.

The Shortest Common Supersequence Problem (SCSP)

Contact: Marc Huber and/or Günther Raidl
Instances and results for SCSP (EvoCOP 2022) can be found here.

Particle Therapy Patient Scheduling

Contact: Johannes Maschler, Martin Riedler, Günther Raidl

Particle Therapy Patient Scheduling Problem (PTPSP)

Instances for PTPSP can be found here. For details on the instance format and the applied preprocessing see the included description. The following publications consider these benchmark instances: 3 results

2018
[3]Particle Therapy Patient Scheduling with Limited Starting Time Variations of Daily Treatments
Johannes Maschler, Günther R. Raidl
International Transactions in Operational Research, 2018.
[bibtex] [pdf] [doi]
[2]Particle Therapy Patient Scheduling: Time Estimation for Scheduling Sets of Treatments
Johannes Maschler, Martin Riedler, Günther R. Raidl
Computer Aided Systems Theory – EUROCAST 2017, Part I, pages 364–372, 2018, Springer.
[bibtex] [pdf] [doi]
2017
[1]An Enhanced Iterated Greedy Metaheuristic for the Particle Therapy Patient Scheduling Problem
Johannes Maschler, Thomas Hackl, Martin Riedler, Günther R. Raidl
Proceedings of the 12th Metaheuristics International Conference, pages 465–474, 2017.
[bibtex] [pdf]

First instances for PTPSP including a description of the used file format can be found here. Updated instances and results can be found here. These benchmark instances have been considered by 1 result

2016
[1]Particle Therapy Patient Scheduling: First Heuristic Approaches
Johannes Maschler, Martin Riedler, Markus Stock, Günther R. Raidl
PATAT 2016: Proceedings of the 11th International Conference of the Practice and Theory of Automated Timetabling, pages 223–244, 2016.
[bibtex] [pdf]

Simplified Intraday Particle Therapy Patient Scheduling Problem (SI-PTPSP)

The instances can be found here. For details on the instance format see the included README file.
The following publication considers these test instances:
1 result

2020
[1]An Iterative Time-Bucket Refinement Algorithm for a High-Resolution Resource-Constrained Project Scheduling Problem
Martin Riedler, Thomas Jatschka, Johannes Maschler, Günther R. Raidl
International Transactions in Operational Research, jan 2020.
[bibtex] [pdf] [doi]

Job Sequencing with One Common and Multiple Secondary Resources (JSOCMSR)

Instances for the JSOCMSR can be found here

Districting and Routing Problem for Security Control

Contact: Benjamin Biesinger, Christian Kloimüllner

Instances for the published results can be found here.

Dial-a-Ride Problem

Contact: Martin Riedler, Günther Raidl

Instances including a description of the used file format can be found here.

Network Design Problem with Relays

Contact: Markus Leitner, Ivana Ljubic, Martin Riedler, Mario Ruthmair

Instances including a description of the used file format can be found here.
Further instances from the literature can be found at https://sites.psu.edu/auk3/research/test-problems/.

Directed Network Design Problem with Relays

Contact: Markus Leitner, Ivana Ljubic, Martin Riedler, Mario Ruthmair

The modified instances by Cabral et al. are available here.
Our newly generated Euclidean instances can be found here.
The used instance format is described in format-description.txt.
The instances by Konak can be retrieved at https://sites.psu.edu/auk3/research/test-problems/.

Rooted Delay-Constrained Minimum Spanning Tree Problems

Contact: Mario Ruthmair

  • C++-Code for reading instance format
  • complete instance graphs with 100, 200, 500, 1000 nodes and random integer edge costs and delays in [1,99]

Consensus Tree Problem

Contact: Sandro Pirkwieser

  • instances based on real data
  • new artificially generated instances
  • new artificially generated small instances

Periodic Vehicle Routing Problem with Time Windows

Contact: Sandro Pirkwieser

We created instances based on Solomon's VRPTW instances with 100 customers:

  • planning period of four days
  • planning period of six days
  • planning period of eight days

Of the newly created instances with a planning horizon of four days we generated smaller ones for the exact approaches:

  • having 36 customers
  • having 50 customers

Periodic Vehicle Routing Problem and Periodic Traveling Salesman Problem

Contact: Sandro Pirkwieser

We created larger instances having 336 to 576 customers and a planning horizon of four or six days

  • instances for the pvrp
  • instances for the ptsp

Vehicle Routing Problem with Compartments

Contact: Sandro Pirkwieser

  • benchmark instances of Derigs et al. available here
  • modified petrol benchmark instances of Derigs et al. exhibiting a harder packing subproblem

Bi-level Vehicle Routing Problem

Contact: Günther R. Raidl, Bin Hu

  • Full result table of "Boosting an Exact Logic-Based Benders Decomposition Approach by Variable Neighborhood Search"

Balancing Bicycle Sharing System (BBSS) Problem

Contact: Christian Kloimüllner, Petrina Papazek

The homepage of the Balancing Bicylce Sharing System (BBSS) project can be found here.

Our instances are based on real data from Citybike Wien. We got information about 92 stations which contain fill levels at different time in the system, capacity of stations, geographic coordinates, and traveling times between stations.

We constructed instances which contain:

  • capacity,
  • initial fill level,
  • target fill level of stations,
  • traveling times, and
  • (user) demand values for dynamic rebalancing.

Furthermore, our instances have different size of stations, namely, 10, 20, 30, 60, 90, 120, 180, 240, 300, 400, 500, 600 and 700. Thus, we got a set of artificial stations from our partner, the AIT (Austrian Institute of Technology), which extend the real data we got from Citybike Wien. In particular, we choose the stations for our instances randomly from a set of 92 real stations plus 664 artificial stations.

For the following set of instances we took a snapshot from the system of Citybike Wien to derive initial fill levels for the stations. Furthermore, we set the target value of stations to be 50% of their capacities. We used exactly one depot and also one travel time matrix and the demands for the stations are derived randomly for eight different time points.

  • bench2: Benchmark instances based on data from Citybike Wien (used in [1-3, 6])

In EVOCOP-2013 results we list complete computational results based on bench 2 for comparing our auxilary algroithms for deriving loading operations described in [2013,4].

The next benchmark instances contain (user) demand values for the real stations which we got from our partner, the AIT. For the artificial stations we calculated random demand values according to a Beta distribution.

Moreover, we adopted the initial fill levels and target values. The initial fill levels for the artificial stations have been calculated the same way like we did it for the demands, i.e., such that the distribution of the fill levels for artificial stations is similar to that one of the real stations. The target values were set according to their demand. For stations with a high bike demand we set the target value to be 75% of the stations capacity, for stations with a high slot demand to 25% and if both, the bike- as well as the slot demand, are similar we set their target value to 50% of the capacity.

Additionally, we provided four different travel time matrices which show the traveling time at 4:30 am, 8:00 am, 12:00 pm, as well as 6:15 pm.

  • bench3: Benchmark instances with advanced initial and target fill levels and time-varying travel times (used in [4,5])

Publications using these benchmark instances

7 results
2019
[7]Algorithmic Approaches for Optimization Problems in Bike Sharing and Security Control
Christian Kloimüllner
mar 2019, PhD thesis, Institute of Logic and Computation, TU Wien.
Note: supervised by Günther R. Raidl
[bibtex] [pdf]
2015
[6]PILOT, GRASP, and VNS Approaches for the Static Balancing of Bicycle Sharing Systems
Marian Rainer-Harbach, Petrina Papazek, Günther R. Raidl, Bin Hu, Christian Kloimüllner
Journal of Global Optimization, volume 63, number 3, pages 597-629, 2015, Springer.
[bibtex] [pdf] [doi]
2014
[5]Balancing Bicycle Sharing Systems: An Analysis of Path Relinking and Recombination within a GRASP Hybrid
Petrina Papazek, Christian Kloimüllner, Bin Hu, Günther R. Raidl
Parallel Problem Solving from Nature – PPSN XIII (Thomas Bartz-Beielstein, Jürgen Branke, Bogdan Filipic, Jim Smith, eds.), volume 8672 of LNCS, pages 792–801, 2014, Springer.
[bibtex] [pdf] [doi]
[4]Balancing Bicycle Sharing Systems: An Approach for the Dynamic Case
Christian Kloimüllner, Petrina Papazek, Bin Hu, Günther R. Raidl
Evolutionary Computation in Combinatorial Optimization – EvoCOP 2014 (Christian Blum, Gabriela Ochoa, eds.), volume 8600 of LNCS, pages 73–84, 2014, Springer.
[bibtex] [pdf] [doi]
2013
[3]Balancing Bicycle Sharing Systems: A Variable Neighborhood Search Approach
Marian Rainer-Harbach, Petrina Papazek, Bin Hu, Günther R. Raidl
Evolutionary Computation in Combinatorial Optimisation – 13th European Conference, EvoCOP 2013 (M. Middendorf, C. Blum, eds.), volume 7832 of LNCS, pages 121-132, 2013, Springer.
[bibtex] [pdf]
[2]Balancing Bicycle Sharing Systems: Improving a VNS by Efficiently Determining Optimal Loading Operations
Günther R. Raidl, Bin Hu, Marian Rainer-Harbach, Petrina Papazek
Hybrid Metaheuristics, 8th Int. Workshop, HM 2013 (M. J. Blesa, others, eds.), volume 7919 of LNCS, pages 130–143, 2013, Springer.
[bibtex] [pdf]
[1]A PILOT/VND/GRASP Hybrid for the Static Balancing of Public Bicycle Sharing Systems
Petrina Papazek, Günther R. Raidl, Marian Rainer-Harbach, Bin Hu
Computer Aided Systems Theory – EUROCAST 2013 (Roberto Moreno-Díaz, Franz Pichler, Alexis Quesada-Arencibia, eds.), volume 8111 of LNCS, pages 372–379, 2013, Springer.
[bibtex] [pdf]

Mulitmodal Home-Healthcare Scheduling (MHS) Problem

Contact: Günther R. Raidl, Matthias Prandtstetter

  • Appendix to "Metaheuristics for Solving a Multimodal Home-Healthcare Scheduling Problem", submitted to Central European Journal of Operations Research
  • Benchmark instances based on real world data

Competitive Facility Location Problems

Contact: Benjamin Biesinger, Bin Hu, Günther R. Raidl

  • Benchmark instances with 50 and 100 customers for the Leader-Follower Facility Location Problem with Proportional Customer Behavior
  • Benchmark instances with 150 and 200 customers for the Discrete (r|p)-Centroid Problem (RPCP)
  • Full result tables of "A Hybrid Genetic Algorithm with Solution Archive for the Discrete (r|p)-Centroid Problem", accepted by Journal of Heuristics

Multi Layer Hierarchical Ring Network Design Problem

Contact: Christian Schauer, Günther R. Raidl

  • Benchmark instances ranging from 22 to 439 nodes
  • All results for the Multi-Commodity Flow Based Mixed Integer Linear Programming Approach

Two Dimensional Pre-Marshalling Problem

Contact: Günther Raidl Benchmark instances for the Two Dimensional Pre-Marshalling Problem (2D-PMP) with 4,6,8,10,12,and 14 columns width, 4 stacks height and 50% and 75% fullness ratio. By combining these parameters we obtain a total of 612=12 categories of instances. Each category contains 50 instances. The instances were generated using the instance generator found at (https://sites.google.com/site/gciports/premarshalling-problem/bay-generator) provided by:

  • Exposito-Izquierdo, C., Melian-Batista, B., Moreno-Vega, M.: Pre-marshalling problem: Heuristic solution method and instances generator. Expert Systems with Applications 39(9) (2012) 8337-8349

File names are encoded using the following key: instance_w_h_c_x.txt

  • w - width
  • h - height
  • c - number of containers within bay (defined by fullness ratio)
  • x - instance number within category

Generalized Vehicle Routing Problem with Stochastic Demands

Contact: Benjamin Biesinger, Bin Hu, Günther R. Raidl

  • Benchmark instances for the Generalized Vehicle Routing Problem with Stochastic Demands based on the instances for the GVRP (http://www.personal.soton.ac.uk/tb12v07/gvrp.html) using the same format. In the demand section the expected demand d for each cluster is listed along with a number x. This number determines the possible demand values which are given by D={d-ceil(x*d),...,d+ceil(x*d)} and each demand value has equal probability 1 / |D|.
  • Full result tables of "A Variable Neighborhood Search for the Generalized Vehicle Routing Problem with Stochastic Demands", accepted by the EvoCOP 2015 coference.

Virtual Network Mapping Problem

(Contact: Johannes Inführ, Günther Raidl)

Benchmark Set for the VNMP

  • VNMP Benchmark Set

Solutions Achieved by Heuristic and Exact Approaches

  • CH and LS
  • VND, GRASP, MA, VNS
  • CP
  • ILP

Benchmark Set for the VNMP-DRL

  • VNMP-DRL Benchmark Set
  • VNMP-DRL Benchmark Set Updated

Data Supplement for EvoCOP 2013

  • Data Supplement

News

  • Best Paper Award at SOFSEM 2025

    Best Paper Award at SOFSEM 2025

    2025-01-23
    Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, and Martin Nöllenburg received the Best Paper Award for their paper …Read More »
  • Markus Wallinger receives Award of Excellence for his PhD Thesis

    Markus Wallinger receives Award of Excellence for his PhD Thesis

    2024-12-05
    Our former group member Markus Wallinger won the Award of Excellence by the Federal Ministry for Education, Science and Research. …Read More »
  • Thomas Depian receives State Prize for his Master’s Thesis

    Thomas Depian receives State Prize for his Master’s Thesis

    2024-11-21
    Our group member Thomas Depian won the Appreciation Award given by the Federal Ministry for Education, Science and Research. This …Read More »
  • Best Paper Award at GECCO 2024 for M. Bresich, G. Raidl, and S. Limmer

    Best Paper Award at GECCO 2024 for M. Bresich, G. Raidl, and S. Limmer

    2024-07-24
    Maria Bresich, Günther Raidl, and Steffen Limmer received the best paper award at the 2024 Genetic and Evolutionary Computation Conference …Read More »
  • Welcome to our Feodor Lynen Fellow Dr. Frank Sommer

    Welcome to our Feodor Lynen Fellow Dr. Frank Sommer

    2024-06-14
    On June 1, 2024, Dr. Frank Sommer has joined the Algorithms and Complexity group with a prestigious Feodor Lynen postdoc …Read More »

News archive

All news for 2015, 2016, 2017, 2018, 2019, 2020, 2021, 2022, 2023 and 2024.
TU Wien Informatics
Offenlegung (§25 MedienG) Inhaber der Website ist das Institut für Logic and Computation an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. – Disclaimer – Datenschutzerklärung
Log in requires cookies.