Numerical constraint systems are often handled by branch and prune algorithms that combine splitting techniques, local consistencies, and interval methods. This paper first recalls the principles of {\tt Quad}, a global constraint that works on a tight and safe linear relaxation of quadratic subsystems of constraints. Then, it introduces a generalization of {\tt Quad} to polynomial constraint systems. It also introduces a method to get safe linear relaxations and shows how to compute safe bounds of the variables of the linear constraint system. Different linearization techniques are investigated to limit the number of generated constraints. {\tt QuadSolver}, a new branch and prune algorithm that combines {\tt Quad}, local consistencies, and interval methods, is introduced. {\tt QuadSolver} has been evaluated on a variety of benchmarks from kinematics, mechanics, and robotics. On these benchmarks, it outperforms classical interval methods as well as constraint satisfaction problem solvers and it compares well with state-of-the-art optimization solvers.
1 February 2007 in Journal of Computational and Applied Mathematics
This article describes a software package called Interval Constraint Solver (ICOS), which implements a branch and bound algorithm for rigorously solving global optimization problems. The ICOS library contains algorithms coming from constraint programming, interval analysis, and linear relaxation techniques. It contains an interface to linear programming solvers and local optimization solvers (e.g. Coin/Clp, Cplex, and IpOpt). ICOS has also its own AMPL parser, which enables calling ICOS binary code in a Unix-like command. The ICOS strategy language enables combining and parameterizing existing algorithms for solving optimization problems. Thus, the user can develop his own solving strategies without changing anything in the ICOS internal architecture. Various examples are given to show how the strategy language can be used. We give an overview of ICOS design, implementation, and a quick user’s guide.