Whilst constraint programming languages offer a broad selection of built-in constraints, each new industrial application typically requires a number of application-specific constraints which aren't among the built-in constraints.
Let us take, as an ongoing example, the constraint that two tasks sharing a single resource cannot be done at the same time. This constraint was introduced in section 2.2.2 above.
The constraint involves six variables: the start times , end times and resources of the two tasks. The specification of this constraint is as follows:
either the two tasks use distinct resource ( ) or task ends before task starts ( ) or else task ends before task starts ( ).We shall compare three different ways of handling this constraint.
First we recall how it can be encoded using numerical equations and inequalities, together with integer constraints. This is the encoding necessary to allow it to be solved using MIP algorithms, as available through the eplex library. However the MIP package is not necessarily the best algorithm for handling such a constraint.
Indeed experience with practical applications suggests that the more 0/1 variables it is necessary to introduce to handle each constraint, the less efficient MIP becomes. The inefficiency comes partly because the MIP constraints are handled globally, and the cost of handling extra constraints and boolean variables increases very fast with their number. It also comes because, until the boolean variables take a value very close to 0 they have very little effect on the search.
By contrast we shall show how it can be handled using two further libraries of ECLiPSe - the propia library and the chr library. These libraries allow the constraint to be modelled much more simply and handled more efficiently.