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
Generic incremental algorithms for local search
RISE - Research Institutes of Sweden, ICT, SICS.
2007 (English)In: Constraints, ISSN 1383-7133, E-ISSN 1572-9354, Vol. 12, 293-324 p.Article in journal (Refereed) Published
Abstract [en]

When a new (global) constraint is introduced in local search, measures for the penalty and variable conflicts of that constraint must be defined, and incremental algorithms for maintaining these measures must be implemented. These are complicated and time-consuming tasks, which clearly reduces the productivity of the local-search practitioner. We introduce a generic scheme that, from a description of a constraint in monadic existential second-order logic extended with counting, automatically gives penalty and variable-conflict measures for such a constraint, as well as incremental algorithms for maintaining these measures. We prove that our variable-conflict measure for a variable x is lower-bounded by the maximum penalty decrease that may be achieved by only changing the value of x, as well as upper bounded by the penalty measure. Without these properties, the local search performance may degrade. We also demonstrate the usefulness of the approach by replacing a built-in global constraint by a modelled version, while still obtaining competitive results in terms of runtime and robustness. This is especially attractive when a particular (global) constraint is not built in.

Place, publisher, year, edition, pages
2007, 1. Vol. 12, 293-324 p.
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:ri:diva-23572DOI: 10.1007/s10601-007-9021-0OAI: oai:DiVA.org:ri-23572DiVA: diva2:1042648
Available from: 2016-10-31 Created: 2016-10-31 Last updated: 2017-07-28Bibliographically 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
In the same journal
Constraints
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 6 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.26.0