Accelerating exact and approximate inference for (distributed) discrete optimization with GPUs View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2018-01

AUTHORS

Ferdinando Fioretto, Enrico Pontelli, William Yeoh, Rina Dechter

ABSTRACT

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. More... »

PAGES

1-43

References to SciGraph publications

  • 2015. Exploiting GPUs in Solving (Distributed) Constraint Optimization Problems with Dynamic Programming in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING
  • 2004-11. The State of the Art of Nurse Rostering in JOURNAL OF SCHEDULING
  • 2006. Global Grammar Constraints in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2006
  • 2004. External A* in KI 2004: ADVANCES IN ARTIFICIAL INTELLIGENCE
  • 2015-05. Distributed constraint optimization for teams of mobile sensing agents in AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS
  • 1988. Network-Based Heuristics for Constraint-Satisfaction Problems in SEARCH IN ARTIFICIAL INTELLIGENCE
  • 2007. Enhancing Supply Chain Decisions Using Constraint Programming: A Case Study in MICAI 2007: ADVANCES IN ARTIFICIAL INTELLIGENCE
  • 2005. Approximations in Distributed Optimization in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2005
  • 2014. Improving DPOP with Branch Consistency for Solving Distributed Constraint Optimization Problems in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING
  • 2004. A Regular Language Membership Constraint for Finite Sequences of Variables in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING – CP 2004
  • 2016. A Dynamic Programming-Based MCMC Framework for Solving DCOPs with GPUs in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING
  • 2003-02. A Dynamic Programming Approach for Consistency and Propagation for Knapsack Constraints in ANNALS OF OPERATIONS RESEARCH
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10601-017-9274-1

    DOI

    http://dx.doi.org/10.1007/s10601-017-9274-1

    DIMENSIONS

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


    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/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

    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-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

    Subject Predicate Object
    1 sg:pub.10.1007/s10601-017-9274-1 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N31a96658209b47fc8f7892ffde0f4b0e
    4 schema:citation sg:pub.10.1007/11564751_68
    5 sg:pub.10.1007/11889205_64
    6 sg:pub.10.1007/978-1-4613-8788-6_11
    7 sg:pub.10.1007/978-3-319-10428-7_24
    8 sg:pub.10.1007/978-3-319-23219-5_9
    9 sg:pub.10.1007/978-3-319-44953-1_51
    10 sg:pub.10.1007/978-3-540-30201-8_36
    11 sg:pub.10.1007/978-3-540-30221-6_18
    12 sg:pub.10.1007/978-3-540-76631-5_106
    13 sg:pub.10.1007/s10458-014-9255-3
    14 sg:pub.10.1023/a:1021801522545
    15 sg:pub.10.1023/b:josh.0000046076.75950.0b
    16 https://doi.org/10.1002/cpe.2931
    17 https://doi.org/10.1016/0020-0255(74)90008-5
    18 https://doi.org/10.1016/j.artint.2004.09.003
    19 https://doi.org/10.1016/j.artint.2009.07.004
    20 https://doi.org/10.1016/j.artint.2014.03.005
    21 https://doi.org/10.1016/j.compind.2009.02.006
    22 https://doi.org/10.1016/j.cor.2011.03.014
    23 https://doi.org/10.1016/s0004-3702(01)00159-x
    24 https://doi.org/10.1016/s0004-3702(99)00059-4
    25 https://doi.org/10.1017/cbo9780511615320
    26 https://doi.org/10.1017/s1471068411000615
    27 https://doi.org/10.1093/bioinformatics/18.suppl_1.s189
    28 https://doi.org/10.1109/hpcc.2011.32
    29 https://doi.org/10.1109/naps.2013.6666853
    30 https://doi.org/10.1109/pdp.2014.28
    31 https://doi.org/10.1109/tpami.1981.4767144
    32 https://doi.org/10.1126/science.286.5439.509
    33 https://doi.org/10.1145/1375527.1375572
    34 https://doi.org/10.1145/1964179.1964184
    35 https://doi.org/10.1145/2155620.2155676
    36 https://doi.org/10.1145/256303.256306
    37 https://doi.org/10.1145/2688909
    38 https://doi.org/10.1145/332306.332355
    39 https://doi.org/10.1145/636865.636866
    40 https://doi.org/10.1609/aimag.v33i3.2429
    41 https://doi.org/10.1613/jair.2849
    42 https://doi.org/10.1613/jair.4193
    43 https://doi.org/10.2200/s00529ed1v01y201308aim023
    44 schema:datePublished 2018-01
    45 schema:datePublishedReg 2018-01-01
    46 schema: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.
    47 schema:genre research_article
    48 schema:inLanguage en
    49 schema:isAccessibleForFree true
    50 schema:isPartOf N081219adf6ac461b83f68c12b066819e
    51 Nb2ff52e04667469282b35d7ddf1436b5
    52 sg:journal.1043977
    53 schema:name Accelerating exact and approximate inference for (distributed) discrete optimization with GPUs
    54 schema:pagination 1-43
    55 schema:productId N47fec8caa1d6452f97e546b187d553ce
    56 N8e35e0fde6504ce485dd2b77e3b5d3bd
    57 Ne2b0777e583d491aab9959a4d68d698d
    58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091243493
    59 https://doi.org/10.1007/s10601-017-9274-1
    60 schema:sdDatePublished 2019-04-11T00:30
    61 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    62 schema:sdPublisher Nf92ece92bfe24466b6f9aed7e17228f3
    63 schema:url http://link.springer.com/10.1007/s10601-017-9274-1
    64 sgo:license sg:explorer/license/
    65 sgo:sdDataset articles
    66 rdf:type schema:ScholarlyArticle
    67 N081219adf6ac461b83f68c12b066819e schema:volumeNumber 23
    68 rdf:type schema:PublicationVolume
    69 N08ef2d9482cd43d5b092d95005a286b0 rdf:first sg:person.0736627660.65
    70 rdf:rest rdf:nil
    71 N1a8d4a12d71543c781255f33e8010e02 rdf:first sg:person.014206615152.31
    72 rdf:rest N08ef2d9482cd43d5b092d95005a286b0
    73 N31a96658209b47fc8f7892ffde0f4b0e rdf:first sg:person.016125743065.12
    74 rdf:rest N9c09b977e53848ed9166e6c1c1454d30
    75 N47fec8caa1d6452f97e546b187d553ce schema:name readcube_id
    76 schema:value 2ba2301e9938778098cb48defb6a912cbab9fdbc7f596c836cc872d1cbaa1b8c
    77 rdf:type schema:PropertyValue
    78 N8e35e0fde6504ce485dd2b77e3b5d3bd schema:name doi
    79 schema:value 10.1007/s10601-017-9274-1
    80 rdf:type schema:PropertyValue
    81 N9c09b977e53848ed9166e6c1c1454d30 rdf:first sg:person.01337162670.74
    82 rdf:rest N1a8d4a12d71543c781255f33e8010e02
    83 Nb2ff52e04667469282b35d7ddf1436b5 schema:issueNumber 1
    84 rdf:type schema:PublicationIssue
    85 Ne2b0777e583d491aab9959a4d68d698d schema:name dimensions_id
    86 schema:value pub.1091243493
    87 rdf:type schema:PropertyValue
    88 Nf92ece92bfe24466b6f9aed7e17228f3 schema:name Springer Nature - SN SciGraph project
    89 rdf:type schema:Organization
    90 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    91 schema:name Information and Computing Sciences
    92 rdf:type schema:DefinedTerm
    93 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    94 schema:name Computation Theory and Mathematics
    95 rdf:type schema:DefinedTerm
    96 sg:grant.3489778 http://pending.schema.org/fundedItem sg:pub.10.1007/s10601-017-9274-1
    97 rdf:type schema:MonetaryGrant
    98 sg:grant.3850236 http://pending.schema.org/fundedItem sg:pub.10.1007/s10601-017-9274-1
    99 rdf:type schema:MonetaryGrant
    100 sg:grant.3982729 http://pending.schema.org/fundedItem sg:pub.10.1007/s10601-017-9274-1
    101 rdf:type schema:MonetaryGrant
    102 sg:grant.4312883 http://pending.schema.org/fundedItem sg:pub.10.1007/s10601-017-9274-1
    103 rdf:type schema:MonetaryGrant
    104 sg:grant.5019994 http://pending.schema.org/fundedItem sg:pub.10.1007/s10601-017-9274-1
    105 rdf:type schema:MonetaryGrant
    106 sg:journal.1043977 schema:issn 1383-7133
    107 1572-9354
    108 schema:name Constraints
    109 rdf:type schema:Periodical
    110 sg:person.01337162670.74 schema:affiliation https://www.grid.ac/institutes/grid.24805.3b
    111 schema:familyName Pontelli
    112 schema:givenName Enrico
    113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01337162670.74
    114 rdf:type schema:Person
    115 sg:person.014206615152.31 schema:affiliation https://www.grid.ac/institutes/grid.4367.6
    116 schema:familyName Yeoh
    117 schema:givenName William
    118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014206615152.31
    119 rdf:type schema:Person
    120 sg:person.016125743065.12 schema:affiliation https://www.grid.ac/institutes/grid.214458.e
    121 schema:familyName Fioretto
    122 schema:givenName Ferdinando
    123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016125743065.12
    124 rdf:type schema:Person
    125 sg:person.0736627660.65 schema:affiliation https://www.grid.ac/institutes/grid.266093.8
    126 schema:familyName Dechter
    127 schema:givenName Rina
    128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0736627660.65
    129 rdf:type schema:Person
    130 sg:pub.10.1007/11564751_68 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024908747
    131 https://doi.org/10.1007/11564751_68
    132 rdf:type schema:CreativeWork
    133 sg:pub.10.1007/11889205_64 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012781170
    134 https://doi.org/10.1007/11889205_64
    135 rdf:type schema:CreativeWork
    136 sg:pub.10.1007/978-1-4613-8788-6_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039844346
    137 https://doi.org/10.1007/978-1-4613-8788-6_11
    138 rdf:type schema:CreativeWork
    139 sg:pub.10.1007/978-3-319-10428-7_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014697834
    140 https://doi.org/10.1007/978-3-319-10428-7_24
    141 rdf:type schema:CreativeWork
    142 sg:pub.10.1007/978-3-319-23219-5_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032574147
    143 https://doi.org/10.1007/978-3-319-23219-5_9
    144 rdf:type schema:CreativeWork
    145 sg:pub.10.1007/978-3-319-44953-1_51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032139924
    146 https://doi.org/10.1007/978-3-319-44953-1_51
    147 rdf:type schema:CreativeWork
    148 sg:pub.10.1007/978-3-540-30201-8_36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044615390
    149 https://doi.org/10.1007/978-3-540-30201-8_36
    150 rdf:type schema:CreativeWork
    151 sg:pub.10.1007/978-3-540-30221-6_18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029744433
    152 https://doi.org/10.1007/978-3-540-30221-6_18
    153 rdf:type schema:CreativeWork
    154 sg:pub.10.1007/978-3-540-76631-5_106 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043346632
    155 https://doi.org/10.1007/978-3-540-76631-5_106
    156 rdf:type schema:CreativeWork
    157 sg:pub.10.1007/s10458-014-9255-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010077580
    158 https://doi.org/10.1007/s10458-014-9255-3
    159 rdf:type schema:CreativeWork
    160 sg:pub.10.1023/a:1021801522545 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047477367
    161 https://doi.org/10.1023/a:1021801522545
    162 rdf:type schema:CreativeWork
    163 sg:pub.10.1023/b:josh.0000046076.75950.0b schema:sameAs https://app.dimensions.ai/details/publication/pub.1033661233
    164 https://doi.org/10.1023/b:josh.0000046076.75950.0b
    165 rdf:type schema:CreativeWork
    166 https://doi.org/10.1002/cpe.2931 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027078169
    167 rdf:type schema:CreativeWork
    168 https://doi.org/10.1016/0020-0255(74)90008-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042040952
    169 rdf:type schema:CreativeWork
    170 https://doi.org/10.1016/j.artint.2004.09.003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048606903
    171 rdf:type schema:CreativeWork
    172 https://doi.org/10.1016/j.artint.2009.07.004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044144643
    173 rdf:type schema:CreativeWork
    174 https://doi.org/10.1016/j.artint.2014.03.005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038599837
    175 rdf:type schema:CreativeWork
    176 https://doi.org/10.1016/j.compind.2009.02.006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031271660
    177 rdf:type schema:CreativeWork
    178 https://doi.org/10.1016/j.cor.2011.03.014 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027633851
    179 rdf:type schema:CreativeWork
    180 https://doi.org/10.1016/s0004-3702(01)00159-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1016297700
    181 rdf:type schema:CreativeWork
    182 https://doi.org/10.1016/s0004-3702(99)00059-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035238649
    183 rdf:type schema:CreativeWork
    184 https://doi.org/10.1017/cbo9780511615320 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098666162
    185 rdf:type schema:CreativeWork
    186 https://doi.org/10.1017/s1471068411000615 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053807885
    187 rdf:type schema:CreativeWork
    188 https://doi.org/10.1093/bioinformatics/18.suppl_1.s189 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015905794
    189 rdf:type schema:CreativeWork
    190 https://doi.org/10.1109/hpcc.2011.32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094484536
    191 rdf:type schema:CreativeWork
    192 https://doi.org/10.1109/naps.2013.6666853 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094379968
    193 rdf:type schema:CreativeWork
    194 https://doi.org/10.1109/pdp.2014.28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095018166
    195 rdf:type schema:CreativeWork
    196 https://doi.org/10.1109/tpami.1981.4767144 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061741792
    197 rdf:type schema:CreativeWork
    198 https://doi.org/10.1126/science.286.5439.509 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010080128
    199 rdf:type schema:CreativeWork
    200 https://doi.org/10.1145/1375527.1375572 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006207992
    201 rdf:type schema:CreativeWork
    202 https://doi.org/10.1145/1964179.1964184 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011765313
    203 rdf:type schema:CreativeWork
    204 https://doi.org/10.1145/2155620.2155676 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050199325
    205 rdf:type schema:CreativeWork
    206 https://doi.org/10.1145/256303.256306 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017609577
    207 rdf:type schema:CreativeWork
    208 https://doi.org/10.1145/2688909 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017818875
    209 rdf:type schema:CreativeWork
    210 https://doi.org/10.1145/332306.332355 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049104539
    211 rdf:type schema:CreativeWork
    212 https://doi.org/10.1145/636865.636866 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047440984
    213 rdf:type schema:CreativeWork
    214 https://doi.org/10.1609/aimag.v33i3.2429 schema:sameAs https://app.dimensions.ai/details/publication/pub.1103067107
    215 rdf:type schema:CreativeWork
    216 https://doi.org/10.1613/jair.2849 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105674392
    217 rdf:type schema:CreativeWork
    218 https://doi.org/10.1613/jair.4193 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105689920
    219 rdf:type schema:CreativeWork
    220 https://doi.org/10.2200/s00529ed1v01y201308aim023 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069288410
    221 rdf:type schema:CreativeWork
    222 https://www.grid.ac/institutes/grid.214458.e schema:alternateName University of Michigan–Ann Arbor
    223 schema:name Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI, USA
    224 rdf:type schema:Organization
    225 https://www.grid.ac/institutes/grid.24805.3b schema:alternateName New Mexico State University
    226 schema:name Computer Science, New Mexico State University, Las Cruces, NM, USA
    227 rdf:type schema:Organization
    228 https://www.grid.ac/institutes/grid.266093.8 schema:alternateName University of California, Irvine
    229 schema:name School of Information and Computer Science, University of California, Irvine, CA, USA
    230 rdf:type schema:Organization
    231 https://www.grid.ac/institutes/grid.4367.6 schema:alternateName Washington University in St. Louis
    232 schema:name Computer Science and Engineering, Washington University in St. Louis, St. Louis, MO, USA
    233 rdf:type schema:Organization
     




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


    ...