Constraint Reasoning with Uncertain Data Using CDF-Intervals View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2010

AUTHORS

Aya Saad , Carmen Gervet , Slim Abdennadher

ABSTRACT

Interval coefficients have been introduced in OR and CP to specify uncertain data in order to provide reliable solutions to convex models. The output is generally a solution set, guaranteed to contain all solutions possible under any realization of the data. This set can be too large to be meaningful. Furthermore, each solution has equal uncertainty weight, thus does not reflect any possible degree of knowledge about the data. To overcome these problems we propose to extend the notion of interval coefficient by introducing a second dimension to each interval bound. Each bound is now specified by its data value and its degree of knowledge. This is formalized using the cumulative distribution function of the data set. We define the formal framework of constraint reasoning over this cdf-intervals. The main contribution of this paper concerns the formal definition of a new interval arithmetic and its implementation. Promising results on problem instances demonstrate the approach. More... »

PAGES

292-306

Book

TITLE

Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems

ISBN

978-3-642-13519-4
978-3-642-13520-0

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-13520-0_32

DOI

http://dx.doi.org/10.1007/978-3-642-13520-0_32

DIMENSIONS

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


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/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "German University in Cairo", 
          "id": "https://www.grid.ac/institutes/grid.187323.c", 
          "name": [
            "German University in Cairo, New Cairo City, Egypt"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Saad", 
        "givenName": "Aya", 
        "id": "sg:person.011245360251.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011245360251.63"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "German University in Cairo", 
          "id": "https://www.grid.ac/institutes/grid.187323.c", 
          "name": [
            "German University in Cairo, New Cairo City, Egypt"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gervet", 
        "givenName": "Carmen", 
        "id": "sg:person.013221377553.51", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013221377553.51"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "German University in Cairo", 
          "id": "https://www.grid.ac/institutes/grid.187323.c", 
          "name": [
            "German University in Cairo, New Cairo City, Egypt"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Abdennadher", 
        "givenName": "Slim", 
        "id": "sg:person.010445445574.13", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010445445574.13"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0004-3702(77)90007-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001107257"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-59155-9_1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005014387", 
          "https://doi.org/10.1007/3-540-59155-9_1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-4730(95)00010-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020615877"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00933139", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022275509", 
          "https://doi.org/10.1007/bf00933139"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0167-6377(99)00016-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023678521"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.imavis.2008.10.002", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025771146"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00122574", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041153045", 
          "https://doi.org/10.1007/bf00122574"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00122574", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041153045", 
          "https://doi.org/10.1007/bf00122574"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0024-3795(98)10044-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046802106"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0377-0427(00)00430-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047769736"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1057/palgrave.jors.2600891", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050894846", 
          "https://doi.org/10.1057/palgrave.jors.2600891"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1459010.1459013", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052778231"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/cbo9780511813610", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098666485"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "Interval coefficients have been introduced in OR and CP to specify uncertain data in order to provide reliable solutions to convex models. The output is generally a solution set, guaranteed to contain all solutions possible under any realization of the data. This set can be too large to be meaningful. Furthermore, each solution has equal uncertainty weight, thus does not reflect any possible degree of knowledge about the data. To overcome these problems we propose to extend the notion of interval coefficient by introducing a second dimension to each interval bound. Each bound is now specified by its data value and its degree of knowledge. This is formalized using the cumulative distribution function of the data set. We define the formal framework of constraint reasoning over this cdf-intervals. The main contribution of this paper concerns the formal definition of a new interval arithmetic and its implementation. Promising results on problem instances demonstrate the approach.", 
    "editor": [
      {
        "familyName": "Lodi", 
        "givenName": "Andrea", 
        "type": "Person"
      }, 
      {
        "familyName": "Milano", 
        "givenName": "Michela", 
        "type": "Person"
      }, 
      {
        "familyName": "Toth", 
        "givenName": "Paolo", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-13520-0_32", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-13519-4", 
        "978-3-642-13520-0"
      ], 
      "name": "Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems", 
      "type": "Book"
    }, 
    "name": "Constraint Reasoning with Uncertain Data Using CDF-Intervals", 
    "pagination": "292-306", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1039136723"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-13520-0_32"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "ba6d44893b3232873a4320d454dd552bf896f1d0c5659d35249f614c9bf94bc5"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-13520-0_32", 
      "https://app.dimensions.ai/details/publication/pub.1039136723"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:06", 
    "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/0000000359_0000000359/records_29222_00000002.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-642-13520-0_32"
  }
]
 

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-642-13520-0_32'

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-642-13520-0_32'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-13520-0_32'

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-642-13520-0_32'


 

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

129 TRIPLES      23 PREDICATES      39 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-13520-0_32 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author N73c5c543d14a4d37b98dd2cd8afd5b3b
4 schema:citation sg:pub.10.1007/3-540-59155-9_1
5 sg:pub.10.1007/bf00122574
6 sg:pub.10.1007/bf00933139
7 sg:pub.10.1057/palgrave.jors.2600891
8 https://doi.org/10.1016/0004-3702(77)90007-8
9 https://doi.org/10.1016/0167-4730(95)00010-2
10 https://doi.org/10.1016/j.imavis.2008.10.002
11 https://doi.org/10.1016/s0024-3795(98)10044-7
12 https://doi.org/10.1016/s0167-6377(99)00016-4
13 https://doi.org/10.1016/s0377-0427(00)00430-1
14 https://doi.org/10.1017/cbo9780511813610
15 https://doi.org/10.1145/1459010.1459013
16 schema:datePublished 2010
17 schema:datePublishedReg 2010-01-01
18 schema:description Interval coefficients have been introduced in OR and CP to specify uncertain data in order to provide reliable solutions to convex models. The output is generally a solution set, guaranteed to contain all solutions possible under any realization of the data. This set can be too large to be meaningful. Furthermore, each solution has equal uncertainty weight, thus does not reflect any possible degree of knowledge about the data. To overcome these problems we propose to extend the notion of interval coefficient by introducing a second dimension to each interval bound. Each bound is now specified by its data value and its degree of knowledge. This is formalized using the cumulative distribution function of the data set. We define the formal framework of constraint reasoning over this cdf-intervals. The main contribution of this paper concerns the formal definition of a new interval arithmetic and its implementation. Promising results on problem instances demonstrate the approach.
19 schema:editor Ndb3c389e514d4323a7f5c9834aaa1470
20 schema:genre chapter
21 schema:inLanguage en
22 schema:isAccessibleForFree true
23 schema:isPartOf Ne07e477f8c954a45a47a43e5ae9b4f4e
24 schema:name Constraint Reasoning with Uncertain Data Using CDF-Intervals
25 schema:pagination 292-306
26 schema:productId N12dcca0f29804ba892af3bc915e4bb40
27 N817e67c4da4e4b709d555aca4d8d7182
28 Nf935f6eabeaf462aafdeb68b243dac24
29 schema:publisher N51e8fbddd5444bb98c999af7ca23f422
30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039136723
31 https://doi.org/10.1007/978-3-642-13520-0_32
32 schema:sdDatePublished 2019-04-16T08:06
33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
34 schema:sdPublisher Ne1243d58325d4326866b55525811b1b4
35 schema:url https://link.springer.com/10.1007%2F978-3-642-13520-0_32
36 sgo:license sg:explorer/license/
37 sgo:sdDataset chapters
38 rdf:type schema:Chapter
39 N12dcca0f29804ba892af3bc915e4bb40 schema:name dimensions_id
40 schema:value pub.1039136723
41 rdf:type schema:PropertyValue
42 N51e8fbddd5444bb98c999af7ca23f422 schema:location Berlin, Heidelberg
43 schema:name Springer Berlin Heidelberg
44 rdf:type schema:Organisation
45 N626680d20ad844289a0d0a8aaa8b669a rdf:first Nf65d7e2049b04496a58a48d2d213e5bc
46 rdf:rest rdf:nil
47 N73c5c543d14a4d37b98dd2cd8afd5b3b rdf:first sg:person.011245360251.63
48 rdf:rest N9f21d97b6c404aeaa18670c340d0ab0f
49 N817e67c4da4e4b709d555aca4d8d7182 schema:name readcube_id
50 schema:value ba6d44893b3232873a4320d454dd552bf896f1d0c5659d35249f614c9bf94bc5
51 rdf:type schema:PropertyValue
52 N965de77f54bb4c5a9b552b41bbe9c2d6 rdf:first N9fde6d6688d44315960de495f350d625
53 rdf:rest N626680d20ad844289a0d0a8aaa8b669a
54 N9f21d97b6c404aeaa18670c340d0ab0f rdf:first sg:person.013221377553.51
55 rdf:rest Naf786e55c9b946c28cd1189da280ac42
56 N9fde6d6688d44315960de495f350d625 schema:familyName Milano
57 schema:givenName Michela
58 rdf:type schema:Person
59 Naf786e55c9b946c28cd1189da280ac42 rdf:first sg:person.010445445574.13
60 rdf:rest rdf:nil
61 Nbec9da279d4e459a9d791e998bc878ac schema:familyName Lodi
62 schema:givenName Andrea
63 rdf:type schema:Person
64 Ndb3c389e514d4323a7f5c9834aaa1470 rdf:first Nbec9da279d4e459a9d791e998bc878ac
65 rdf:rest N965de77f54bb4c5a9b552b41bbe9c2d6
66 Ne07e477f8c954a45a47a43e5ae9b4f4e schema:isbn 978-3-642-13519-4
67 978-3-642-13520-0
68 schema:name Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
69 rdf:type schema:Book
70 Ne1243d58325d4326866b55525811b1b4 schema:name Springer Nature - SN SciGraph project
71 rdf:type schema:Organization
72 Nf65d7e2049b04496a58a48d2d213e5bc schema:familyName Toth
73 schema:givenName Paolo
74 rdf:type schema:Person
75 Nf935f6eabeaf462aafdeb68b243dac24 schema:name doi
76 schema:value 10.1007/978-3-642-13520-0_32
77 rdf:type schema:PropertyValue
78 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
79 schema:name Information and Computing Sciences
80 rdf:type schema:DefinedTerm
81 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
82 schema:name Information Systems
83 rdf:type schema:DefinedTerm
84 sg:person.010445445574.13 schema:affiliation https://www.grid.ac/institutes/grid.187323.c
85 schema:familyName Abdennadher
86 schema:givenName Slim
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010445445574.13
88 rdf:type schema:Person
89 sg:person.011245360251.63 schema:affiliation https://www.grid.ac/institutes/grid.187323.c
90 schema:familyName Saad
91 schema:givenName Aya
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011245360251.63
93 rdf:type schema:Person
94 sg:person.013221377553.51 schema:affiliation https://www.grid.ac/institutes/grid.187323.c
95 schema:familyName Gervet
96 schema:givenName Carmen
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013221377553.51
98 rdf:type schema:Person
99 sg:pub.10.1007/3-540-59155-9_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005014387
100 https://doi.org/10.1007/3-540-59155-9_1
101 rdf:type schema:CreativeWork
102 sg:pub.10.1007/bf00122574 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041153045
103 https://doi.org/10.1007/bf00122574
104 rdf:type schema:CreativeWork
105 sg:pub.10.1007/bf00933139 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022275509
106 https://doi.org/10.1007/bf00933139
107 rdf:type schema:CreativeWork
108 sg:pub.10.1057/palgrave.jors.2600891 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050894846
109 https://doi.org/10.1057/palgrave.jors.2600891
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1016/0004-3702(77)90007-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001107257
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1016/0167-4730(95)00010-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020615877
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1016/j.imavis.2008.10.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025771146
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1016/s0024-3795(98)10044-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046802106
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1016/s0167-6377(99)00016-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023678521
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1016/s0377-0427(00)00430-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047769736
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1017/cbo9780511813610 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098666485
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1145/1459010.1459013 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052778231
126 rdf:type schema:CreativeWork
127 https://www.grid.ac/institutes/grid.187323.c schema:alternateName German University in Cairo
128 schema:name German University in Cairo, New Cairo City, Egypt
129 rdf:type schema:Organization
 




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


...