Underestimating the cost of a soft constraint is dangerous: Revisiting the edit-distance based soft regular constraint
2013 (English)In: Journal of Heuristics, ISSN 1381-1231, E-ISSN 1572-9397, Vol. 19, no 5, 729-756 p.Article in journal (Refereed) Published
Many real-life problems are over-constrained, so that no solution satisfying all their constraints exists. Soft constraints, with costs denoting how much the constraints are violated, are used to solve these problems. We use the edit-distance based soft regular constraint as an example to show that a propagation algorithm that sometimes underestimates the cost may guide the search to incorrect (non-optimal) solutions to an over-constrained problem. To compute correctly the cost for the edit-distance based soft regular constraint, we present a quadratic-time propagation algorithm based on dynamic programming and a proof of its correctness. We also give an improved propagation algorithm using an idea of computing the edit distance between two strings, which may also be applied to other constraints with propagators based on dynamic programming. The asymptotic time complexity of our improved propagator is always at least as good as the one of our quadratic-time propagator, but significantly better when the edit distance is small. Our propagators achieve domain consistency on the problem variables and bounds consistency on the cost variable. Our method can also be adapted for the violation measure of the edit-distance based regular constraint for constraint-based local search.
Place, publisher, year, edition, pages
2013. Vol. 19, no 5, 729-756 p.
constraint programming, soft regular constraint, edit distance, network flows, dynamic programming
Research subject Computer Science
IdentifiersURN: urn:nbn:se:uu:diva-195699DOI: 10.1007/s10732-013-9222-1ISI: 000325021400001OAI: oai:DiVA.org:uu-195699DiVA: diva2:608201
FunderSwedish Research Council, 2007-6445Swedish Research Council, 2011-6133