Research map / Learning theory and algorithms / Combinatorial and search optimization
Explaining Propagators for String Edit Distance Constraints
Felix Winter, Nysret Musliu, Peter Stuckey
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace edit distance decomposition with global propagator | CP model · Paint shop I3 | runtime to prove optimality (s): 3.76 -> 1.75 | Improved |
| replace edit distance decomposition with global propagator | CP model · Paint shop I4 | runtime to prove optimality (s): 178.46 -> 25.05 | Improved |
| replace edit distance decomposition with global propagator | CP model · Paint shop I8 | runtime to prove optimality (s): 2915.83 -> 445.43 | Improved |
| replace decomposition with global propagator | CP model · Paint shop I7, I9, I10 | best objective within 1 h: 1046 -> 1040 | Improved |
| remove lazy clause learning, with global propagator vs decomposition (ablation) | CP model · Paint shop I1 | best objective within 1 h: 3282 -> 775* | Improved |
| remove lazy clause learning, with global propagator vs decomposition (ablation) | CP model · Paint shop I4 | best objective within 1 h: — -> 918* | Improved |
| replace decomposition with global propagator | CP model · Median string | average runtime (s): 219.12 -> 61.61 | Improved |
| replace decomposition with global propagator | CP model · Median string | # optimal solutions found: 180 -> 227 | Improved |
| global propagator CP versus MIP formulation | CP+global · Median string | average runtime (s): 143.16 -> 61.61 | Improved |
| global propagator CP versus MIP formulation | CP+global · Median string | # best found solutions: 213 -> 246 | Improved |
| CP with decomposition versus MIP formulation | CP decomposition · Median string | # optimal solutions found: 208 -> 180 | Hurt |
| CP with decomposition versus MIP formulation | CP decomposition · Median string | proof time | No clear effect |
Closest papers by meaning
- Wasserstein Distance Constraint and Parameter Sparsification for Batched and Iterative Knowledge Editing (AAAI 2025 · similarity 0.82)
- StringLLM: Understanding the String Processing Capability of Large Language Models (ICLR 2025 · similarity 0.81)
- AlphaEdit: Null-Space Constrained Knowledge Editing for Language Models (ICLR 2025 · similarity 0.80)
- Repeat After Me: Transformers are Better than State Space Models at Copying (ICML 2024 · similarity 0.80)
- Frontier Language Models Struggle to Copy: Text Can Be Better Viewed in 2D (NeurIPS 2026 · similarity 0.80)
- The Impact of Literal Sorting on Cardinality Constraint Encodings (AAAI 2025 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
