|Article: Electronic||Free Download|
Combinatorial (optimization) problems appear in many real life applications, such as planning, scheduling, timetabling, routing, placement, investment, DNA sequencing. Tackling combinatorial(optimization) problems include two steps: modelling and solving.
There are three main approaches for solving these problems: mathematical methods(includes Linear Programming(LP), Integer Programming(IP) and Mixed Integer Programming (MIP)), Constraint Programming(CP) and Local Search(LS).
For modelling combinatorial (optimization) problems there are many tools of which three categories are most relevant to our current research: constraint programming languages, constraint programming libraries and mathematical modelling languages.
Modelling languages provide the best approach to the modelling, since they do not require sophisticated programming skills. However, a limitation of current modelling languages is that they do not support true solver independent modelling. The reason why this is important is that none of the current solving techniques: MIP, CP or LS is uniformly better and often experiment is required to see which one is the best for a particular application. Thus we would like to be able to use the same model with solvers supporting three different techniques.
In this project, we plan to develop a new solver independent modelling language named Zinc. Zinc also supports: high-level modelling, user defined constraints, optimization problems and soft constraints.
|Keywords:||Combinatorial optimization problems, Constraint Programming, Modelling Languages, Solving techniques, Solver independency|
Article: Electronic (PDF File; 535.643KB). Published by The Open Source Developers' Conference Papers.