Solver-Independent Large Neighbourhood Search View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2018-08-23

AUTHORS

Jip J. Dekker , Maria Garcia de la Banda , Andreas Schutt , Peter J. Stuckey , Guido Tack

ABSTRACT

The combination of large neighbourhood search (LNS) methods with complete search methods has proved to be very effective. By restricting the search to (small) areas around an existing solution, the complete method is often able to quickly improve its solutions. However, developing such a combined method can be time-consuming: While the model of a problem can be expressed in a high-level solver-independent language, the LNS search strategies typically need to be implemented in the search language of the target constraint solvers. In this paper we show how we can simplify this process by (a) extending constraint modelling languages to support solver-independent LNS search definitions, and (b) defining small solver extensions that allow solvers to implement these solver-independent LNS searches. Modellers can then implement an LNS search to be executed in any extended solver, by simply using the modelling language constructs. Experiments show that the resulting LNS searches only introduce a small overhead compared to direct implementations in the search language of the underlying solvers. More... »

PAGES

81-98

Book

TITLE

Principles and Practice of Constraint Programming

ISBN

978-3-319-98333-2
978-3-319-98334-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-98334-9_6

DOI

http://dx.doi.org/10.1007/978-3-319-98334-9_6

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1106284287


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Data61, CSIRO, Melbourne, Australia", 
          "id": "http://www.grid.ac/institutes/grid.425461.0", 
          "name": [
            "Monash University, Melbourne, Australia", 
            "Data61, CSIRO, Melbourne, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dekker", 
        "givenName": "Jip J.", 
        "id": "sg:person.012137355413.18", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012137355413.18"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Monash University, Melbourne, Australia", 
          "id": "http://www.grid.ac/institutes/grid.1002.3", 
          "name": [
            "Monash University, Melbourne, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "de la Banda", 
        "givenName": "Maria Garcia", 
        "id": "sg:person.016350443307.93", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016350443307.93"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Data61, CSIRO, Melbourne, Australia", 
          "id": "http://www.grid.ac/institutes/grid.425461.0", 
          "name": [
            "Data61, CSIRO, Melbourne, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Schutt", 
        "givenName": "Andreas", 
        "id": "sg:person.012207644265.98", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012207644265.98"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Data61, CSIRO, Melbourne, Australia", 
          "id": "http://www.grid.ac/institutes/grid.425461.0", 
          "name": [
            "Monash University, Melbourne, Australia", 
            "Data61, CSIRO, Melbourne, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Stuckey", 
        "givenName": "Peter J.", 
        "id": "sg:person.012243374043.93", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012243374043.93"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Data61, CSIRO, Melbourne, Australia", 
          "id": "http://www.grid.ac/institutes/grid.425461.0", 
          "name": [
            "Monash University, Melbourne, Australia", 
            "Data61, CSIRO, Melbourne, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tack", 
        "givenName": "Guido", 
        "id": "sg:person.01235032467.07", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01235032467.07"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2018-08-23", 
    "datePublishedReg": "2018-08-23", 
    "description": "The combination of large neighbourhood search (LNS) methods with complete search methods has proved to be very effective. By restricting the search to (small) areas around an existing solution, the complete method is often able to quickly improve its solutions. However, developing such a combined method can be time-consuming: While the model of a problem can be expressed in a high-level solver-independent language, the LNS search strategies typically need to be implemented in the search language of the target constraint solvers. In this paper we show how we can simplify this process by (a) extending constraint modelling languages to support solver-independent LNS search definitions, and (b) defining small solver extensions that allow solvers to implement these solver-independent LNS searches. Modellers can then implement an LNS search to be executed in any extended solver, by simply using the modelling language constructs. Experiments show that the resulting LNS searches only introduce a small overhead compared to direct implementations in the search language of the underlying solvers.", 
    "editor": [
      {
        "familyName": "Hooker", 
        "givenName": "John", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-98334-9_6", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-98333-2", 
        "978-3-319-98334-9"
      ], 
      "name": "Principles and Practice of Constraint Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "search language", 
      "search method", 
      "large neighborhood search method", 
      "large neighborhood search", 
      "complete search method", 
      "neighborhood search method", 
      "modelling language", 
      "constraint solver", 
      "language constructs", 
      "neighborhood search", 
      "small overhead", 
      "direct implementation", 
      "extended solver", 
      "complete method", 
      "search strategy", 
      "language", 
      "solver", 
      "search", 
      "overhead", 
      "modelers", 
      "implementation", 
      "combined method", 
      "method", 
      "solution", 
      "extension", 
      "definition", 
      "model", 
      "experiments", 
      "process", 
      "strategies", 
      "area", 
      "constructs", 
      "combination", 
      "paper", 
      "problem"
    ], 
    "name": "Solver-Independent Large Neighbourhood Search", 
    "pagination": "81-98", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1106284287"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-98334-9_6"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-98334-9_6", 
      "https://app.dimensions.ai/details/publication/pub.1106284287"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:44", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_236.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-98334-9_6"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-98334-9_6'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-98334-9_6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-98334-9_6'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-98334-9_6'


 

This table displays all metadata directly associated to this object as RDF triples.

127 TRIPLES      23 PREDICATES      60 URIs      53 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-98334-9_6 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N8cdaf1fd171040ea85317e59e8deda9a
4 schema:datePublished 2018-08-23
5 schema:datePublishedReg 2018-08-23
6 schema:description The combination of large neighbourhood search (LNS) methods with complete search methods has proved to be very effective. By restricting the search to (small) areas around an existing solution, the complete method is often able to quickly improve its solutions. However, developing such a combined method can be time-consuming: While the model of a problem can be expressed in a high-level solver-independent language, the LNS search strategies typically need to be implemented in the search language of the target constraint solvers. In this paper we show how we can simplify this process by (a) extending constraint modelling languages to support solver-independent LNS search definitions, and (b) defining small solver extensions that allow solvers to implement these solver-independent LNS searches. Modellers can then implement an LNS search to be executed in any extended solver, by simply using the modelling language constructs. Experiments show that the resulting LNS searches only introduce a small overhead compared to direct implementations in the search language of the underlying solvers.
7 schema:editor Na0ddae09cb074919a52ac27a7f7400d3
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nea9b855016314f4097a74b16d60725ee
12 schema:keywords area
13 combination
14 combined method
15 complete method
16 complete search method
17 constraint solver
18 constructs
19 definition
20 direct implementation
21 experiments
22 extended solver
23 extension
24 implementation
25 language
26 language constructs
27 large neighborhood search
28 large neighborhood search method
29 method
30 model
31 modelers
32 modelling language
33 neighborhood search
34 neighborhood search method
35 overhead
36 paper
37 problem
38 process
39 search
40 search language
41 search method
42 search strategy
43 small overhead
44 solution
45 solver
46 strategies
47 schema:name Solver-Independent Large Neighbourhood Search
48 schema:pagination 81-98
49 schema:productId N639e279f370648559363502ac1155961
50 Nc83c66ba9bf14eccb61a1ce5918a3ee4
51 schema:publisher Ncac3dc07742f490897db8d24faa1c57b
52 schema:sameAs https://app.dimensions.ai/details/publication/pub.1106284287
53 https://doi.org/10.1007/978-3-319-98334-9_6
54 schema:sdDatePublished 2022-05-20T07:44
55 schema:sdLicense https://scigraph.springernature.com/explorer/license/
56 schema:sdPublisher N6637cbef35b74665bebf50df26a58364
57 schema:url https://doi.org/10.1007/978-3-319-98334-9_6
58 sgo:license sg:explorer/license/
59 sgo:sdDataset chapters
60 rdf:type schema:Chapter
61 N59ca684d56764749aa999fcd75925d02 rdf:first sg:person.016350443307.93
62 rdf:rest Ncd4e5a1afa7d46ef8f414a1cea02a698
63 N5f1329ad63a74649995541c503915845 schema:familyName Hooker
64 schema:givenName John
65 rdf:type schema:Person
66 N639e279f370648559363502ac1155961 schema:name dimensions_id
67 schema:value pub.1106284287
68 rdf:type schema:PropertyValue
69 N6637cbef35b74665bebf50df26a58364 schema:name Springer Nature - SN SciGraph project
70 rdf:type schema:Organization
71 N745c0082d21b4ad397dcf72b3245e80e rdf:first sg:person.012243374043.93
72 rdf:rest Nf583d589d8e047209074dbd646480627
73 N8cdaf1fd171040ea85317e59e8deda9a rdf:first sg:person.012137355413.18
74 rdf:rest N59ca684d56764749aa999fcd75925d02
75 Na0ddae09cb074919a52ac27a7f7400d3 rdf:first N5f1329ad63a74649995541c503915845
76 rdf:rest rdf:nil
77 Nc83c66ba9bf14eccb61a1ce5918a3ee4 schema:name doi
78 schema:value 10.1007/978-3-319-98334-9_6
79 rdf:type schema:PropertyValue
80 Ncac3dc07742f490897db8d24faa1c57b schema:name Springer Nature
81 rdf:type schema:Organisation
82 Ncd4e5a1afa7d46ef8f414a1cea02a698 rdf:first sg:person.012207644265.98
83 rdf:rest N745c0082d21b4ad397dcf72b3245e80e
84 Nea9b855016314f4097a74b16d60725ee schema:isbn 978-3-319-98333-2
85 978-3-319-98334-9
86 schema:name Principles and Practice of Constraint Programming
87 rdf:type schema:Book
88 Nf583d589d8e047209074dbd646480627 rdf:first sg:person.01235032467.07
89 rdf:rest rdf:nil
90 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
91 schema:name Information and Computing Sciences
92 rdf:type schema:DefinedTerm
93 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
94 schema:name Artificial Intelligence and Image Processing
95 rdf:type schema:DefinedTerm
96 sg:person.012137355413.18 schema:affiliation grid-institutes:grid.425461.0
97 schema:familyName Dekker
98 schema:givenName Jip J.
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012137355413.18
100 rdf:type schema:Person
101 sg:person.012207644265.98 schema:affiliation grid-institutes:grid.425461.0
102 schema:familyName Schutt
103 schema:givenName Andreas
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012207644265.98
105 rdf:type schema:Person
106 sg:person.012243374043.93 schema:affiliation grid-institutes:grid.425461.0
107 schema:familyName Stuckey
108 schema:givenName Peter J.
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012243374043.93
110 rdf:type schema:Person
111 sg:person.01235032467.07 schema:affiliation grid-institutes:grid.425461.0
112 schema:familyName Tack
113 schema:givenName Guido
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01235032467.07
115 rdf:type schema:Person
116 sg:person.016350443307.93 schema:affiliation grid-institutes:grid.1002.3
117 schema:familyName de la Banda
118 schema:givenName Maria Garcia
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016350443307.93
120 rdf:type schema:Person
121 grid-institutes:grid.1002.3 schema:alternateName Monash University, Melbourne, Australia
122 schema:name Monash University, Melbourne, Australia
123 rdf:type schema:Organization
124 grid-institutes:grid.425461.0 schema:alternateName Data61, CSIRO, Melbourne, Australia
125 schema:name Data61, CSIRO, Melbourne, Australia
126 Monash University, Melbourne, Australia
127 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...