%0 Journal Article
%T A reliable affine relaxation method for global optimization
%+ Lab-STICC_ENSTAB_CID_IHSEV ; OSM
%+ Département STIC [Brest] (STIC)
%+ Groupe de Recherches en Electrodynamique (LAPLACE-GREM3)
%+ Groupe d'études et de recherche en analyse des décisions (GERAD & HEC Montréal)
%A Ninin, Jordan
%A Messine, Frédéric
%A Hansen, Pierre
%< avec comité de lecture
%@ 1619-4500
%J 4OR: A Quarterly Journal of Operations Research
%I Springer Verlag
%V 13
%N 3
%P 247-277
%8 2015-09
%D 2015
%R 10.1007/s10288-014-0269-0
%Z 90C26 65H20 65G30 65G40 49M20
%Z Computer Science [cs]/Operations Research [cs.RO]
%Z Mathematics [math]/Optimization and Control [math.OC]Journal articles
%X 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 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 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.
%G English
%2 https://hal.science/hal-01194735/document
%2 https://hal.science/hal-01194735/file/NININ_MESSINE_HANSEN_no.pdf
%L hal-01194735
%U https://hal.science/hal-01194735
%~ ENSTA-BRETAGNE
%~ UNIV-TLSE3
%~ CNRS
%~ ENSTA-BRETAGNE-STIC
%~ INSMI
%~ SMS
%~ LAB-STICC
%~ TDS-MACS
%~ LAPLACE
%~ LAPLACE_GREM3
%~ TOULOUSE-INP
%~ UNIV-UT3
%~ UT3-INP
%~ UT3-TOULOUSEINP