Solving combinatorial optimisation problems, such as scheduling or timetabling, is a difficult and time-consuming task which often depends on two factors: finding a good model and developing problem-specific heuristics. High level modeling languages support a syntax close to the usual problem notation (e.g. mathematical notation) and allow their users to design a model without considering low implementation details such as memory usage. These features greatly simplify the task of finding good models but, since they are not general purpose languages, their capabilities to specify problem-specific heuristics is very limited. Constraint programming languages are generic programming languages specifically designed to solve combinatorial problems, allowing the user to implement virtually any customised technique required to solve them. Unfortunately, they usually lack support for high-level modeling. The aim of this project is to investigate the possibility of providing high-level modeling support to the constraint programming language HAL and, in particular, to support the modeling capabilities of OPL, a popular and powerful high-level modeling language for describing combinatorial problems. In order to achieve this aims, two orthogonal approaches will be pursued: extending HAL with a modeling library (obtaining what we call HAL++), and developing an OPL-to-HAL++ compiler.
 
Core References

Pascal Van Hentenryck. The OPL Optimization Programming Language. The MIT Press, Cambridge, Massachusetts. 1999.

Laurent Michel, Pascal van Hentenryck. Modeler++: A Modeling Layer for Constraint Programming Libraries. Brown University.

Student
Virginia Lee
 
Supervisor
Maria Garcia de la Banda, Kim Marriott
 
Type
Bachelor Computer Science (Honours)
 
Project Start
February 2002
 
Completion
November 2002