Generalized Interval Projection: A New Technique for Consistent Domain Extension

Overview & Synopsis

This paper deals with systems of parametric equations over the reals, in the framework of interval constraint programming. As parameters vary within intervals, the solution set of a problem may have a non null volume. In these cases, an inner box (i.e., a box included in the solution set) instead of a single punctual solution is of particular interest, because it gives greater freedom for choosing a solution. Our approach is able to build an inner box for the problem starting with a single point solution, by consistently extending the domain of every variable. The key point is a new method called "generalized projection". The requirements are that each parameter must occur only once in the system, variable domains must be bounded, and each variable must occur only once in each constraint. Our extension is based on an extended algebraic structure of intervals called generalized intervals, where improper intervals are allowed (e.g. [1,0]).