Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

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.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

Littérature citée [2 références]  Voir  Masquer  Télécharger

https://hal-enac.archives-ouvertes.fr/hal-00934795
Contributeur : Laurence Porte Connectez-vous pour contacter le contributeur
Soumis le : mardi 15 avril 2014 - 14:29:43
Dernière modification le : mardi 19 octobre 2021 - 11:02:49
Archivage à long terme le : : mardi 15 juillet 2014 - 10:37:30

Fichier

171.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00934795, version 1

Collections

Citation

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⟩

Partager

Métriques

Consultations de la notice

206

Téléchargements de fichiers

51