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 and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
From Support Propagation to Belief Propagation in Constraint Programming
Authors: Gilles Pesant
JAIR 2019 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this section we attempt to answer several research questions empirically. All experiments were run on a cluster of dual core AMD Opteron 275 @ 2.2 GHz processors running Java SE 11 on Linux Cent OS 7.6 and our prototype was built on top of Mini CP 1.0. We use four combinatorial problems that can be modelled using the constraints from the previous section: Partial Latin Square, Cost-Constrained Rostering, Partial Magic Square, and Primes. |
| Researcher Affiliation | Academia | Gilles Pesant EMAIL Polytechnique Montréal, Montreal, Canada CIRRELT, Université de Montréal, Montreal, Canada |
| Pseudocode | Yes | Algorithm 1: IntVar.receiveMessage(v, µc x(v)) ... Algorithm 10: Sum.updateBelief() |
| Open Source Code | Yes | 1. Its current implementation is available at https://github.com/PesantGilles/MiniCPBP |
| Open Datasets | Yes | Partial Latin Square Problem An n n grid is partially filled with integers from {1, 2, . . . , n} and must be completed such that each integer appears exactly once per row and column (problem 67 of the CSPLib Jefferson, Miguel, Hnich, Walsh, & Gent, 1999). ... For Section 6.7 we use the challenging set of forty larger (n = 30) instances Latin Square/m1/gp from the XCSP3 collection of benchmark instances2. ... Partial Magic Square Problem An n n grid is partially filled with integers from {1, 2, . . . , n2} and must be completed such that each integer appears exactly once and such that the sum of the entries in each row, column, and main diagonal is the same (problem 19 of the CSPLib). ... Primes Problem We are asked to solve a sparse system of linear equalities over a given finite subset of the integers. We use the set of thirty-two instances Primes/m1/p10 from XCSP3, featuring 100 variables taking their value from subset {2, 3, . . . , 29} and between twenty and eighty linear equalities (i.e. weighted sum constraints) each over a relatively small subset of these variables. ... 2. http://www.xcsp.org |
| Dataset Splits | No | The paper describes generating instances or using benchmark instances (e.g., from CSPLib, XCSP3) rather than splitting a single dataset into train/test/validation sets. For example: "We randomly generated two sets of ten instances of size n = 10 with 50% (pls-10-50) and 55% (pls-10-55) free cells respectively, using the instance generator of (Gomes & Shmoys, 2002) with the balanced setting." It does not provide specific train/test/validation splits for these instances in the traditional sense. |
| Hardware Specification | Yes | All experiments were run on a cluster of dual core AMD Opteron 275 @ 2.2 GHz processors running Java SE 11 on Linux Cent OS 7.6 and our prototype was built on top of Mini CP 1.0. |
| Software Dependencies | Yes | All experiments were run on a cluster of dual core AMD Opteron 275 @ 2.2 GHz processors running Java SE 11 on Linux Cent OS 7.6 and our prototype was built on top of Mini CP 1.0. |
| Experiment Setup | Yes | We consider two parameters: the number of bp iterations and whether or not standard support propagation is applied before bp. We use the following two-way branching heuristic: max-strength assigns the variable-value pair exhibiting the largest positive difference between its marginal and the reciprocal of the domain size (i.e. its marginal strength) and disallows it upon backtracking. ... We set τ = 6, triggering approximate counting for alldifferent until enough variables are fixed to count exactly. We stop an individual run after one hour of computation time. |