Improved linearization of constraint programming models

Gleb Belov, Peter J. Stuckey, Guido Tack, Mark Wallace

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    Abstract

    Constraint Programming (CP) standardizes many specialized “global constraints” allowing high-level modelling of combinatorial optimization and feasibility problems. Current Mixed-Integer Linear Programming (MIP) technology lacks both a modelling language and a solving mechanism based on high-level constraints. MiniZinc is a solver-independent CP modelling language. The solver interface works by translating a MiniZinc model into the simpler language FlatZinc. A specific solver can provide its own redefinition library of MiniZinc constraints. This paper describes improvements to the redefinitions for MIP solvers and to the compiler front-end. We discuss known and new translation methods, in particular we introduce a coordinated decomposition for domain constraints. The redefinition library is tested on the benchmarks of the MiniZinc Challenges 2012–2015. Experiments show that the two solving paradigms have rather diverse sets of strengths and weaknesses. We believe this is an important step for modelling languages. It illustrates that the high-level approach of recognizing and naming combinatorial substructure and using this to define a model, common to CP modellers, is equally applicable to those wishing to use MIP solving technology. It also makes the goal of solver-independent modelling one step closer. At least for prototyping, the new front-end frees the modeller from considering the solving technology, extracting very good performance from MIP solvers for high-level CP-style MiniZinc models.

    Original languageEnglish
    Title of host publicationPrinciples and Practice of Constraint Programming
    Subtitle of host publication22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings
    EditorsMichel Rueher
    Place of PublicationSwitzerland
    PublisherSpringer
    Pages49-65
    Number of pages17
    ISBN (Electronic)9783319449531
    ISBN (Print)9783319449524
    DOIs
    Publication statusPublished - 2016
    EventInternational Conference on Principles and Practice of Constraint Programming 2016 - Toulouse, France
    Duration: 5 Sep 20169 Sep 2016
    Conference number: 22d
    http://cp2016.a4cp.org/

    Publication series

    NameLecture Notes in Computer Science
    Volume9892
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    ConferenceInternational Conference on Principles and Practice of Constraint Programming 2016
    Abbreviated titleCP 2016
    CountryFrance
    CityToulouse
    Period5/09/169/09/16
    Internet address

    Keywords

    • Automatic reformulation
    • Combinatorial optimization
    • Context-aware reformulation
    • High-level modelling
    • Linear decomposition

    Cite this

    Belov, G., Stuckey, P. J., Tack, G., & Wallace, M. (2016). Improved linearization of constraint programming models. In M. Rueher (Ed.), Principles and Practice of Constraint Programming: 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings (pp. 49-65). (Lecture Notes in Computer Science; Vol. 9892). Switzerland: Springer. https://doi.org/10.1007/978-3-319-44953-1_4
    Belov, Gleb ; Stuckey, Peter J. ; Tack, Guido ; Wallace, Mark. / Improved linearization of constraint programming models. Principles and Practice of Constraint Programming: 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings. editor / Michel Rueher. Switzerland : Springer, 2016. pp. 49-65 (Lecture Notes in Computer Science).
    @inproceedings{041516c41a4741c999bf1087a821c9b0,
    title = "Improved linearization of constraint programming models",
    abstract = "Constraint Programming (CP) standardizes many specialized “global constraints” allowing high-level modelling of combinatorial optimization and feasibility problems. Current Mixed-Integer Linear Programming (MIP) technology lacks both a modelling language and a solving mechanism based on high-level constraints. MiniZinc is a solver-independent CP modelling language. The solver interface works by translating a MiniZinc model into the simpler language FlatZinc. A specific solver can provide its own redefinition library of MiniZinc constraints. This paper describes improvements to the redefinitions for MIP solvers and to the compiler front-end. We discuss known and new translation methods, in particular we introduce a coordinated decomposition for domain constraints. The redefinition library is tested on the benchmarks of the MiniZinc Challenges 2012–2015. Experiments show that the two solving paradigms have rather diverse sets of strengths and weaknesses. We believe this is an important step for modelling languages. It illustrates that the high-level approach of recognizing and naming combinatorial substructure and using this to define a model, common to CP modellers, is equally applicable to those wishing to use MIP solving technology. It also makes the goal of solver-independent modelling one step closer. At least for prototyping, the new front-end frees the modeller from considering the solving technology, extracting very good performance from MIP solvers for high-level CP-style MiniZinc models.",
    keywords = "Automatic reformulation, Combinatorial optimization, Context-aware reformulation, High-level modelling, Linear decomposition",
    author = "Gleb Belov and Stuckey, {Peter J.} and Guido Tack and Mark Wallace",
    year = "2016",
    doi = "10.1007/978-3-319-44953-1_4",
    language = "English",
    isbn = "9783319449524",
    series = "Lecture Notes in Computer Science",
    publisher = "Springer",
    pages = "49--65",
    editor = "Michel Rueher",
    booktitle = "Principles and Practice of Constraint Programming",

    }

    Belov, G, Stuckey, PJ, Tack, G & Wallace, M 2016, Improved linearization of constraint programming models. in M Rueher (ed.), Principles and Practice of Constraint Programming: 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings. Lecture Notes in Computer Science, vol. 9892, Springer, Switzerland, pp. 49-65, International Conference on Principles and Practice of Constraint Programming 2016, Toulouse, France, 5/09/16. https://doi.org/10.1007/978-3-319-44953-1_4

    Improved linearization of constraint programming models. / Belov, Gleb; Stuckey, Peter J.; Tack, Guido; Wallace, Mark.

    Principles and Practice of Constraint Programming: 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings. ed. / Michel Rueher. Switzerland : Springer, 2016. p. 49-65 (Lecture Notes in Computer Science; Vol. 9892).

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    TY - GEN

    T1 - Improved linearization of constraint programming models

    AU - Belov, Gleb

    AU - Stuckey, Peter J.

    AU - Tack, Guido

    AU - Wallace, Mark

    PY - 2016

    Y1 - 2016

    N2 - Constraint Programming (CP) standardizes many specialized “global constraints” allowing high-level modelling of combinatorial optimization and feasibility problems. Current Mixed-Integer Linear Programming (MIP) technology lacks both a modelling language and a solving mechanism based on high-level constraints. MiniZinc is a solver-independent CP modelling language. The solver interface works by translating a MiniZinc model into the simpler language FlatZinc. A specific solver can provide its own redefinition library of MiniZinc constraints. This paper describes improvements to the redefinitions for MIP solvers and to the compiler front-end. We discuss known and new translation methods, in particular we introduce a coordinated decomposition for domain constraints. The redefinition library is tested on the benchmarks of the MiniZinc Challenges 2012–2015. Experiments show that the two solving paradigms have rather diverse sets of strengths and weaknesses. We believe this is an important step for modelling languages. It illustrates that the high-level approach of recognizing and naming combinatorial substructure and using this to define a model, common to CP modellers, is equally applicable to those wishing to use MIP solving technology. It also makes the goal of solver-independent modelling one step closer. At least for prototyping, the new front-end frees the modeller from considering the solving technology, extracting very good performance from MIP solvers for high-level CP-style MiniZinc models.

    AB - Constraint Programming (CP) standardizes many specialized “global constraints” allowing high-level modelling of combinatorial optimization and feasibility problems. Current Mixed-Integer Linear Programming (MIP) technology lacks both a modelling language and a solving mechanism based on high-level constraints. MiniZinc is a solver-independent CP modelling language. The solver interface works by translating a MiniZinc model into the simpler language FlatZinc. A specific solver can provide its own redefinition library of MiniZinc constraints. This paper describes improvements to the redefinitions for MIP solvers and to the compiler front-end. We discuss known and new translation methods, in particular we introduce a coordinated decomposition for domain constraints. The redefinition library is tested on the benchmarks of the MiniZinc Challenges 2012–2015. Experiments show that the two solving paradigms have rather diverse sets of strengths and weaknesses. We believe this is an important step for modelling languages. It illustrates that the high-level approach of recognizing and naming combinatorial substructure and using this to define a model, common to CP modellers, is equally applicable to those wishing to use MIP solving technology. It also makes the goal of solver-independent modelling one step closer. At least for prototyping, the new front-end frees the modeller from considering the solving technology, extracting very good performance from MIP solvers for high-level CP-style MiniZinc models.

    KW - Automatic reformulation

    KW - Combinatorial optimization

    KW - Context-aware reformulation

    KW - High-level modelling

    KW - Linear decomposition

    UR - http://www.scopus.com/inward/record.url?scp=84986237263&partnerID=8YFLogxK

    UR - http://link.springer.com/book/10.1007/978-3-319-44953-1

    U2 - 10.1007/978-3-319-44953-1_4

    DO - 10.1007/978-3-319-44953-1_4

    M3 - Conference Paper

    SN - 9783319449524

    T3 - Lecture Notes in Computer Science

    SP - 49

    EP - 65

    BT - Principles and Practice of Constraint Programming

    A2 - Rueher, Michel

    PB - Springer

    CY - Switzerland

    ER -

    Belov G, Stuckey PJ, Tack G, Wallace M. Improved linearization of constraint programming models. In Rueher M, editor, Principles and Practice of Constraint Programming: 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings. Switzerland: Springer. 2016. p. 49-65. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-44953-1_4