Faster and Better Simple Temporal Problems
Authors: Dario Ostuni, Alice Raffaele, Romeo Rizzi, Matteo Zavatteri11913-11920
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We show the practical competitiveness of our approach through a proof-of-concept implementation and an experimental evaluation involving also state-of-the-art SMT solvers. |
| Researcher Affiliation | Academia | 1University of Verona, Department of Computer Science, Strada Le Grazie 15, 37134 Verona (Italy) 2University of Trento, Department of Mathematics, Via Sommarive 14, 38123 Povo (Italy) |
| Pseudocode | Yes | Algorithm 1: ESTP solver |
| Open Source Code | Yes | 2https://github.com/CALIPSO-UniVR/estp-aaai2021 |
| Open Datasets | No | We have defined four classes of instances, including hard instances to provide various degrees of hardness and require maximal work from all approaches, thus highlighting their performance. These instances are generated rather than being a publicly available dataset with concrete access information. |
| Dataset Splits | No | The paper describes generating instances for evaluation but does not specify any training, validation, or test dataset splits or proportions. |
| Hardware Specification | Yes | Table 1: Benchmark environment. CPU Intel Core i7-6700K @ 4.00GHz RAM 64 GB DDR4 @ 2133MHz SSD Samsung SSD 850 EVO 1TB |
| Software Dependencies | Yes | Table 1: Benchmark environment. OS Arch Linux kernel 5.8.5-zen CXXFLAGS -O3 -march=native -std=c++17 |
| Experiment Setup | Yes | We have defined four classes of instances, including hard instances to provide various degrees of hardness and require maximal work from all approaches, thus highlighting their performance. We consider hard all consistent instances with deep shortest-paths trees and all inconsistent instances with few and long negative cycles. All classes of instances contain an Hamiltonian zero-weight cycle, thus ensuring hardness for consistent instances. Moreover, all instances contain random edges, in proportion 8 to 1 with respect to the number of nodes, which do not form any negative cycle. Here follows a description of the four classes: H000 are consistent instances with no further additions; H001 are inconsistent instances with a single negative cycle with length equal to the 1% of the number of nodes; H025 are inconsistent instances with a single negative cycle with length equal to the 25% of the number of nodes; H100 are inconsistent instances with a single Hamiltonian negative cycle. Starting with number of nodes n = 32, for each class 8 instances are generated and solved by each variant, computing the average of the running times. At the end of each iteration, n is multiplied by 2 and the process is repeated, until the execution takes more than 100 seconds. |