next up previous contents
Next: The propia (Generalised Propagation) Up: ECLiPSe : A Previous: The eplex (External CPLEX

Complex Constraints

  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 tex2html_wrap_inline1376 , end times tex2html_wrap_inline1378 and resources tex2html_wrap_inline1380 of the two tasks. The specification of this constraint is as follows:

either the two tasks use distinct resource ( tex2html_wrap_inline1382 ) or task tex2html_wrap_inline1384 ends before task tex2html_wrap_inline1386 starts ( tex2html_wrap_inline1388 ) or else task tex2html_wrap_inline1386 ends before task tex2html_wrap_inline1384 starts ( tex2html_wrap_inline1394 ).
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.gif It also comes because, until the boolean variables take a value very close to 0 they have very little effect on the search.gif

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.

Joachim Schimpf
Wed Sep 3 18:07:19 BST 1997