Solving Quantum-Inspired Perfect Matching Problems via Tutte-Theorem-Based Hybrid Boolean Constraints
Authors: Moshe Y. Vardi, Zhiwei Zhang
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Empirical results demonstrate that our encoding, in suitable languages with advanced SAT solvers, scales significantly better than a number of competing approaches on constrained-matching benchmarks. |
| Researcher Affiliation | Academia | Moshe Y. Vardi , Zhiwei Zhang Rice University, Houston, TX, USA {vardi, zhiwei}@rice.edu |
| Pseudocode | Yes | Algorithm 1: Enum-Blossom: An Enumeration Based Algorithm for FORALL-PMVC |
| Open Source Code | Yes | The implementations and benchmarks can be found in the Git Hub repository: https://github.com/zzwonder/PMVC. |
| Open Datasets | No | The paper describes generating its own benchmark graphs: 'We generate two types of graphs. First, for n {6, 8, , 40} we generate graphs that satisfy Dicke(n, n/2) (see Section 3 and Figure 2), where the size of legal coloring grows exponentially as n increases. Second, we fix n = 36 and generate graphs that satisfy Dicke(36, k) with k {1, 2, , 18}.' and 'Graphs in this benchmark are obtained by removing edges from graphs that satisfy the Dicke state.' However, no concrete access information (link, DOI, citation) is provided for these generated datasets. |
| Dataset Splits | No | The paper describes evaluating algorithms on generated benchmark graphs but does not specify any training, validation, or test dataset splits for model training or evaluation reproducibility. |
| Hardware Specification | Yes | All experiments were run on single CPU cores of a Linux cluster at 2.60-GHz and with 16 GB of RAM. |
| Software Dependencies | No | The paper mentions various software tools used (e.g., Clingo, Kissat, Clasp, Lin PB, networkx, Dep QBF) along with citations to their respective papers. However, it does not explicitly state the specific version numbers of these software dependencies as used in their experiments. For example, it says 'we use Clingo [Gebser et al., 2019]' instead of 'Clingo version X.Y'. |
| Experiment Setup | No | The paper describes general optimization techniques applied to its Tutte encoding and sets a time limit of 1000 seconds for problem instances, but it does not provide specific hyperparameter values or detailed system-level training settings for the various solvers used (e.g., learning rates, batch sizes, specific solver configurations beyond the time limit). |