Introduction

Combinatorial problems are a special class of problems involving decision variables and constraints. Constraints dictate the architecture and fundamental properties of the problem. More importantly, constraints describe the expected outcome of the decision variables, by specifying their domain. Typical combinatorial problems are timetabling, staff scheduling, resource allocation, planning and the travelling salesman problem (TSP). Most combinatorial problems are classified under the NP-hard problem category and, therefore, there is no known algorithm to solve them in polynomial time. As the dimension of the problem increases, the time needed to solve the problem grows exponentially. Unfortunately, large organisations encounter these problems on a day-to-day basis, and the lack of an efficient algorithm affects the effective utilization of their resources. Since resources often constitute a big part of total cost in large organisations, efficient solving of staff scheduling for instance can end up saving thousands and even millions of dollar.

The need to solve combinatorial problems effectively has attracted much attention from the research community and remains as one of the most actively researched areas. Consequently, the research community has devoted a lot of effort to address this issue computationally. This has resulted in three main approaches of solving combinatorial problems, namely Operation Research (OR) also widely known as Mathematical Programming(##Winston ##Winston), Constraint Programming and meta-heuristic(##heuristic ##heuristic) (normally associated with Artificial Intelligence (AI)).

Mathematical programming uses equation solving techniques to solve combinatorial problems. In contrast to Mathematical Programming, constraint programming focuses more on applying a judicious search strategy that exploits the problem structure to enumerate possible solution in an efficient manner. Meta-heuristic is an ad-hoc approach in which the search algorithm is based on a collection of heuristics techniques (or ``rules of thumb''). These heuristics techniques range from probabilistic and memory-based to actual simulation of natural processes.

All three fields have developed substantially over the years and obtained variable degrees of success. Generally, if a combinatorial problem needs an optimal solution, then mathematical programming techniques such as Simplex would seem a good fit provided the problem could be modelled as linear equations. However, if only a feasible solution is required, the problem is a good candidate for applying constraint programming techniques. The application of meta-heuristic techniques in combinatorial solving are not well understood. Due to this uncertainty, meta-heuristic techniques often served as an alternative approach when the other two techniques could not produce desired solutions.

Even though all three approaches have orthogonal strengths and weaknesses, researchers generally agreed that hybrid algorithms generate better results compare to conventional approaches (##Hooker2000 ##Hooker2000). Although solving techniques play a big part in combinatorial problem solving, there are other issues involved to ensure a combinatorial problem is solved efficiently. One such issue is modelling. A problem that is represented inaccurately can affect the solving efficiency. Modelling languages are tools that facilitate the task of modelling. In particular, they allow the user to apply solving techniques without understanding the underlying working mechanism.

In this paper, attention is paid to literatures that cover different aspects of a modelling language and different approaches towards modelling. In doing so, we hope to gain some insights to assist in the research of adding modelling capabilites onto HAL, a constraint logic programming language.

In Section 2, we defined the formal definition of constraint solving and constraint optimization. In Section 3, we discuss solver techniques arise from mathematical programming, constraint programming and meta-heuristic. In Section 4, different tools that facilitate the application of solving techniques are discussed. Finally, in section 5, modelling languages are discussed.