Combining Intervals and Constraint Processing

I have been working since about 1988 with a technology that combines intervals and constraint processing. The particular combination that I am most familiar with is called CLP(BNR) and was developed originally as a sub-system of BNR Prolog during 1988-1992, based on a paper by Dr. John Cleary. Since then other combinations , variants, and improvements have been made : Prolog IV, ILOG, Newton, Helios,...

The classical interval techniques can improve the numerical reliability of computation, but leave the traditional functional & iterative structure more or less intact; consequently, there is still a need for algorithms to control the computation (although intervals do provide an opportunity for some novel algorithms) as well as much work to formulate problems in functional terms. When intervals are coupled with constraint concepts, however, one gets a much more radical change as most "control" either disappears completely or gets relegated into some global policy parameters; in place of algorithms one has mostly just (very carefully chosen) statements of the problem and boundary conditions (including their precision!). To a large extent, the same mathematical formulation can be used regardless of which data is given and which is to be sought. Approximate knowledge, asymptotes, limiting cases etc. can all be tossed into the mix and will automatically be used whenever possible. Non-linearities and consequently multiple solutions are in this framework no longer so problematic generally. This technology is still young and really big problems (on the order of weather forecasting say) haven't been tried as yet, but there have been a number of impressive (and little publicized) successes on more modest problems for which conventional solutions are very difficult or (practically) unworkable (because e.g. they get bogged down in overwhelming complexity ).

Two of the characteristics of this technology deserve special mention: one is that the overall computational structure is logic ( a sort of intuitionit predicate calculus ), and as a consequence general programs for a class of problems tend to have the same sort of structure as the corresponding theory; i.e. the wide gap between "theory" and "code" is absent and numerical computations are always essentially proofs.

Second, and still puzzling, is that what is regarded as hard vs easy in this technology is usually very different than in traditional approaches, in many cases almost the opposite. One aspect of this which has major consequences is that, traditionally, one leaves out "details" of a physical problem in order to regularize its mathematical expression, and solution techniques are oriented around these somewhat abstract mathematical idealizations, but we have found that with CLP(BNR) it can be much more effective--and sometimes necessary-- to deal with the problem in its specific, concrete and detailed form.

Bill Older

Back to Generalized Interval Arithmetic and its Applications

Back to the main menu of the Interval Computations website