Published on April 16, 2014
Pascal Van Hentenryck’s 1994 paper “CLP(Intervals) Revisited” was awarded the “Test of Time Award” (20 years) by the 30th International Conference on Logic Programming (ICLP) program chairs.
This paper introduced box consistency which became a key concept in global optimisation and provided exponential speedups over traditional interval analysis techniques for many benchmarks.
Box consistency was integrated in the Numerica system, which was described in a MIT Press book and commercialised by Ilog in the late mid-1990s. Interval reasoning is now widely used in global nonlinear optimisation.
The committee has considered all ICLP and ILPS papers from 1994 and have selected the paper coauthored by Frédéric Benhamou, David A. McAllester, Pascal Van Hentenryck as the one with the highest impact.
The design and implementation of constraint logic programming (CLP) languages over intervals is revisited. Instead of decomposing complex constraints in terms of simple primitive constraints as in CLP(BNR), complex constraints are manipulated as a whole, enabling more sophisticated narrowing procedures to be applied in the solver. This idea is embodied in a new CLP language, Newton, whose operational semantics is based on the notion of box-consistency, an approximation of arc-consistency, and whose implementation uses Newton interval method. Experimental results indicate that Newton outperforms existing languages by an order of magnitude and is comp etitive with some state-of-the-art tools on some standard benchmarks. Limitations of our current implementation and directions for further work are also identified.