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
Solution neighbourhoods for constraint-directed local search
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)
2012 (English)In: Proc. 27th ACM Symposium on Applied Computing, New York: ACM Press, 2012, 74-79 p.Conference paper, Oral presentation only (Refereed)
Place, publisher, year, edition, pages
New York: ACM Press, 2012. 74-79 p.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-186863DOI: 10.1145/2245276.2245294ISBN: 978-1-4503-0857-1 (print)OAI: oai:DiVA.org:uu-186863DiVA: diva2:573123
Conference
SAC 2012, March 26-30, Riva del Garda, Italy
Available from: 2012-03-28 Created: 2012-11-29 Last updated: 2013-04-02Bibliographically 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. 74 p.
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 Science
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: 2014-07-21Bibliographically approved

Open Access in DiVA

No full text

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
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 474 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