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
Inferring variable conflicts for local search
RISE - Research Institutes of Sweden, ICT, SICS.
2006 (English)In: Proceedings of CP'06, Springer-Verlag , 2006, 2, Vol. 4204, 665-669 p.Conference paper, (Refereed)
Abstract [en]

For efficiency reasons, neighbourhoods in local search are often shrunk by only considering moves modifying variables that actually contribute to the overall penalty. These are known as conflicting variables. We propose a new definition for measuring the conflict of a variable in a model and apply it to the set variables of models expressed in existential second-order logic extended with counting (EMSO). Such a variable conflict can be automatically and incrementally evaluated. Furthermore, this measure is lower-bounded by an intuitive conflict measure, and upper-bounded by the penalty of the model. We also demonstrate the usefulness of the approach by replacing a built-in global constraint by an EMSO version thereof, while still obtaining competitive results.

Place, publisher, year, edition, pages
Springer-Verlag , 2006, 2. Vol. 4204, 665-669 p.
Series
LNCS, 4204
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:ri:diva-23565DOI: 10.1007/11889205_47OAI: oai:DiVA.org:ri-23565DiVA: diva2:1042641
Conference
CP'06, 24-29 Sept 2006, Nantes, France
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
Flener, Pierre
By organisation
SICS
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 4 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