Triangle-based consistencies for cost function networks View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2017-04

AUTHORS

Hiep Nguyen, Christian Bessiere, Simon de Givry, Thomas Schiex

ABSTRACT

Cost Function Networks (aka Weighted CSP) allow to model a variety of problems, such as optimization of deterministic and stochastic graphical models including Markov random Fields and Bayesian Networks. Solving cost function networks is thus an important problem for deterministic and probabilistic reasoning. This paper focuses on local consistencies which define essential tools to simplify Cost Function Networks, and provide lower bounds on their optimal solution cost. To strengthen arc consistency bounds, we follow the idea of triangle-based domain consistencies for hard constraint networks (path inverse consistency, restricted or max-restricted path consistencies), describe their systematic extension to cost function networks, study their relative strengths, define enforcing algorithms, and experiment with them on a large set of benchmark problems. On some of these problems, our improved lower bounds seem necessary to solve them. More... »

PAGES

230-264

References to SciGraph publications

Journal

TITLE

Constraints

ISSUE

2

VOLUME

22

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10601-016-9250-1

DOI

http://dx.doi.org/10.1007/s10601-016-9250-1

DIMENSIONS

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


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/0104", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Statistics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "name": [
            "MIAT, UR 875, Universit\u00e9 de Toulouse, INRA, Castanet-Tolosan, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nguyen", 
        "givenName": "Hiep", 
        "id": "sg:person.016341137430.49", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016341137430.49"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Montpellier", 
          "id": "https://www.grid.ac/institutes/grid.121334.6", 
          "name": [
            "University of Montpellier, Montpellier, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bessiere", 
        "givenName": "Christian", 
        "id": "sg:person.013164552637.20", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013164552637.20"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "MIAT, UR 875, Universit\u00e9 de Toulouse, INRA, Castanet-Tolosan, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Givry", 
        "givenName": "Simon de", 
        "id": "sg:person.016264131727.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016264131727.46"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "MIAT, UR 875, Universit\u00e9 de Toulouse, INRA, Castanet-Tolosan, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Schiex", 
        "givenName": "Thomas", 
        "id": "sg:person.01072303420.99", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01072303420.99"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/j.artint.2004.05.004", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004337524"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1026488509554", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010942827", 
          "https://doi.org/10.1023/a:1026488509554"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10601-005-2240-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017431728", 
          "https://doi.org/10.1007/s10601-005-2240-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10601-005-2240-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017431728", 
          "https://doi.org/10.1007/s10601-005-2240-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0017448", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018041561", 
          "https://doi.org/10.1007/bfb0017448"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.artint.2003.09.002", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021273787"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bioinformatics/btt374", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023371638"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1009812409930", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025752985", 
          "https://doi.org/10.1023/a:1009812409930"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.artint.2010.02.001", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038096395"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45349-0_30", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042748592", 
          "https://doi.org/10.1007/3-540-45349-0_30"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10601-007-9029-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044041135", 
          "https://doi.org/10.1007/s10601-007-9029-5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10601-016-9245-y", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046823138", 
          "https://doi.org/10.1007/s10601-016-9245-y"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.artint.2007.05.006", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048085317"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0165-0114(02)00134-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051570822"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1021/acs.jctc.5b00594", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1055098688"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/caia.1995.378792", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094455415"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1613/jair.3476", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1105689803"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2017-04", 
    "datePublishedReg": "2017-04-01", 
    "description": "Cost Function Networks (aka Weighted CSP) allow to model a variety of problems, such as optimization of deterministic and stochastic graphical models including Markov random Fields and Bayesian Networks. Solving cost function networks is thus an important problem for deterministic and probabilistic reasoning. This paper focuses on local consistencies which define essential tools to simplify Cost Function Networks, and provide lower bounds on their optimal solution cost. To strengthen arc consistency bounds, we follow the idea of triangle-based domain consistencies for hard constraint networks (path inverse consistency, restricted or max-restricted path consistencies), describe their systematic extension to cost function networks, study their relative strengths, define enforcing algorithms, and experiment with them on a large set of benchmark problems. On some of these problems, our improved lower bounds seem necessary to solve them.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s10601-016-9250-1", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1043977", 
        "issn": [
          "1383-7133", 
          "1572-9354"
        ], 
        "name": "Constraints", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "22"
      }
    ], 
    "name": "Triangle-based consistencies for cost function networks", 
    "pagination": "230-264", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "5d83828587d91b1be0b3c162a36b8e1f0ad7aeb8809a9218df4d37842a684579"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10601-016-9250-1"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1019627120"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10601-016-9250-1", 
      "https://app.dimensions.ai/details/publication/pub.1019627120"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T12:40", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000363_0000000363/records_70049_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs10601-016-9250-1"
  }
]
 

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/s10601-016-9250-1'

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/s10601-016-9250-1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10601-016-9250-1'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10601-016-9250-1'


 

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

143 TRIPLES      21 PREDICATES      43 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10601-016-9250-1 schema:about anzsrc-for:01
2 anzsrc-for:0104
3 schema:author N0a1a8c424f72444d9efefb475eeae91d
4 schema:citation sg:pub.10.1007/3-540-45349-0_30
5 sg:pub.10.1007/bfb0017448
6 sg:pub.10.1007/s10601-005-2240-3
7 sg:pub.10.1007/s10601-007-9029-5
8 sg:pub.10.1007/s10601-016-9245-y
9 sg:pub.10.1023/a:1009812409930
10 sg:pub.10.1023/a:1026488509554
11 https://doi.org/10.1016/j.artint.2003.09.002
12 https://doi.org/10.1016/j.artint.2004.05.004
13 https://doi.org/10.1016/j.artint.2007.05.006
14 https://doi.org/10.1016/j.artint.2010.02.001
15 https://doi.org/10.1016/s0165-0114(02)00134-3
16 https://doi.org/10.1021/acs.jctc.5b00594
17 https://doi.org/10.1093/bioinformatics/btt374
18 https://doi.org/10.1109/caia.1995.378792
19 https://doi.org/10.1613/jair.3476
20 schema:datePublished 2017-04
21 schema:datePublishedReg 2017-04-01
22 schema:description Cost Function Networks (aka Weighted CSP) allow to model a variety of problems, such as optimization of deterministic and stochastic graphical models including Markov random Fields and Bayesian Networks. Solving cost function networks is thus an important problem for deterministic and probabilistic reasoning. This paper focuses on local consistencies which define essential tools to simplify Cost Function Networks, and provide lower bounds on their optimal solution cost. To strengthen arc consistency bounds, we follow the idea of triangle-based domain consistencies for hard constraint networks (path inverse consistency, restricted or max-restricted path consistencies), describe their systematic extension to cost function networks, study their relative strengths, define enforcing algorithms, and experiment with them on a large set of benchmark problems. On some of these problems, our improved lower bounds seem necessary to solve them.
23 schema:genre research_article
24 schema:inLanguage en
25 schema:isAccessibleForFree true
26 schema:isPartOf N38b7335eaf714dfe80a8639d8df73abd
27 N4214feea39424e71b11d83fdb0406fbe
28 sg:journal.1043977
29 schema:name Triangle-based consistencies for cost function networks
30 schema:pagination 230-264
31 schema:productId N3b4683a2dacd4a4887acf66e79da1e2a
32 Nc53bca950d1c4b8bb6112124bc313ec2
33 Nc6529c041e67464899f8fd69c23aa1f4
34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019627120
35 https://doi.org/10.1007/s10601-016-9250-1
36 schema:sdDatePublished 2019-04-11T12:40
37 schema:sdLicense https://scigraph.springernature.com/explorer/license/
38 schema:sdPublisher N0ec557d174064711a6a5847afa5ea517
39 schema:url https://link.springer.com/10.1007%2Fs10601-016-9250-1
40 sgo:license sg:explorer/license/
41 sgo:sdDataset articles
42 rdf:type schema:ScholarlyArticle
43 N0a1a8c424f72444d9efefb475eeae91d rdf:first sg:person.016341137430.49
44 rdf:rest Nef6c37b3c4ba48ed99c27bab3f651812
45 N0ec557d174064711a6a5847afa5ea517 schema:name Springer Nature - SN SciGraph project
46 rdf:type schema:Organization
47 N2dd683af207740218aee7eaefca61f57 schema:name MIAT, UR 875, Université de Toulouse, INRA, Castanet-Tolosan, France
48 rdf:type schema:Organization
49 N38b7335eaf714dfe80a8639d8df73abd schema:issueNumber 2
50 rdf:type schema:PublicationIssue
51 N3b4683a2dacd4a4887acf66e79da1e2a schema:name readcube_id
52 schema:value 5d83828587d91b1be0b3c162a36b8e1f0ad7aeb8809a9218df4d37842a684579
53 rdf:type schema:PropertyValue
54 N4214feea39424e71b11d83fdb0406fbe schema:volumeNumber 22
55 rdf:type schema:PublicationVolume
56 N4c560185ffa143ee9acb9ac9df181b74 rdf:first sg:person.016264131727.46
57 rdf:rest Nffa919ee9e384441b059491b91ed1c67
58 Nbee181d34cfb47fab07cf2a0072e36d2 schema:name MIAT, UR 875, Université de Toulouse, INRA, Castanet-Tolosan, France
59 rdf:type schema:Organization
60 Nc53bca950d1c4b8bb6112124bc313ec2 schema:name dimensions_id
61 schema:value pub.1019627120
62 rdf:type schema:PropertyValue
63 Nc5f0e06980af439c822f69b5e48344f5 schema:name MIAT, UR 875, Université de Toulouse, INRA, Castanet-Tolosan, France
64 rdf:type schema:Organization
65 Nc6529c041e67464899f8fd69c23aa1f4 schema:name doi
66 schema:value 10.1007/s10601-016-9250-1
67 rdf:type schema:PropertyValue
68 Nef6c37b3c4ba48ed99c27bab3f651812 rdf:first sg:person.013164552637.20
69 rdf:rest N4c560185ffa143ee9acb9ac9df181b74
70 Nffa919ee9e384441b059491b91ed1c67 rdf:first sg:person.01072303420.99
71 rdf:rest rdf:nil
72 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
73 schema:name Mathematical Sciences
74 rdf:type schema:DefinedTerm
75 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
76 schema:name Statistics
77 rdf:type schema:DefinedTerm
78 sg:journal.1043977 schema:issn 1383-7133
79 1572-9354
80 schema:name Constraints
81 rdf:type schema:Periodical
82 sg:person.01072303420.99 schema:affiliation Nc5f0e06980af439c822f69b5e48344f5
83 schema:familyName Schiex
84 schema:givenName Thomas
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01072303420.99
86 rdf:type schema:Person
87 sg:person.013164552637.20 schema:affiliation https://www.grid.ac/institutes/grid.121334.6
88 schema:familyName Bessiere
89 schema:givenName Christian
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013164552637.20
91 rdf:type schema:Person
92 sg:person.016264131727.46 schema:affiliation Nbee181d34cfb47fab07cf2a0072e36d2
93 schema:familyName Givry
94 schema:givenName Simon de
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016264131727.46
96 rdf:type schema:Person
97 sg:person.016341137430.49 schema:affiliation N2dd683af207740218aee7eaefca61f57
98 schema:familyName Nguyen
99 schema:givenName Hiep
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016341137430.49
101 rdf:type schema:Person
102 sg:pub.10.1007/3-540-45349-0_30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042748592
103 https://doi.org/10.1007/3-540-45349-0_30
104 rdf:type schema:CreativeWork
105 sg:pub.10.1007/bfb0017448 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018041561
106 https://doi.org/10.1007/bfb0017448
107 rdf:type schema:CreativeWork
108 sg:pub.10.1007/s10601-005-2240-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017431728
109 https://doi.org/10.1007/s10601-005-2240-3
110 rdf:type schema:CreativeWork
111 sg:pub.10.1007/s10601-007-9029-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044041135
112 https://doi.org/10.1007/s10601-007-9029-5
113 rdf:type schema:CreativeWork
114 sg:pub.10.1007/s10601-016-9245-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1046823138
115 https://doi.org/10.1007/s10601-016-9245-y
116 rdf:type schema:CreativeWork
117 sg:pub.10.1023/a:1009812409930 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025752985
118 https://doi.org/10.1023/a:1009812409930
119 rdf:type schema:CreativeWork
120 sg:pub.10.1023/a:1026488509554 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010942827
121 https://doi.org/10.1023/a:1026488509554
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1016/j.artint.2003.09.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021273787
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1016/j.artint.2004.05.004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004337524
126 rdf:type schema:CreativeWork
127 https://doi.org/10.1016/j.artint.2007.05.006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048085317
128 rdf:type schema:CreativeWork
129 https://doi.org/10.1016/j.artint.2010.02.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038096395
130 rdf:type schema:CreativeWork
131 https://doi.org/10.1016/s0165-0114(02)00134-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051570822
132 rdf:type schema:CreativeWork
133 https://doi.org/10.1021/acs.jctc.5b00594 schema:sameAs https://app.dimensions.ai/details/publication/pub.1055098688
134 rdf:type schema:CreativeWork
135 https://doi.org/10.1093/bioinformatics/btt374 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023371638
136 rdf:type schema:CreativeWork
137 https://doi.org/10.1109/caia.1995.378792 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094455415
138 rdf:type schema:CreativeWork
139 https://doi.org/10.1613/jair.3476 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105689803
140 rdf:type schema:CreativeWork
141 https://www.grid.ac/institutes/grid.121334.6 schema:alternateName University of Montpellier
142 schema:name University of Montpellier, Montpellier, France
143 rdf:type schema:Organization
 




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


...