Groupe d’études et de recherche en analyse des décisions

G-2010-31

A Reliable Affine Relaxation Method for Global Optimization

, et

An automatic method for constructing linear relaxations of constrained global optimization problems is proposed. Such a construction is based on affine and interval arithmetics and uses operator overloading. The linear programs so-generated have exactly the same numbers of variables and of inequality constraints as the given problems. Each equality constraint is replaced by two inequalities. This new procedure for computing reliable bounds and certificates of unfeasibility is inserted within a classical interval Branch and Bound algorithm. Extensive computation experiments were made on a sample of 74 problems from the COCONUT database with up to 24 variables and 17 constraints; 64 of these were solved, and 32 of them for the first time, with a certified lower bound on the relative error equal to 10-8. Moreover this sample comprises 39 examples to which the GlobSol algorithm was recently applied finding reliable solutions in 32 cases. The proposed method allows solving 31 of these 32, and 5 more with a CPU-time never exceeding 2 minutes.

, 27 pages