Explaining Propagators for String Edit Distance Constraints
Authors: Felix Winter, Nysret Musliu, Peter Stuckey1676-1683
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experimental results show that the proposed propagator is able to significantly improve the performance of existing exact methods regarding solution quality and computation speed for benchmark problems from the literature. |
| Researcher Affiliation | Academia | 1Christian Doppler Laboratory for Artificial Intelligence and Optimization for Planning and Scheduling DBAI, TU Wien, Vienna, Austria {winter,musliu}@dbai.tuwien.ac.at 2Monash University, Melbourne, Australia peter.stuckey@monash.edu |
| Pseudocode | Yes | Algorithm 1: Propagate Edit Distance Lower Bound; Algorithm 2: Generate disequalities for minimal explanation |
| Open Source Code | No | The paper does not provide any specific links or explicit statements about the availability of the source code for the methodology described. |
| Open Datasets | Yes | For our experiments we used 12 benchmarks instances that we have previously published (Winter et al. 2019).; We generated a large number of instances following the instance generation procedure that has been proposed in (Hayashida and Koyano 2016) to evaluate the performance of different exact solution approaches |
| Dataset Splits | No | The paper describes the instance generation process for the median string problem and mentions using 12 benchmark instances for the paint shop scheduling problem, but it does not specify any train, validation, or test dataset splits. |
| Hardware Specification | Yes | All of our experiments have been conducted on an Intel Xeon E5345 2.33 GHz CPU with 48 GB RAM, using a single CPU core. |
| Software Dependencies | Yes | We implemented the constraint propagation and explanation algorithms proposed in this paper for use with a recent version of the lazy clause generation solver Chuffed (Chu 2011).; We performed experiments with all of the 250 benchmark instances under a time limit of 10 minutes, using a recent version of the Chuffed solver (Chu 2011) for the CP model and the CP model that uses our propagator, as well as Gurobi 8.0.1 (Gurobi Optimization 2019) for experiments with the MIP model |
| Experiment Setup | Yes | For each of the instances we used the same programmed search strategies that have been used for the final experiments in (Winter and Musliu 2019). Afterwards, we ran the Chuffed solver with both the existing decomposition model and a model that uses the propagator proposed in this paper on all 12 instances within a time limit of 1 hour.; We generated a large number of instances following the instance generation procedure that has been proposed in (Hayashida and Koyano 2016)...Our instance generation routine considered different numbers of strings n = [2, 4, 6, 10, 15] as well as different maximum string lengths k = [3, 5, 8, 13, 20]. We used a simple alphabet consisting of 4 different characters Σ = {1, 2, 3, 4} to randomly generate 10 different instances for each of the possible |n k| configurations...We performed experiments with all of the 250 benchmark instances under a time limit of 10 minutes |