Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1]
Generating Weighted MAX-2-SAT Instances with Frustrated Loops: an RBM Case Study
Authors: Yan Ru Pei, Haik Manukian, Massimiliano Di Ventra
JMLR 2020 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this study, we focus on generating n n RBM instances (equal number of visible and hidden spins) using the random-loop algorithm (see algorithm 1) and the structured-loop algorithm (see algorithm 2). An RBM instance can be generated with three parameters: the size of the system n, the frustration index f (see Section 4.4), and the loop density ρ, where the loop density is defined as the ratio between the number of loops and the size of the system. To study the hardness of the generated instance, we use simulated annealing (SA) (Kirkpatrick et al., 1983) as a powerful stochastic optimizer to solve the generated instances of different parameter triplets {n, f, ρ}, and we record the number of sweeps it takes for the solver to find the ground state (see Section 6.1). The SA algorithm performs directly on the problem in the original RBM form (see Section 2.3). For testing the performance of a general MAX-SAT solver, one can easily convert the problem into the corresponding MAX-2-SAT form. |
| Researcher Affiliation | Academia | Yan Ru Pei EMAIL Haik Manukian EMAIL Massimiliano Di Ventra EMAIL Department of Physics University of California, San Diego 9500 Gilman Drive, La Jolla, California 92093-0319, USA |
| Pseudocode | Yes | Algorithm 1 Random Frustrated-Loop Algorithm... Algorithm 2 Structured Frustrated-Loop Algorithm... Algorithm 3 Simulated Annealing on RBMs |
| Open Source Code | Yes | The MATLAB implementation of both algorithms are available in the Github repository Pea Brane/Ising-Simulation. A MATLAB implementation of the random and structured loop algorithm is available in the Github repository Pea Brane/Ising-Simulation, which also includes the code for the SA solver used to perform the hardness measurement. |
| Open Datasets | No | The paper focuses on generating synthetic MAX-2-SAT instances with frustrated loops, which are then used for experimental evaluation. It does not utilize or provide access information for any pre-existing, publicly available datasets. |
| Dataset Splits | No | The paper describes generating instances on the fly for evaluation, stating: 'For each tuple {n, ρ}, we generated 10,000 different instances and solve them with SA to estimate the sample distribution of Ntot...' and 'For each {n, f, ρ} triple, 10000 RBM instances are generated independently to ensure accurate percentile statistics.' This process does not involve fixed training/test/validation splits of a static dataset. |
| Hardware Specification | Yes | For each generated instance, the solver is run on a single core of an AMD EPYC 7401 24-core processor. |
| Software Dependencies | No | The MATLAB implementation of both algorithms are available in the Github repository Pea Brane/Ising-Simulation. While MATLAB is mentioned, no specific version number for MATLAB or any specific libraries with their versions are provided, which is necessary for reproducible software dependencies. |
| Experiment Setup | Yes | The SA solver we implement uses a linearly increasing β schedule from 0.01 to log(n), such that the excited states are suppressed as 1/n (White, 1984). This schedule is scaled by a factor of 1/ρ in the high density regime to compensate for the increase in the magnitudes of weights (see Section I). ... In the second iteration, we then use the optimal value of Nsweep properly optimized at the hardness peak to derive more accurately the following fitting function Nsweep = (1.29n2 33.1n + 1664) (41.4f3 11.7f2 + 1.06f 0.018). |