https://hal-enac.archives-ouvertes.fr/hal-00935464Belotti, PietroPietroBelottiDepartment of Mathematical Sciences - Clemson UniversityCafieri, SoniaSoniaCafieriMAIAA - ENAC - Laboratoire de Mathématiques Appliquées, Informatique et Automatique pour l'Aérien - ENAC - Ecole Nationale de l'Aviation CivileLee, JonJonLeeUniversity of Michigan [Ann Arbor] - University of Michigan SystemLiberti, LeoLeoLibertiLIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau] - X - École polytechnique - CNRS - Centre National de la Recherche ScientifiqueOn feasibility based bounds tighteningHAL CCSD2012global optimizationMINLPspatial Branch-and-Boundrange reduction[MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC]Porte, Laurence2014-04-08 16:15:002023-03-24 14:52:582014-04-08 16:20:05enOther publicationsapplication/pdf1Mathematical programming problems involving nonconvexities are usually solved to optimality using a (spatial) Branch-and-Bound algorithm. Algorithmic e?ciency depends on many factors, among which the widths of the bounding box for the problem variables at each Branch-and-Bound node naturally plays a critical role. The practically fastest box-tightening algorithm is known as FBBT (Feasibility-Based Bounds Tightening): an iterative procedure to tighten the variable ranges. Depending on the instance, FBBT may not converge ?nitely to its limit ranges, even in the case of linear constraints. Tolerance-based termination criteria yield ?nite termination, but not in worstcase polynomial-time. We model FBBT by using ?xed-point equations in terms of the variable bounding box, and we treat these equations as constraints of an auxiliary mathematical program. We demonstrate that the auxiliary mathematical problem is a linear program, which can of course be solved in polynomial time. We demonstrate the usefulness of our approach by improving an existing Branch-and-Bound implementation. global optimization, MINLP, spatial Branch-and-Bound, range reduction.