Delay of Nonlinear Constraints

   

In the above discussion of the operational model, we saw how each operational step results in one or more constraints being added to the collected constraint set, and the new set being checked for satisfiability. Because of efficiency requirements, there is a limit to how sophisticated the decision algorithm for constraints can be, and consequently the collected constraint set may get too complicated for the decision algorithm. In particular, consider a case when the collected constraint set is solvable, but one constraint is added that makes the set so complicated that it is not practical to decide whether it has remained solvable.

A naive approach to dealing with this problem is simply to disallow expressions that can result in such complexity. This is tantamount to disallowing all nonlinear constraints. The loss in expressive power is, however, unacceptable. Instead, CLP( ) allows nonlinear constraints but keeps them in a delayed constraint set. More precisely, at each operational step, instead of blindly adding each constraint to the collected constraint set and incurring the cost of performing a satisfiability test, we remove certain constraints that would make the set too complicated. We keep these removed constraints in the delayed constraint set. Additionally, at each step it is possible that some constraint in the delayed constraint set need no longer be delayed because of new information. In this case it should be moved from the delayed constraint set to the collected constraint set and the usual solvability check made. Note that, in general, the notion of which expressions are ``too complicated'' is dependent on the implementation. In CLP( ) only the nonlinear constraints are delayed.

Now let us consider an example where the collected constraint set is initially empty; then suppose we obtain the constraint

		 V = I * R.

This is placed in the delayed constraint set. Continuing, if the next constraint is

		 V = 10

it may be added to the collected constraint set, but note that it is still not easy to decide whether the two constraints together are solvable Now consider what happens if the next constraint is

		 R = 5.

This gives us enough information to make the delayed constraint linear, so we simply remove this constraint from the delayed constraint set, place it in the collected constraint set, and check that it is solvable, which of course it is. Note that the delayed constraint set may have contained other constraints, which may have to remain there until much later. Also note that because of this delay mechanism, we may continue through a certain computation sequence even though the collected and delayed constraint sets together are not solvable. In the worst case it can result in an infinite loop. This is the price we pay for an efficient decision algorithm.

As we have already stated, in the CLP( ) system a linear equation or inequality is always considered to be sufficiently simple to be solved immediately, but nonlinear constraints are delayed until they become linear. bsphackfloatpenalty -Mii floatpenalty-Miii parmoderrfloatpenalty@ nextcurrboxfreelist currbox-2floatpenalty@ fltovf currboxtempboxa tempboxa @floatesphackbsphackfloatpenalty -Mii floatpenalty-Miii parmoderrfloatpenalty@ nextcurrboxfreelist currbox-3floatpenalty@ fltovf currboxtempboxa tempboxa @floatesphack This includes the functions sin/1, arcsin/1, cos/1, arccos/1, pow/2, max/2, min/2 and abs/1            which are delayed until they become simple evaluations in one direction or another. bsphackfloatpenalty -Mii floatpenalty-Miii parmoderrfloatpenalty@ nextcurrboxfreelist currbox-4floatpenalty@ fltovf currboxtempboxa tempboxa @floatesphack This means that sin and cos require the input to be ground, while pow requires at least two out of three arguments to be ground, except in cases such as

		 X = pow(Y, Z)

where Z = 0. The reason is that is defined to be 1 for all values of Y. Note that while this is sufficient to determine the value of X, Y remains non-ground. There are similar special cases when Z is 1, and when Y is 0 or 1. bsphackfloatpenalty -Mii floatpenalty-Miii parmoderrfloatpenalty@ nextcurrboxfreelist currbox-2floatpenalty@ fltovf currboxtempboxa tempboxa @floatesphackbsphackfloatpenalty -Mii floatpenalty-Miii parmoderrfloatpenalty@ nextcurrboxfreelist currbox-3floatpenalty@ fltovf currboxtempboxa tempboxa @floatesphack The functions arcsin and arccos are delayed until either the input is ground or the result of the function is ground. They are also different in that they are functions and the input domain for arcsin ranges from to and arccos from 0 to whereas sin and cos are defined for any number in radians. Thus sin and cos behave as relations which is non-invertible while arcsin and arccos are true functions which are invertible. See Section 5.2 for a more precise definition of the delaying conditions for the different nonlinear functions. bsphackfloatpenalty -Mii floatpenalty-Miii parmoderrfloatpenalty@ nextcurrboxfreelist currbox-4floatpenalty@ fltovf currboxtempboxa tempboxa @floatesphack

As a final example, consider the mortgage program in Chapter 2, and consider the goal:

		 ?-  mortgage(120, 2, IR, 0, 80).

This will give rise to nonlinear constraints, and the system returns a quadratic equation as the answer constraint:

		 80 = (0.1*IR + 40) * (0.000833333*IR + 1)

and indicates that this is an unsolved answer. Note that while CLP( ) cannot determine whether this equation is solvable, the equation indeed describes the correct answer.