uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Underestimating the cost of a soft constraint is dangerous: Revisiting the edit-distance based soft regular constraint
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. (ASTRA)
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. (ASTRA)
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. (ASTRA)
2013 (English)In: Journal of Heuristics, ISSN 1381-1231, E-ISSN 1572-9397, Vol. 19, no 5, p. 729-756Article in journal (Refereed) Published
Abstract [en]

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, p. 729-756
Keyword [en]
constraint programming, soft regular constraint, edit distance, network flows, dynamic programming
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-195699DOI: 10.1007/s10732-013-9222-1ISI: 000325021400001OAI: oai:DiVA.org:uu-195699DiVA, id: diva2:608201
Funder
Swedish Research Council, 2007-6445Swedish Research Council, 2011-6133
Available from: 2013-02-26 Created: 2013-02-26 Last updated: 2018-01-11Bibliographically approved
In thesis
1. Constraints for Membership in Formal Languages under Systematic Search and Stochastic Local Search
Open this publication in new window or tab >>Constraints for Membership in Formal Languages under Systematic Search and Stochastic Local Search
2013 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis focuses on constraints for membership in formal languages under both the systematic search and stochastic local search approaches to constraint programming (CP). Such constraints are very useful in CP for the following three reasons: They provide a powerful tool for user-level extensibility of CP languages. They are very useful for modelling complex work shift regulation constraints, which exist in many shift scheduling problems. In the analysis, testing, and verification of string-manipulating programs, string constraints often arise. We show in this thesis that CP solvers with constraints for membership in formal languages are much more suitable than existing solvers used in tools that have to solve string constraints. In the stochastic local search approach to CP, we make the following two contributions: We introduce a stochastic method of maintaining violations for the regular constraint and extend our method to the automaton constraint with counters. To improve the usage of constraints for which there exists no known constant-time algorithm for neighbour evaluation, we introduce a framework of using solution neighbourhoods, and give an efficient algorithm of constructing a solution neighbourhood for the regular constraint. In the systematic search approach to CP, we make the following two contributions: We show that there may be unwanted consequences when using a propagator that may underestimate a cost of a soft constraint, as the propagator may guide the search to incorrect (non-optimum) solutions to an over-constrained problem. We introduce and compare several propagators that compute correctly the cost of the edit-distance based soft-regular constraint. We show that the context-free grammar constraint is useful and introduce an improved propagator for it.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2013. p. 74
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1027
Keyword
constraint programming, regular constraint, automaton constraint, context-free grammar constraint, solution neighbourhood, counter automaton
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:uu:diva-196347 (URN)978-91-554-8617-4 (ISBN)
Public defence
2013-04-26, Room 2446, Polacksbacken, Lägerhyddsvägen 2, Uppsala, 13:00 (English)
Opponent
Supervisors
Available from: 2013-03-26 Created: 2013-03-08 Last updated: 2018-01-11Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

He, JunFlener, PierrePearson, Justin

Search in DiVA

By author/editor
He, JunFlener, PierrePearson, Justin
By organisation
Computing Science
In the same journal
Journal of Heuristics
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 454 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf