Problem Instances
Contents
- 1 Problem Instances
- 1.1 Searching for Stable Fixed-Edge Graphs - Instances and Source Code
- 1.2 Snarks which do not contain perfect pseudo-matching whose contraction leads to planar/K5-minor-free/SUD-K5-minor-free graphs
- 1.3 Anytime Algorithms For Solving the Longest Common Palindromic Subsequence Problem (LCPS):
- 1.4 Service Point Distribution Problem (SPDP)
- 1.5 Prize-Collecting Job Sequencing with One Common and Multiple Secondary Resources (PC-JSOCMSR)
- 1.6 The Longest Common Palindromic Subsequence Problem
- 1.7 Particle Therapy Patient Scheduling
- 1.8 Job Sequencing with One Common and Multiple Secondary Resources (JSOCMSR)
- 1.9 Districting and Routing Problem for Security Control
- 1.10 Dial-a-Ride Problem
- 1.11 Network Design Problem with Relays
- 1.12 Directed Network Design Problem with Relays
- 1.13 Rooted Delay-Constrained Minimum Spanning Tree Problems
- 1.14 Consensus Tree Problem
- 1.15 Periodic Vehicle Routing Problem with Time Windows
- 1.16 Periodic Vehicle Routing Problem and Periodic Traveling Salesman Problem
- 1.17 Vehicle Routing Problem with Compartments
- 1.18 Bi-level Vehicle Routing Problem
- 1.19 Balancing Bicycle Sharing System (BBSS) Problem
- 1.20 Mulitmodal Home-Healthcare Scheduling (MHS) Problem
- 1.21 Competitive Facility Location Problems
- 1.22 Multi Layer Hierarchical Ring Network Design Problem
- 1.23 Two Dimensional Pre-Marshalling Problem
- 1.24 Generalized Vehicle Routing Problem with Stochastic Demands
- 1.25 Virtual Network Mapping Problem
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 |
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.
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:
5 results
| 2021 | |
| [5] | A*-based Construction of Decision Diagrams for a Prize-Collecting Scheduling Problem Computers & Operations Research, volume 126, pages 105125, 2021. Note: previous technical report version at https://www.ac.tuwien.ac.at/files/tr/ac-tr-18-011a.pdf |
| 2020 | |
| [4] | A* Search for Prize-Collecting Job Sequencing with One Common and Multiple Secondary Resources Annals of Operations Research, 2020. Note: previous technical report version at https://www.ac.tuwien.ac.at/files/tr/ac-tr-19-002.pdf |
| 2019 | |
| [3] | Multivalued Decision Diagrams for Prize-Collecting Job Sequencing with One Common and Multiple Secondary Resources 2019, Technical report AC-TR-19-003, Algorithms and Complexity Group, TU Wien. |
| 2018 | |
| [2] | Multivalued Decision Diagrams for a Prize-Collecting Sequencing Problem PATAT 2018: Proceedings of the 12th International Conference of the Practice and Theory of Automated Timetabling, pages 375–397, 2018. |
| [1] | An A* Algorithm for Solving a Prize-Collecting Sequencing Problem with One Common and Multiple Secondary Resources and Time Windows PATAT 2018: Proceedings of the 12th International Conference of the Practice and Theory of Automated Timetabling, pages 235–256, 2018. |
The Longest Common Palindromic Subsequence Problem
Contact: Marko Djukanovic and/or Günther Raidl
Instances for LCPSP (provided by Christian Blum ) 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
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
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 International Transactions in Operational Research, jan 2020. |
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
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
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 resultsMulitmodal 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)
