ICOS: a branch and bound based solver for rigorous global optimization

Abstract

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.

Keywords:

• global optimization
• interval analysis
• constraint programming
• problem solving

AMS Subject Classification :

• 90C26
• 65G40
• 68T20
• 68N01

Acknowledgements

First I want to thank Michel Rueher and Claude Michel for their support and advice. I wish to thank Olivier Lhomme who supported the author during the first development of the ICOS system. I thank Oleg Shcherbina for testing ICOS on nonlinear systems within the COCONUT project. I thank Hans Mittelmann for introducing ICOS in NEOS server. I wish also to thank Arnold Neumaier for his advice and support in 2006 during the Vienna visit. The author would like to acknowledge reviewers for helpful comments.

Notes

A feasible point x′ is a local minimum if for a small ε, any feasible point x having |x _i −x′ _i <ε, f(x)≥f(x′).We recall that the feasible region of Equation (1) is the set of points that satisfy the m constraints of Equation (1).

Any point x in the feasible region for which f(x)≥f(xˇ) for all points x in the feasible region is a global minimum.

In interval analysis terminology, a feasible or safe box is a vector of intervals where there is a mathematical proof that the box contains a unique solution.

ASTs are well established in compiler construction where they provide an efficient data structure to handle the program however complex it is. An AST is a finite, labelled, directed tree, where each interior node represents a programming language construct and the children of that node represent computation components of the construct.

Words with only lower-case letters are terminals. Words beginning with one single capital letter are non-terminals. Repeated terms are compacted with Term{,Term} where Term is the repeated term, and “,” is the separating symbol. For instance, LocSolver{,LocSolver} denotes a sequence of LocSolver.