Explaining Propagators for String Edit Distance Constraints

Felix Winter, Nysret Musliu, Peter J. Stuckey

Abstract

This paper introduces a novel global constraint propagator for string edit distance designed for Lazy Clause Generation (LCG) solvers. By combining an optimistic dynamic programming approach with a backward-traversal explanation algorithm, the authors significantly enhance the solving of NP-hard combinatorial problems like paint shop scheduling and the median string problem. The proposed method demonstrates superior pruning power and learning capabilities, leading to faster optimality proofs and higher solution quality compared to existing Constraint Programming (CP) and Mixed Integer Programming (MIP) techniques.

Introduction

The string edit distance, or Levenshtein distance, measures the minimum number of operations—insertions, deletions, or substitutions—required to transform one string into another. While calculating this for fixed strings is a standard dynamic programming task, the problem becomes NP-hard when the strings themselves are decision variables in a larger optimization context. Applications range from bioinformatics to industrial scheduling, such as car paint shop optimization where setup costs between production rounds must be minimized. Existing methods often rely on inefficient decompositions or Integer Linear Programming (ILP) models that fail to capture the problem's inherent structure. This work addresses the gap by providing a global propagator for CP solvers that can reason about edit distance and learn from search failures.

Methodology

The researchers propose a two-pronged approach to improve solver performance:

Global Propagator ($ED$)

Rather than decomposing the edit distance into numerous small constraints, the authors treat it as a single global unit. The propagator employs an "optimistic" version of the standard dynamic programming matrix. If a character in a string is not yet fixed, the propagator assumes the best possible outcome (e.g., a zero-cost match if the variable domains overlap). This allows the solver to compute a valid lower bound on the edit distance even for partially decided strings, enabling early pruning of suboptimal search branches.

Explanation Algorithm

The core innovation lies in the explanation algorithm for LCG. When a solver encounters an impossible path, it must identify the specific constraints responsible. The authors developed a backward-traversal algorithm that starts from the end of the DP matrix to find the minimal set of character assignments forcing a high edit distance. These explanations are converted into logical clauses (nogoods), allowing the solver to prune large sections of the search tree in subsequent steps.

Experimental Evaluation

The method was evaluated on two NP-hard problems: Paint Shop Scheduling (12 real-world instances) and the Median String Problem (250 instances).

Performance on the Median String Problem

The "CP + Propagator" approach significantly outperformed alternatives. It identified 227 optimal solutions out of 250, compared to 208 for the best MIP model and 180 for standard CP. As shown in Figure 1, the solution quality of the proposed method consistently aligns with the best known costs.

Comparison of solution cost ratios across CP, CP + Propagator, and MIP methods.

Computational efficiency also saw dramatic improvements. The average runtime for median string tests dropped from 143.16 seconds (MIP) to 61.61 seconds with the new propagator. Furthermore, the proposed method was the fastest to prove optimality in every instance where all tested methods reached an optimal solution.

Relative time required to prove optimality for various solvers.

Paint Shop Scheduling

In the paint shop benchmarks, the global propagator found better upper bounds and proved optimality significantly faster than previous state-of-the-art decomposition methods, demonstrating its robustness across different problem domains.

Conclusion and Future Work

The introduction of a global propagator with an explanation mechanism provides a powerful tool for solving string-based optimization problems. By leveraging the structure of the dynamic programming matrix for both pruning and learning, the proposed method achieves state-of-the-art results. Future research will explore "backwards pruning," using the edit distance upper bound to directly constrain the domains of the string variables, which could further enhance performance in highly constrained scenarios.

Summary updated

Abstract

The computation of string similarity measures has been thoroughly studied in the scientific literature and has applications in a wide variety of different areas. One of the most widely used measures is the so called string edit distance which captures the number of required edit operations to transform a string into another given string. Although polynomial time algorithms are known for calculating the edit distance between two strings, there also exist NP-hard problems from practical applications like scheduling or computational biology that constrain the minimum edit distance between arrays of decision variables. In this work, we propose a novel global constraint to formulate restrictions on the minimum edit distance for such problems. Furthermore, we describe a propagation algorithm and investigate an explanation strategy for an edit distance constraint propagator that can be incorporated into state of the art lazy clause generation solvers. 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.
BibTeX
@inproceedings{winter2020explaining,
  author = {Felix Winter and Nysret Musliu and Peter J. Stuckey},
  title = {{Explaining Propagators for String Edit Distance Constraints}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i02.5530},
}
Figure