Ontology type: schema:ScholarlyArticle Open Access: True
2018-01
AUTHORSFerdinando Fioretto, Enrico Pontelli, William Yeoh, Rina Dechter
ABSTRACTDiscrete optimization is a central problem in artificial intelligence. The optimization of the aggregated cost of a network of cost functions arises in a variety of problems including Weighted Constraint Programs (WCSPs), Distributed Constraint Optimization (DCOP), as well as optimization in stochastic variants such as the tasks of finding the most probable explanation (MPE) in belief networks. Inference-based algorithms are powerful techniques for solving discrete optimization problems, which can be used independently or in combination with other techniques. However, their applicability is often limited by their compute intensive nature and their space requirements. This paper proposes the design and implementation of a novel inference-based technique, which exploits modern massively parallel architectures, such as those found in Graphical Processing Units (GPUs), to speed up the resolution of exact and approximated inference-based algorithms for discrete optimization. The paper studies the proposed algorithm in both centralized and distributed optimization contexts. The paper demonstrates that the use of GPUs provides significant advantages in terms of runtime and scalability, achieving up to two orders of magnitude in speedups and showing a considerable reduction in execution time (up to 345 times faster) with respect to a sequential version. More... »
PAGES1-43
http://scigraph.springernature.com/pub.10.1007/s10601-017-9274-1
DOIhttp://dx.doi.org/10.1007/s10601-017-9274-1
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1091243493
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/0802",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computation Theory and Mathematics",
"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": "University of Michigan\u2013Ann Arbor",
"id": "https://www.grid.ac/institutes/grid.214458.e",
"name": [
"Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI, USA"
],
"type": "Organization"
},
"familyName": "Fioretto",
"givenName": "Ferdinando",
"id": "sg:person.016125743065.12",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016125743065.12"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "New Mexico State University",
"id": "https://www.grid.ac/institutes/grid.24805.3b",
"name": [
"Computer Science, New Mexico State University, Las Cruces, NM, USA"
],
"type": "Organization"
},
"familyName": "Pontelli",
"givenName": "Enrico",
"id": "sg:person.01337162670.74",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01337162670.74"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Washington University in St. Louis",
"id": "https://www.grid.ac/institutes/grid.4367.6",
"name": [
"Computer Science and Engineering, Washington University in St. Louis, St. Louis, MO, USA"
],
"type": "Organization"
},
"familyName": "Yeoh",
"givenName": "William",
"id": "sg:person.014206615152.31",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014206615152.31"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "University of California, Irvine",
"id": "https://www.grid.ac/institutes/grid.266093.8",
"name": [
"School of Information and Computer Science, University of California, Irvine, CA, USA"
],
"type": "Organization"
},
"familyName": "Dechter",
"givenName": "Rina",
"id": "sg:person.0736627660.65",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0736627660.65"
],
"type": "Person"
}
],
"citation": [
{
"id": "https://doi.org/10.1145/1375527.1375572",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1006207992"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10458-014-9255-3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1010077580",
"https://doi.org/10.1007/s10458-014-9255-3"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1126/science.286.5439.509",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1010080128"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/1964179.1964184",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1011765313"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11889205_64",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1012781170",
"https://doi.org/10.1007/11889205_64"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11889205_64",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1012781170",
"https://doi.org/10.1007/11889205_64"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-10428-7_24",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1014697834",
"https://doi.org/10.1007/978-3-319-10428-7_24"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1093/bioinformatics/18.suppl_1.s189",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1015905794"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s0004-3702(01)00159-x",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1016297700"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/256303.256306",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017609577"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/2688909",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017818875"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11564751_68",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1024908747",
"https://doi.org/10.1007/11564751_68"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11564751_68",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1024908747",
"https://doi.org/10.1007/11564751_68"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1002/cpe.2931",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1027078169"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.cor.2011.03.014",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1027633851"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-30221-6_18",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1029744433",
"https://doi.org/10.1007/978-3-540-30221-6_18"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-30221-6_18",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1029744433",
"https://doi.org/10.1007/978-3-540-30221-6_18"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.compind.2009.02.006",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1031271660"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-44953-1_51",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1032139924",
"https://doi.org/10.1007/978-3-319-44953-1_51"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-23219-5_9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1032574147",
"https://doi.org/10.1007/978-3-319-23219-5_9"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1023/b:josh.0000046076.75950.0b",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1033661233",
"https://doi.org/10.1023/b:josh.0000046076.75950.0b"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s0004-3702(99)00059-4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1035238649"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.artint.2014.03.005",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1038599837"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-1-4613-8788-6_11",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039844346",
"https://doi.org/10.1007/978-1-4613-8788-6_11"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0020-0255(74)90008-5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1042040952"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0020-0255(74)90008-5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1042040952"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-76631-5_106",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043346632",
"https://doi.org/10.1007/978-3-540-76631-5_106"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-76631-5_106",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043346632",
"https://doi.org/10.1007/978-3-540-76631-5_106"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.artint.2009.07.004",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1044144643"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-30201-8_36",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1044615390",
"https://doi.org/10.1007/978-3-540-30201-8_36"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-30201-8_36",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1044615390",
"https://doi.org/10.1007/978-3-540-30201-8_36"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/636865.636866",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1047440984"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1023/a:1021801522545",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1047477367",
"https://doi.org/10.1023/a:1021801522545"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.artint.2004.09.003",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1048606903"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/332306.332355",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1049104539"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/332306.332355",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1049104539"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/2155620.2155676",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1050199325"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1017/s1471068411000615",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1053807885"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/tpami.1981.4767144",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1061741792"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.2200/s00529ed1v01y201308aim023",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1069288410"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/naps.2013.6666853",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1094379968"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/hpcc.2011.32",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1094484536"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/pdp.2014.28",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1095018166"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1017/cbo9780511615320",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1098666162"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1609/aimag.v33i3.2429",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1103067107"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1613/jair.2849",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1105674392"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1613/jair.4193",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1105689920"
],
"type": "CreativeWork"
}
],
"datePublished": "2018-01",
"datePublishedReg": "2018-01-01",
"description": "Discrete optimization is a central problem in artificial intelligence. The optimization of the aggregated cost of a network of cost functions arises in a variety of problems including Weighted Constraint Programs (WCSPs), Distributed Constraint Optimization (DCOP), as well as optimization in stochastic variants such as the tasks of finding the most probable explanation (MPE) in belief networks. Inference-based algorithms are powerful techniques for solving discrete optimization problems, which can be used independently or in combination with other techniques. However, their applicability is often limited by their compute intensive nature and their space requirements. This paper proposes the design and implementation of a novel inference-based technique, which exploits modern massively parallel architectures, such as those found in Graphical Processing Units (GPUs), to speed up the resolution of exact and approximated inference-based algorithms for discrete optimization. The paper studies the proposed algorithm in both centralized and distributed optimization contexts. The paper demonstrates that the use of GPUs provides significant advantages in terms of runtime and scalability, achieving up to two orders of magnitude in speedups and showing a considerable reduction in execution time (up to 345 times faster) with respect to a sequential version.",
"genre": "research_article",
"id": "sg:pub.10.1007/s10601-017-9274-1",
"inLanguage": [
"en"
],
"isAccessibleForFree": true,
"isFundedItemOf": [
{
"id": "sg:grant.5019994",
"type": "MonetaryGrant"
},
{
"id": "sg:grant.4312883",
"type": "MonetaryGrant"
},
{
"id": "sg:grant.3489778",
"type": "MonetaryGrant"
},
{
"id": "sg:grant.3850236",
"type": "MonetaryGrant"
},
{
"id": "sg:grant.3982729",
"type": "MonetaryGrant"
}
],
"isPartOf": [
{
"id": "sg:journal.1043977",
"issn": [
"1383-7133",
"1572-9354"
],
"name": "Constraints",
"type": "Periodical"
},
{
"issueNumber": "1",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "23"
}
],
"name": "Accelerating exact and approximate inference for (distributed) discrete optimization with GPUs",
"pagination": "1-43",
"productId": [
{
"name": "readcube_id",
"type": "PropertyValue",
"value": [
"2ba2301e9938778098cb48defb6a912cbab9fdbc7f596c836cc872d1cbaa1b8c"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s10601-017-9274-1"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1091243493"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s10601-017-9274-1",
"https://app.dimensions.ai/details/publication/pub.1091243493"
],
"sdDataset": "articles",
"sdDatePublished": "2019-04-11T00:30",
"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/0000000001_0000000264/records_8695_00000601.jsonl",
"type": "ScholarlyArticle",
"url": "http://link.springer.com/10.1007/s10601-017-9274-1"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
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-017-9274-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-017-9274-1'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10601-017-9274-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-017-9274-1'
This table displays all metadata directly associated to this object as RDF triples.
233 TRIPLES
21 PREDICATES
67 URIs
19 LITERALS
7 BLANK NODES