MiniZinc: Towards a Standard CP Modelling Language View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2007

AUTHORS

Nicholas Nethercote , Peter J. Stuckey , Ralph Becket , Sebastian Brand , Gregory J. Duck , Guido Tack

ABSTRACT

There is no standard modelling language for constraint programming (CP) problems. Most solvers have their own modelling language. This makes it difficult for modellers to experiment with different solvers for a problem. In this paper we present MiniZinc, a simple but expressive CP modelling language which is suitable for modelling problems for a range of solvers and provides a reasonable compromise between many design possibilities. Equally importantly, we also propose a low-level solver-input language called FlatZinc, and a straightforward translation from MiniZinc to FlatZinc that preserves all solver-supported global constraints. This lets a solver writer support MiniZinc with a minimum of effort—they only need to provide a simple FlatZinc front-end to their solver, and then combine it with an existing MiniZinc-to-FlatZinc translator. Such a front-end may then serve as a stepping stone towards a full MiniZinc implementation that is more tailored to the particular solver. A standard language for modelling CP problems will encourage experimentation with and comparisons between different solvers. Although MiniZinc is not perfect—no standard modelling language will be—we believe its simplicity, expressiveness, and ease of implementation make it a practical choice for a standard language. More... »

PAGES

529-543

References to SciGraph publications

  • 2004. Introducing esra, a Relational Language for Modelling Combinatorial Problems in LOGIC BASED PROGRAM SYNTHESIS AND TRANSFORMATION
  • 2006. The Modelling Language Zinc in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2006
  • 2006. ACD Term Rewriting in LOGIC PROGRAMMING
  • 2006. Towards “Propagation = Logic + Control” in LOGIC PROGRAMMING
  • 2003. Introducing esra, a Relational Language for Modelling Combinatorial Problems (Abstract) in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING – CP 2003
  • 1999. CSPlib: A Benchmark Library for Constraints in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING – CP’99
  • Book

    TITLE

    Principles and Practice of Constraint Programming – CP 2007

    ISBN

    978-3-540-74969-1

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-74970-7_38

    DOI

    http://dx.doi.org/10.1007/978-3-540-74970-7_38

    DIMENSIONS

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


    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/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "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": {
              "name": [
                "National ICT Australia and the University of Melbourne, Victoria, Australia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Nethercote", 
            "givenName": "Nicholas", 
            "id": "sg:person.07732570545.28", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07732570545.28"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "National ICT Australia and the University of Melbourne, Victoria, Australia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Stuckey", 
            "givenName": "Peter J.", 
            "id": "sg:person.012243374043.93", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012243374043.93"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "National ICT Australia and the University of Melbourne, Victoria, Australia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Becket", 
            "givenName": "Ralph", 
            "id": "sg:person.010164767572.44", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010164767572.44"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "National ICT Australia and the University of Melbourne, Victoria, Australia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Brand", 
            "givenName": "Sebastian", 
            "id": "sg:person.012224671401.25", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012224671401.25"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "National ICT Australia and the University of Melbourne, Victoria, Australia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Duck", 
            "givenName": "Gregory J.", 
            "id": "sg:person.014415213001.27", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014415213001.27"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Saarland University", 
              "id": "https://www.grid.ac/institutes/grid.11749.3a", 
              "name": [
                "Programming Systems Lab, Saarland University, Saarbr\u00fccken, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Tack", 
            "givenName": "Guido", 
            "id": "sg:person.01235032467.07", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01235032467.07"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/11799573_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009388152", 
              "https://doi.org/10.1007/11799573_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11799573_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009388152", 
              "https://doi.org/10.1007/11799573_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11889205_54", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032948861", 
              "https://doi.org/10.1007/11889205_54"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-25938-1_18", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033426672", 
              "https://doi.org/10.1007/978-3-540-25938-1_18"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-25938-1_18", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033426672", 
              "https://doi.org/10.1007/978-3-540-25938-1_18"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-45193-8_95", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037006276", 
              "https://doi.org/10.1007/978-3-540-45193-8_95"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-48085-3_36", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042874840", 
              "https://doi.org/10.1007/978-3-540-48085-3_36"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11799573_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053601832", 
              "https://doi.org/10.1007/11799573_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11799573_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053601832", 
              "https://doi.org/10.1007/11799573_11"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2007", 
        "datePublishedReg": "2007-01-01", 
        "description": "There is no standard modelling language for constraint programming (CP) problems. Most solvers have their own modelling language. This makes it difficult for modellers to experiment with different solvers for a problem. In this paper we present MiniZinc, a simple but expressive CP modelling language which is suitable for modelling problems for a range of solvers and provides a reasonable compromise between many design possibilities. Equally importantly, we also propose a low-level solver-input language called FlatZinc, and a straightforward translation from MiniZinc to FlatZinc that preserves all solver-supported global constraints. This lets a solver writer support MiniZinc with a minimum of effort\u2014they only need to provide a simple FlatZinc front-end to their solver, and then combine it with an existing MiniZinc-to-FlatZinc translator. Such a front-end may then serve as a stepping stone towards a full MiniZinc implementation that is more tailored to the particular solver. A standard language for modelling CP problems will encourage experimentation with and comparisons between different solvers. Although MiniZinc is not perfect\u2014no standard modelling language will be\u2014we believe its simplicity, expressiveness, and ease of implementation make it a practical choice for a standard language.", 
        "editor": [
          {
            "familyName": "Bessi\u00e8re", 
            "givenName": "Christian", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-74970-7_38", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-74969-1"
          ], 
          "name": "Principles and Practice of Constraint Programming \u2013 CP 2007", 
          "type": "Book"
        }, 
        "name": "MiniZinc: Towards a Standard CP Modelling Language", 
        "pagination": "529-543", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-74970-7_38"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "21615ce24cc713b17f98a8df16c8204830b9bc3f29b0dafd6b46921a8e27a586"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1007007409"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-74970-7_38", 
          "https://app.dimensions.ai/details/publication/pub.1007007409"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T05:31", 
        "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/0000000346_0000000346/records_99809_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-540-74970-7_38"
      }
    ]
     

    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-540-74970-7_38'

    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-540-74970-7_38'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-74970-7_38'

    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-540-74970-7_38'


     

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

    133 TRIPLES      23 PREDICATES      33 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-74970-7_38 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N2f963cde5d6f413a8e72f86db6bdfa4c
    4 schema:citation sg:pub.10.1007/11799573_10
    5 sg:pub.10.1007/11799573_11
    6 sg:pub.10.1007/11889205_54
    7 sg:pub.10.1007/978-3-540-25938-1_18
    8 sg:pub.10.1007/978-3-540-45193-8_95
    9 sg:pub.10.1007/978-3-540-48085-3_36
    10 schema:datePublished 2007
    11 schema:datePublishedReg 2007-01-01
    12 schema:description There is no standard modelling language for constraint programming (CP) problems. Most solvers have their own modelling language. This makes it difficult for modellers to experiment with different solvers for a problem. In this paper we present MiniZinc, a simple but expressive CP modelling language which is suitable for modelling problems for a range of solvers and provides a reasonable compromise between many design possibilities. Equally importantly, we also propose a low-level solver-input language called FlatZinc, and a straightforward translation from MiniZinc to FlatZinc that preserves all solver-supported global constraints. This lets a solver writer support MiniZinc with a minimum of effort—they only need to provide a simple FlatZinc front-end to their solver, and then combine it with an existing MiniZinc-to-FlatZinc translator. Such a front-end may then serve as a stepping stone towards a full MiniZinc implementation that is more tailored to the particular solver. A standard language for modelling CP problems will encourage experimentation with and comparisons between different solvers. Although MiniZinc is not perfect—no standard modelling language will be—we believe its simplicity, expressiveness, and ease of implementation make it a practical choice for a standard language.
    13 schema:editor N81886c5bf0224688b8abebf2859feb75
    14 schema:genre chapter
    15 schema:inLanguage en
    16 schema:isAccessibleForFree true
    17 schema:isPartOf N69df84af55884eba93ce78d37955c3dd
    18 schema:name MiniZinc: Towards a Standard CP Modelling Language
    19 schema:pagination 529-543
    20 schema:productId Nd886f8ac62984835872dffdbefcc2af4
    21 Ne1cce3e02c0d43e38596e37b5f83a1c4
    22 Nf487fb1c47ca4a4c81a9c7a1bd1d55d9
    23 schema:publisher N51fff56265854f869f32fed1ca9a883c
    24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007007409
    25 https://doi.org/10.1007/978-3-540-74970-7_38
    26 schema:sdDatePublished 2019-04-16T05:31
    27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    28 schema:sdPublisher Nb802823da63446c5bd49323e7b6943c1
    29 schema:url https://link.springer.com/10.1007%2F978-3-540-74970-7_38
    30 sgo:license sg:explorer/license/
    31 sgo:sdDataset chapters
    32 rdf:type schema:Chapter
    33 N1504ccd490e54d57bc0a57a79441f890 schema:familyName Bessière
    34 schema:givenName Christian
    35 rdf:type schema:Person
    36 N1a495fb6cd6a4b3085cb51c20126ebb9 rdf:first sg:person.014415213001.27
    37 rdf:rest N3bd9676ac2c045b3af983e7c209ffe0f
    38 N20a95ac7705f494b9ad5948be113a20a rdf:first sg:person.012243374043.93
    39 rdf:rest N8d59bf8900224982bc69539d8da01826
    40 N2e2e709d9ca04938b30bf6ac410ceb73 rdf:first sg:person.012224671401.25
    41 rdf:rest N1a495fb6cd6a4b3085cb51c20126ebb9
    42 N2f963cde5d6f413a8e72f86db6bdfa4c rdf:first sg:person.07732570545.28
    43 rdf:rest N20a95ac7705f494b9ad5948be113a20a
    44 N319fcb257ecd4375aa2f8afef80b2396 schema:name National ICT Australia and the University of Melbourne, Victoria, Australia
    45 rdf:type schema:Organization
    46 N39ea2d117b3849479c7c6e5a0ce95a83 schema:name National ICT Australia and the University of Melbourne, Victoria, Australia
    47 rdf:type schema:Organization
    48 N3bd9676ac2c045b3af983e7c209ffe0f rdf:first sg:person.01235032467.07
    49 rdf:rest rdf:nil
    50 N51fff56265854f869f32fed1ca9a883c schema:location Berlin, Heidelberg
    51 schema:name Springer Berlin Heidelberg
    52 rdf:type schema:Organisation
    53 N69df84af55884eba93ce78d37955c3dd schema:isbn 978-3-540-74969-1
    54 schema:name Principles and Practice of Constraint Programming – CP 2007
    55 rdf:type schema:Book
    56 N81886c5bf0224688b8abebf2859feb75 rdf:first N1504ccd490e54d57bc0a57a79441f890
    57 rdf:rest rdf:nil
    58 N8d59bf8900224982bc69539d8da01826 rdf:first sg:person.010164767572.44
    59 rdf:rest N2e2e709d9ca04938b30bf6ac410ceb73
    60 N9152192503b04b9cb0fedc4d4baad298 schema:name National ICT Australia and the University of Melbourne, Victoria, Australia
    61 rdf:type schema:Organization
    62 N9699a95e2abd4d8294d60393e875ceb8 schema:name National ICT Australia and the University of Melbourne, Victoria, Australia
    63 rdf:type schema:Organization
    64 Nb54b3d62c6774756b07db15a3072636f schema:name National ICT Australia and the University of Melbourne, Victoria, Australia
    65 rdf:type schema:Organization
    66 Nb802823da63446c5bd49323e7b6943c1 schema:name Springer Nature - SN SciGraph project
    67 rdf:type schema:Organization
    68 Nd886f8ac62984835872dffdbefcc2af4 schema:name readcube_id
    69 schema:value 21615ce24cc713b17f98a8df16c8204830b9bc3f29b0dafd6b46921a8e27a586
    70 rdf:type schema:PropertyValue
    71 Ne1cce3e02c0d43e38596e37b5f83a1c4 schema:name doi
    72 schema:value 10.1007/978-3-540-74970-7_38
    73 rdf:type schema:PropertyValue
    74 Nf487fb1c47ca4a4c81a9c7a1bd1d55d9 schema:name dimensions_id
    75 schema:value pub.1007007409
    76 rdf:type schema:PropertyValue
    77 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    78 schema:name Information and Computing Sciences
    79 rdf:type schema:DefinedTerm
    80 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    81 schema:name Artificial Intelligence and Image Processing
    82 rdf:type schema:DefinedTerm
    83 sg:person.010164767572.44 schema:affiliation N39ea2d117b3849479c7c6e5a0ce95a83
    84 schema:familyName Becket
    85 schema:givenName Ralph
    86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010164767572.44
    87 rdf:type schema:Person
    88 sg:person.012224671401.25 schema:affiliation N9699a95e2abd4d8294d60393e875ceb8
    89 schema:familyName Brand
    90 schema:givenName Sebastian
    91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012224671401.25
    92 rdf:type schema:Person
    93 sg:person.012243374043.93 schema:affiliation Nb54b3d62c6774756b07db15a3072636f
    94 schema:familyName Stuckey
    95 schema:givenName Peter J.
    96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012243374043.93
    97 rdf:type schema:Person
    98 sg:person.01235032467.07 schema:affiliation https://www.grid.ac/institutes/grid.11749.3a
    99 schema:familyName Tack
    100 schema:givenName Guido
    101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01235032467.07
    102 rdf:type schema:Person
    103 sg:person.014415213001.27 schema:affiliation N9152192503b04b9cb0fedc4d4baad298
    104 schema:familyName Duck
    105 schema:givenName Gregory J.
    106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014415213001.27
    107 rdf:type schema:Person
    108 sg:person.07732570545.28 schema:affiliation N319fcb257ecd4375aa2f8afef80b2396
    109 schema:familyName Nethercote
    110 schema:givenName Nicholas
    111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07732570545.28
    112 rdf:type schema:Person
    113 sg:pub.10.1007/11799573_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009388152
    114 https://doi.org/10.1007/11799573_10
    115 rdf:type schema:CreativeWork
    116 sg:pub.10.1007/11799573_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053601832
    117 https://doi.org/10.1007/11799573_11
    118 rdf:type schema:CreativeWork
    119 sg:pub.10.1007/11889205_54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032948861
    120 https://doi.org/10.1007/11889205_54
    121 rdf:type schema:CreativeWork
    122 sg:pub.10.1007/978-3-540-25938-1_18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033426672
    123 https://doi.org/10.1007/978-3-540-25938-1_18
    124 rdf:type schema:CreativeWork
    125 sg:pub.10.1007/978-3-540-45193-8_95 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037006276
    126 https://doi.org/10.1007/978-3-540-45193-8_95
    127 rdf:type schema:CreativeWork
    128 sg:pub.10.1007/978-3-540-48085-3_36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042874840
    129 https://doi.org/10.1007/978-3-540-48085-3_36
    130 rdf:type schema:CreativeWork
    131 https://www.grid.ac/institutes/grid.11749.3a schema:alternateName Saarland University
    132 schema:name Programming Systems Lab, Saarland University, Saarbrücken, Germany
    133 rdf:type schema:Organization
     




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


    ...