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

Problem Instances

Contents

  • 1 Problem Instances
    • 1.1 EV Fleet Charging and Allocation Problem
    • 1.2 EV charging scheduling problem with SOC-dependent maximum charging power
    • 1.3 Searching for Stable Fixed-Edge Graphs - Instances and Source Code
    • 1.4 Snarks which do not contain perfect pseudo-matching whose contraction leads to planar/K5-minor-free/SUD-K5-minor-free graphs
    • 1.5 Anytime Algorithms For Solving the Longest Common Palindromic Subsequence Problem (LCPS):
    • 1.6 Battery Swapping Station Location Problem (BSSLP)
    • 1.7 Service Point Distribution Problem (SPDP)
    • 1.8 Prize-Collecting Job Sequencing with One Common and Multiple Secondary Resources (PC-JSOCMSR)
    • 1.9 String Problems
      • 1.9.1 The Longest Common Subsequence Problem (LCSP)
      • 1.9.2 The Longest Common Palindromic Subsequence Problem (LCPSP)
      • 1.9.3 The Constraint Longest Common Subsequence Problem (CLCSP)
      • 1.9.4 The Shortest Common Supersequence Problem (SCSP)
    • 1.10 Particle Therapy Patient Scheduling
      • 1.10.1 Particle Therapy Patient Scheduling Problem (PTPSP)
      • 1.10.2 Simplified Intraday Particle Therapy Patient Scheduling Problem (SI-PTPSP)
    • 1.11 Job Sequencing with One Common and Multiple Secondary Resources (JSOCMSR)
    • 1.12 Districting and Routing Problem for Security Control
    • 1.13 Dial-a-Ride Problem
    • 1.14 Network Design Problem with Relays
    • 1.15 Directed Network Design Problem with Relays
    • 1.16 Rooted Delay-Constrained Minimum Spanning Tree Problems
    • 1.17 Consensus Tree Problem
    • 1.18 Periodic Vehicle Routing Problem with Time Windows
    • 1.19 Periodic Vehicle Routing Problem and Periodic Traveling Salesman Problem
    • 1.20 Vehicle Routing Problem with Compartments
    • 1.21 Bi-level Vehicle Routing Problem
    • 1.22 Balancing Bicycle Sharing System (BBSS) Problem
    • 1.23 Mulitmodal Home-Healthcare Scheduling (MHS) Problem
    • 1.24 Competitive Facility Location Problems
    • 1.25 Multi Layer Hierarchical Ring Network Design Problem
    • 1.26 Two Dimensional Pre-Marshalling Problem
    • 1.27 Generalized Vehicle Routing Problem with Stochastic Demands
    • 1.28 Virtual Network Mapping Problem
      • 1.28.1 Benchmark Set for the VNMP
        • 1.28.1.1 Solutions Achieved by Heuristic and Exact Approaches
      • 1.28.2 Benchmark Set for the VNMP-DRL
      • 1.28.3 Data Supplement for EvoCOP 2013

EV Fleet Charging and Allocation Problem

Contact: Johannes Varga and/or Günther Raidl

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

  • New FWF ESPRIT Postdocs

    New FWF ESPRIT Postdocs

    2022-11-09
    Leroy Chew and Alexis de Colnet just joined the Algorithms and Complexity group as PIs of their own FWF ESPRIT …Read More »
  • Best student paper award at DIAGRAMS 2022

    Best student paper award at DIAGRAMS 2022

    2022-10-01
    Alexander Dobler received the Best Student Paper Award at the 13th International Conference on the Theory and Application of Diagrams …Read More »
  • Robert Ganian promoted to Associate Professor

    Robert Ganian promoted to Associate Professor

    2022-07-01
    Effective as of today, Robert Ganian is promoted to a tenured Associate Professor at the Algorithms and Complexity group. Congratulations, …Read More »
  • Best paper award at EvoCOP 2022

    Best paper award at EvoCOP 2022

    2022-05-24
    Jonas Mayerhofer, Markus Kirchweger, Marc Huber, and Günther Raidl received the best paper award for their work A Beam Search …Read More »
  • New PhD: Guangping Li

    New PhD: Guangping Li

    2022-05-13
    Guangping Li successfully defended her PhD thesis “An Algorithmic Study of Practical Map Labeling” on May 13, 2022. Congratulations, Dr. …Read More »

News archive

All news for 2015, 2016, 2017, 2018, 2019, 2020, 2021 and 2022.
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.