Incremental Symmetry Breaking Constraints for Graph Search Problems
Authors: Avraham Itzhakov, Michael Codish1536-1543
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We demonstrate our approach through its application on two hard graph search problems. |
| Researcher Affiliation | Academia | Avraham Itzhakov, Michael Codish Department of Computer Science Ben-Gurion University of the Negev {itzhakoa, mcodish}@cs.bgu.ac.il |
| Pseudocode | Yes | Algorithm 1 Compute a compact complete symmetry break for X {R, C}, Y {lex, imp} |
| Open Source Code | Yes | The symmetry breaking constraints described in this paper can be obtained from www. cs.bgu.ac.il/ mcodish/Papers/Tools/incremental SBC. |
| Open Datasets | No | The paper focuses on graph search problems and enumerating objects with certain properties, which does not involve traditional machine learning training datasets. No specific training dataset is mentioned. |
| Dataset Splits | No | The paper describes a graph search and enumeration problem, not a machine learning task that utilizes validation datasets. No dataset splits for validation are mentioned. |
| Hardware Specification | Yes | All computations were performed on a cluster of servers, each with 56 Intel Xeon E5-2620 cores and 256GB of RAM memory, clocked at 2 GHz. |
| Software Dependencies | Yes | The computations described in this paper are performed using the finite-domain constraint compiler BEE (Metodi, Codish, and Stuckey 2013) which compiles constraints to a CNF, and solves it applying an underlying SAT solver (we use Glucose 4.0 (Audemard and Simon )). |
| Experiment Setup | Yes | Each SAT instance is run on a single thread. We impose a 24 hour timeout on each instance. |