Pascal Van Hentenryck’s 1994 paper, ‘CLP (Intervals) Revisited’ has been awarded the ‘Test of Time Award’ by the International Conference on Logic Programming. The award is presented to the most influential paper over 20 years old.
The original paper, co-authored with David McAllester and Frédéric Benhamou, introduced the concept of box consistency in constraint programming that produced dramatic improvements in efficiency over traditional interval analysis techniques in solving nonlinear equations.
Pascal describes the time he spent working on the paper as “productive and really fun”.
“This research started during my sabbatical at MIT where I visited David McAllester. When David and I first implemented this idea, we could not believe that the algorithm solved these standard benchmarks so quickly, but David and I had programmed the algorithm independently so we became really excited. I then spent six months in Marseilles where Frederic and I formalised the pruning principles declaratively. Our ideas were then refined, expanded, and adopted by many researchers and systems.”
Box consistency became the core of the Numerical system for global optimisation as described in a MIT Press book (co-authored with Laurent Michel and Yves Deville) and were embedded in a number of commercial and academic systems.
Pascal is thrilled that his paper won the ‘Test of Time Award’ and believes that it will continue to be relevant in another 20 years’ time.
“Box consistency, its generalisations, and their associated pruning algorithms are a key part of modern global optimisation systems. Together with convex relaxations, these concepts are an integral part of the nonlinear optimisation systems the NICTA optimisation group in Canberra is building for the optimal design of coupled electric power and natural gas systems, a collaborative project with Los Alamos National Laboratories.”
Pascal has been invited to attend the conference in Vienna this July to accept his award and conduct a presentation on the winning paper