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.
| Language | English |
|---|---|
| Title of host publication | Principles and Practice of Constraint Programming |
| Subtitle of host publication | 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings |
| Editors | Michel Rueher |
| Place of Publication | Switzerland |
| Publisher | Springer |
| Pages | 49-65 |
| Number of pages | 17 |
| ISBN (Electronic) | 9783319449531 |
| ISBN (Print) | 9783319449524 |
| DOIs | |
| State | Published - 2016 |
| Event | International Conference on Principles and Practice of Constraint Programming 2016 - Toulouse, France Duration: 5 Sep 2016 → 9 Sep 2016 Conference number: 22d http://cp2016.a4cp.org/ |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Volume | 9892 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | International Conference on Principles and Practice of Constraint Programming 2016 |
|---|---|
| Abbreviated title | CP 2016 |
| Country | France |
| City | Toulouse |
| Period | 5/09/16 → 9/09/16 |
| Internet address |
Keywords
- Automatic reformulation
- Combinatorial optimization
- Context-aware reformulation
- High-level modelling
- Linear decomposition
Cite this
}
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 proceeding › Conference Paper
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
PB - Springer
CY - Switzerland
ER -