Skip to Main content Skip to Navigation
Conference papers

Range reduction using fixed points

Abstract : The efficiency of sBB depends on many parameters, among which the width of the variable ranges at each node. The fastest range reduction algorithm is called Feasibility-Based Bounds Tightening (FBBT) : it is an iterative procedure that propagates bounds up and down the expression trees [1] representing the constraints in (1), tightening them by using the constraint bounds (-?, 0]. Depending on the instance, and even limited to linear constraints only, FBBT may not converge finitely to its limit point. Tolerance-based termination criteria yield finite termination but, in general, in unbounded time (for every time bound, there is an instance exceeding it). So, although the FBBT is practically fast, its theoretical worst-case complexity status is far from satisfactory.
Document type :
Conference papers
Complete list of metadata

Cited literature [2 references]  Display  Hide  Download
Contributor : Laurence Porte Connect in order to contact the contributor
Submitted on : Tuesday, April 15, 2014 - 2:29:43 PM
Last modification on : Tuesday, October 19, 2021 - 11:02:49 AM
Long-term archiving on: : Tuesday, July 15, 2014 - 10:37:30 AM


Files produced by the author(s)


  • HAL Id : hal-00934795, version 1



Leo Liberti, Sonia Cafieri, Jon Lee. Range reduction using fixed points. ROADEF 2010, 11ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Feb 2010, Toulouse, France. ⟨hal-00934795⟩



Les métriques sont temporairement indisponibles