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
Generating compound moves in local search by hybridisation with complete search
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.ORCID iD: 0000-0002-8032-5774
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.ORCID iD: 0000-0001-8730-4098
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
2019 (English)In: Integration of Constraint Programming, Artificial Intelligence, and Operations Research / [ed] L.-M. Rousseau and K. Stergiou, Springer, 2019, Vol. 11494, p. 95-111Conference paper, Published paper (Refereed)
Abstract [en]

A black-box local-search backend to a solving-technology-independent modelling language, such as MiniZinc, automatically infers from the structure of a declarative model for a satisfaction or optimisation problem a combination of a neighbourhood, heuristic, and meta-heuristic. These ingredients are then provided to a local-search solver, but are manually designed in a handcrafted local-search algorithm. However, such a backend can perform poorly due to model structure that is inappropriate for local search, for example when it considers moves modifying only variables that represent auxiliary information. Towards overcoming such inefficiency, we propose compound-move generation, an extension to local-search solvers that uses a complete-search solver in order to augment moves modifying non-auxiliary variables so that they also modify auxiliary ones. Since compound-move generation is intended to be applied to such models, we discuss how to identify them.

We present several refinements of compound-move generation and show its very positive impact on several third-party models. This helps reduce the unavoidable gap between black-box local search and local-search algorithms crafted by experts.

Place, publisher, year, edition, pages
Springer, 2019. Vol. 11494, p. 95-111
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 11494
National Category
Computer Sciences
Research subject
Computing Science
Identifiers
URN: urn:nbn:se:uu:diva-396494DOI: 10.1007/978-3-030-19212-9_7ISBN: 978-3-030-19212-9 (electronic)OAI: oai:DiVA.org:uu-396494DiVA, id: diva2:1370945
Conference
CPAIOR 2019, 4 – 7 June, Thessaloniki, Greece
Funder
Swedish Research Council, 2015-04910Available from: 2019-11-18 Created: 2019-11-18 Last updated: 2019-11-29Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Björdal, GustavFlener, PierrePearson, Justin

Search in DiVA

By author/editor
Björdal, GustavFlener, PierrePearson, Justin
By organisation
Computing Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

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