Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • 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
Revisiting constraint-directed search
RISE, Swedish ICT, SICS. Computer Systems Laboratory.
Number of Authors: 3
2009 (English)In: Information and Computation, Vol. 207, 438-457 p.Article in journal (Refereed) Published
Abstract [en]

In constraint-based local search the solutions are described declaratively by a conjunction of (often high-level) constraints. In this article we show that this opens up new ideas for constraint-directed search. For a constraint we introduce three neighbourhoods, where the penalty for that constraint alone is decreasing, increasing, or unchanged. We give specialised algorithms for common constraints that efficiently implement these neighbourhoods. Further, we give a general algorithm that implements these neighbourhoods from specifications of constraints in monadic existential second-order logic. Finally, we show how common constraint-directed local search algorithms are often easier to express using these neighbourhoods.

Place, publisher, year, edition, pages
2009, 1. Vol. 207, 438-457 p.
Keyword [en]
Constraint-based local search, Constraint-directed search, Monadic existential second-order logic
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:ri:diva-23485DOI: 10.1016/j.ic.2008.12.001OAI: oai:DiVA.org:ri-23485DiVA: diva2:1042561
Available from: 2016-10-31 Created: 2016-10-31Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full texthttp

Search in DiVA

By author/editor
Pearson, Justin
By organisation
SICS
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 5 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • 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
v. 2.27.0