Optimization Online


A Reliable Affine Relaxation Method for Global Optimization

Jordan Ninin(jordan.ninin***at***ensta-bretagne.fr)
Frederic Messine(frederic.messine***at***enseeiht.fr)
Pierre Hansen(pierre.hansen***at***gerad.ca)

Abstract: 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. These linear programs 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 infeasibility is inserted into a classical Branch and Bound algorithm based on interval analysis. Extensive computation experiments were made on a sample of 74 problems from the COCONUT database with up to 24 variables or 17 constraints; 61 of these were solved, and 30 of them for the first time, with a guaranteed upper 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, and 5 more with a CPU-time not exceeding 2 minutes.

Keywords: affine arithmetic, interval analysis, linear relaxation, Branch and Bound, global optimization

Category 1: Global Optimization (Theory )

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )


Download: [PDF]

Entry Submitted: 10/23/2012
Entry Accepted: 10/23/2012
Entry Last Modified: 10/23/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society