Range reduction using fixed points - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année :

Range reduction using fixed points


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.
Fichier principal
Vignette du fichier
171.pdf (71.02 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00934795 , version 1 (15-04-2014)


  • 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⟩
215 Consultations
59 Téléchargements


Gmail Facebook Twitter LinkedIn More