Core-Guided Model Reformulation View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2020-09-02

AUTHORS

Kevin Leo , Graeme Gange , Maria Garcia de la Banda , Mark Wallace

ABSTRACT

Constraint propagation and SAT solvers often underperform when dealing with optimisation problems that have an additive (or separable) objective function. The core-guided search introduced by MaxSAT solvers can overcome this weakness by detecting and exploiting cores: subsets of the objective components that cannot collectively take their lower bounds. This paper shows how to use the information collected during core-guided search, to reformulate the objective function for an entire class of problems (those captured by the problem model). The resulting (currently manual) method is examined on several case studies, with very promising results. More... »

PAGES

445-461

Book

TITLE

Principles and Practice of Constraint Programming

ISBN

978-3-030-58474-0
978-3-030-58475-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-58475-7_26

DOI

http://dx.doi.org/10.1007/978-3-030-58475-7_26

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Faculty of Information Technology, Monash University, Clayton, Australia", 
          "id": "http://www.grid.ac/institutes/grid.1002.3", 
          "name": [
            "Faculty of Information Technology, Monash University, Clayton, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Leo", 
        "givenName": "Kevin", 
        "id": "sg:person.01303145667.62", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01303145667.62"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Faculty of Information Technology, Monash University, Clayton, Australia", 
          "id": "http://www.grid.ac/institutes/grid.1002.3", 
          "name": [
            "Faculty of Information Technology, Monash University, Clayton, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gange", 
        "givenName": "Graeme", 
        "id": "sg:person.012611230125.03", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012611230125.03"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Faculty of Information Technology, Monash University, Clayton, Australia", 
          "id": "http://www.grid.ac/institutes/grid.1002.3", 
          "name": [
            "Faculty of Information Technology, Monash University, Clayton, 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": "Faculty of Information Technology, Monash University, Clayton, Australia", 
          "id": "http://www.grid.ac/institutes/grid.1002.3", 
          "name": [
            "Faculty of Information Technology, Monash University, Clayton, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wallace", 
        "givenName": "Mark", 
        "id": "sg:person.016566542221.14", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016566542221.14"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2020-09-02", 
    "datePublishedReg": "2020-09-02", 
    "description": "Constraint propagation and SAT solvers often underperform when dealing with optimisation problems that have an additive (or separable) objective function. The core-guided search introduced by MaxSAT solvers can overcome this weakness by detecting and exploiting cores: subsets of the objective components that cannot collectively take their lower bounds. This paper shows how to use the information collected during core-guided search, to reformulate the objective function for an entire class of problems (those captured by the problem model). The resulting (currently manual) method is examined on several case studies, with very promising results.", 
    "editor": [
      {
        "familyName": "Simonis", 
        "givenName": "Helmut", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-58475-7_26", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-030-58474-0", 
        "978-3-030-58475-7"
      ], 
      "name": "Principles and Practice of Constraint Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "objective function", 
      "constraint propagation", 
      "SAT solvers", 
      "MaxSAT solvers", 
      "additive objective function", 
      "optimization problem", 
      "promising results", 
      "solver", 
      "lower bounds", 
      "model reformulation", 
      "case study", 
      "search", 
      "entire class", 
      "information", 
      "bounds", 
      "reformulation", 
      "core", 
      "objective components", 
      "weakness", 
      "method", 
      "subset", 
      "class", 
      "function", 
      "components", 
      "results", 
      "propagation", 
      "study", 
      "problem", 
      "paper"
    ], 
    "name": "Core-Guided Model Reformulation", 
    "pagination": "445-461", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1130642763"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-58475-7_26"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-58475-7_26", 
      "https://app.dimensions.ai/details/publication/pub.1130642763"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:45", 
    "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_305.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-58475-7_26"
  }
]
 

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-030-58475-7_26'

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-030-58475-7_26'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-58475-7_26'

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-030-58475-7_26'


 

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

110 TRIPLES      23 PREDICATES      54 URIs      47 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-58475-7_26 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nf979aae4bcff462cad9511471c180f0f
4 schema:datePublished 2020-09-02
5 schema:datePublishedReg 2020-09-02
6 schema:description Constraint propagation and SAT solvers often underperform when dealing with optimisation problems that have an additive (or separable) objective function. The core-guided search introduced by MaxSAT solvers can overcome this weakness by detecting and exploiting cores: subsets of the objective components that cannot collectively take their lower bounds. This paper shows how to use the information collected during core-guided search, to reformulate the objective function for an entire class of problems (those captured by the problem model). The resulting (currently manual) method is examined on several case studies, with very promising results.
7 schema:editor N019d09a49c8d4d39aeb87336f6836c9e
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N8248f2bffa1e44e08d7352a89f1bb241
12 schema:keywords MaxSAT solvers
13 SAT solvers
14 additive objective function
15 bounds
16 case study
17 class
18 components
19 constraint propagation
20 core
21 entire class
22 function
23 information
24 lower bounds
25 method
26 model reformulation
27 objective components
28 objective function
29 optimization problem
30 paper
31 problem
32 promising results
33 propagation
34 reformulation
35 results
36 search
37 solver
38 study
39 subset
40 weakness
41 schema:name Core-Guided Model Reformulation
42 schema:pagination 445-461
43 schema:productId Na1a32d2e969c47caac5927b226fd4de1
44 Nbdac872a1659400dba000934c720f1ec
45 schema:publisher Nc9fa531df9cb4c66aec05703211f0c7d
46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1130642763
47 https://doi.org/10.1007/978-3-030-58475-7_26
48 schema:sdDatePublished 2022-05-20T07:45
49 schema:sdLicense https://scigraph.springernature.com/explorer/license/
50 schema:sdPublisher Nbb46591062d54de4b6b5fe15c8c5b7be
51 schema:url https://doi.org/10.1007/978-3-030-58475-7_26
52 sgo:license sg:explorer/license/
53 sgo:sdDataset chapters
54 rdf:type schema:Chapter
55 N019d09a49c8d4d39aeb87336f6836c9e rdf:first N685da9284b4b4ab7a319537b1ce65786
56 rdf:rest rdf:nil
57 N2475661c471a4c8cbf1870e75ab7a8d2 rdf:first sg:person.016350443307.93
58 rdf:rest Ne8f342ec01a24c61b5702770056b6ff6
59 N630b067bc7054549acf8455676e2e45b rdf:first sg:person.012611230125.03
60 rdf:rest N2475661c471a4c8cbf1870e75ab7a8d2
61 N685da9284b4b4ab7a319537b1ce65786 schema:familyName Simonis
62 schema:givenName Helmut
63 rdf:type schema:Person
64 N8248f2bffa1e44e08d7352a89f1bb241 schema:isbn 978-3-030-58474-0
65 978-3-030-58475-7
66 schema:name Principles and Practice of Constraint Programming
67 rdf:type schema:Book
68 Na1a32d2e969c47caac5927b226fd4de1 schema:name doi
69 schema:value 10.1007/978-3-030-58475-7_26
70 rdf:type schema:PropertyValue
71 Nbb46591062d54de4b6b5fe15c8c5b7be schema:name Springer Nature - SN SciGraph project
72 rdf:type schema:Organization
73 Nbdac872a1659400dba000934c720f1ec schema:name dimensions_id
74 schema:value pub.1130642763
75 rdf:type schema:PropertyValue
76 Nc9fa531df9cb4c66aec05703211f0c7d schema:name Springer Nature
77 rdf:type schema:Organisation
78 Ne8f342ec01a24c61b5702770056b6ff6 rdf:first sg:person.016566542221.14
79 rdf:rest rdf:nil
80 Nf979aae4bcff462cad9511471c180f0f rdf:first sg:person.01303145667.62
81 rdf:rest N630b067bc7054549acf8455676e2e45b
82 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
83 schema:name Information and Computing Sciences
84 rdf:type schema:DefinedTerm
85 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
86 schema:name Computation Theory and Mathematics
87 rdf:type schema:DefinedTerm
88 sg:person.012611230125.03 schema:affiliation grid-institutes:grid.1002.3
89 schema:familyName Gange
90 schema:givenName Graeme
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012611230125.03
92 rdf:type schema:Person
93 sg:person.01303145667.62 schema:affiliation grid-institutes:grid.1002.3
94 schema:familyName Leo
95 schema:givenName Kevin
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01303145667.62
97 rdf:type schema:Person
98 sg:person.016350443307.93 schema:affiliation grid-institutes:grid.1002.3
99 schema:familyName de la Banda
100 schema:givenName Maria Garcia
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016350443307.93
102 rdf:type schema:Person
103 sg:person.016566542221.14 schema:affiliation grid-institutes:grid.1002.3
104 schema:familyName Wallace
105 schema:givenName Mark
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016566542221.14
107 rdf:type schema:Person
108 grid-institutes:grid.1002.3 schema:alternateName Faculty of Information Technology, Monash University, Clayton, Australia
109 schema:name Faculty of Information Technology, Monash University, Clayton, Australia
110 rdf:type schema:Organization
 




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


...