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 Ne2352076dc96415b9e40e57283f66777
    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 Nb909deddcb914dfdbe0796d0a1c4b8ca
    14 schema:genre chapter
    15 schema:inLanguage en
    16 schema:isAccessibleForFree true
    17 schema:isPartOf Na00019b2648c40069e57e51696a0e523
    18 schema:name MiniZinc: Towards a Standard CP Modelling Language
    19 schema:pagination 529-543
    20 schema:productId N52abb76015e54a739aff22912e80c1bd
    21 N59488b270e7b4be69366eae3d3a55848
    22 Naa6787d735694070a5e43ad9e4e654cb
    23 schema:publisher N1774494cab8245eabab0f6e37c1fd633
    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 N4242e79bc5444acbb7d261939aaa4dbf
    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 N1165977f6b86422b8af459b43ba4590f rdf:first sg:person.010164767572.44
    34 rdf:rest Nfb2a285ad7d04befb484be7cf070b89b
    35 N1774494cab8245eabab0f6e37c1fd633 schema:location Berlin, Heidelberg
    36 schema:name Springer Berlin Heidelberg
    37 rdf:type schema:Organisation
    38 N374b26b7ff734b93a28fef07a8e4064c schema:familyName Bessière
    39 schema:givenName Christian
    40 rdf:type schema:Person
    41 N401d031ea8ae44d78f5a8f685863cded schema:name National ICT Australia and the University of Melbourne, Victoria, Australia
    42 rdf:type schema:Organization
    43 N4242e79bc5444acbb7d261939aaa4dbf schema:name Springer Nature - SN SciGraph project
    44 rdf:type schema:Organization
    45 N52abb76015e54a739aff22912e80c1bd schema:name readcube_id
    46 schema:value 21615ce24cc713b17f98a8df16c8204830b9bc3f29b0dafd6b46921a8e27a586
    47 rdf:type schema:PropertyValue
    48 N5314fea1c5fc448f9332a7e1e7cdf631 rdf:first sg:person.01235032467.07
    49 rdf:rest rdf:nil
    50 N59488b270e7b4be69366eae3d3a55848 schema:name dimensions_id
    51 schema:value pub.1007007409
    52 rdf:type schema:PropertyValue
    53 N73144bc9e80d4a70b1031d08569a3ff5 rdf:first sg:person.014415213001.27
    54 rdf:rest N5314fea1c5fc448f9332a7e1e7cdf631
    55 N7d0b57177e6d4885bb8d9e46cd5bb757 schema:name National ICT Australia and the University of Melbourne, Victoria, Australia
    56 rdf:type schema:Organization
    57 N8191e0a3668e4c5881889af040e5c6d6 schema:name National ICT Australia and the University of Melbourne, Victoria, Australia
    58 rdf:type schema:Organization
    59 Na00019b2648c40069e57e51696a0e523 schema:isbn 978-3-540-74969-1
    60 schema:name Principles and Practice of Constraint Programming – CP 2007
    61 rdf:type schema:Book
    62 Naa6787d735694070a5e43ad9e4e654cb schema:name doi
    63 schema:value 10.1007/978-3-540-74970-7_38
    64 rdf:type schema:PropertyValue
    65 Nb909deddcb914dfdbe0796d0a1c4b8ca rdf:first N374b26b7ff734b93a28fef07a8e4064c
    66 rdf:rest rdf:nil
    67 Nd3746ba352434088a7d37d0f5ec33df2 schema:name National ICT Australia and the University of Melbourne, Victoria, Australia
    68 rdf:type schema:Organization
    69 Ndef058a2825f405d91bf49574a8de499 rdf:first sg:person.012243374043.93
    70 rdf:rest N1165977f6b86422b8af459b43ba4590f
    71 Ne2352076dc96415b9e40e57283f66777 rdf:first sg:person.07732570545.28
    72 rdf:rest Ndef058a2825f405d91bf49574a8de499
    73 Ne958a02d14644b66a11ed39692a2fce0 schema:name National ICT Australia and the University of Melbourne, Victoria, Australia
    74 rdf:type schema:Organization
    75 Nfb2a285ad7d04befb484be7cf070b89b rdf:first sg:person.012224671401.25
    76 rdf:rest N73144bc9e80d4a70b1031d08569a3ff5
    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 N7d0b57177e6d4885bb8d9e46cd5bb757
    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 N8191e0a3668e4c5881889af040e5c6d6
    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 N401d031ea8ae44d78f5a8f685863cded
    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 Nd3746ba352434088a7d37d0f5ec33df2
    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 Ne958a02d14644b66a11ed39692a2fce0
    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)


    ...