Introduction
Project Introduction
The use of constraint programming languages to solve combinatorial optimization problems is unpopular. This is due to their lack of support for high-level modelling features, which makes the resulting models cumbersome and requires the modeller to posses sophisticated programming skills. Consequently, users of constraint programming languages are usually limited to computer scientists and programmers. Modelling languages on the other hand offer an alternative method for solving combinatorial problems by supporting high-level modelling features. However, modelling languages have their drawbacks such as the inability to implement problem specific heuristics to obtain good solutions. One way to remedy this situation is to add high-level modelling support to constraint programming languages.
Background
Combinatorial optimisation problems such as scheduling or timetabling are an important class of NP-hard problems. Solving these problems is both a hard and time-consuming process. Often finding a good solution requires problem specific heuristics and an appropriate model of the problem. A good model representation abstracts the problem accurately, while leaving out unnecessary details.
There are two standard approaches in modelling combinatorial optimisation problems. The first approach is based on mathematical modelling languages, the second approach is based on constraint programming languages. The difference between mathematical modelling languages and constraint programming languages is how constraint optimisation problems are modelled. Mathematical modelling languages have a higher-level syntax that enables user to view a problem at a higher-level without the implementation details. Users are not required to posses sophisticated programming skills in order to use it. As a result, it allows the user to focus on how to model a problem more accurately. However, because modelling languages are not full-fledged programming languages there are limited ways where the user can customize the behaviour of the model.
As for constraint programming languages, they generally have a lower level syntax compared to modelling languages. As a full-fledged programming language, constraint programming languages allow user to customize the behaviour of the model. On the downside, as a programming language, in return it also requires the user to posses some sophisticated programming skills. Due to this requirements, the user has to take care of both aspects of modelling and programming of the problems. Consequently, it widens the distance between the model and the actual problem representation.
OPL
OPL stands for Optimization Programming Language, it is a modelling language specifically designed for solving combinatorial optimisation problems. OPL offers some new features not available in other modelling languages such as hybrid modelling styles, ability to customize search procedures and a specialised data type for solving scheduling problems. All these new features make OPL a powerful and expressive language. However, because OPL is not a full-fledged programming language, there is a limit to how a user can customized the search proceduce.
HAL
HAL is a constraint logic programming language. It is jointly developed in Monash University and Melbourne University. HAL was specifically designed to overcome the problems in existing constraint programming languages. However, HAL has the same problem that is inherent it most constraint programming languages, that is, the lack of support for high-level modelling. One example is the use of recursion as the only form of specifying iteration. This problem of HAL can affect the efficient solving of a problem.
Project Aim
As we can see from the above, HAL's lack of high-level modelling support can affect how a problem can be solved efficiently. Therefore, the aim of this project is therefore to provide high-level modelling support for HAL.
Page last updated : November 10, 2002