Interval linear programming techniques in constraint programming and global optimization

Abstract

We consider a constraint programming problem described by a system of nonlinear equations and inequalities; the objective is to tightly enclose all solutions. First, we linearize the constraints to get an interval linear system of equations and inequalities.

Then, we adapt techniques from interval linear programming to find a polyhedral relaxation to the solution set. The linearization depends on a selection of the relaxation center; we discuss various choices and give some recommendations.

The overall procedure can be iterated and thus serves as a contractor.

Keywords

• Interval computation
• linear programming
• constraint programming
• global optimization