Arrêt de service programmé du vendredi 10 juin 16h jusqu’au lundi 13 juin 9h. Pour en savoir plus
Accéder directement au contenu Accéder directement à la navigation
Autre publication

On feasibility based bounds tightening

Abstract : Mathematical 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.
Type de document :
Autre publication
Liste complète des métadonnées

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

https://hal-enac.archives-ouvertes.fr/hal-00935464
Contributeur : Laurence Porte Connectez-vous pour contacter le contributeur
Soumis le : mardi 8 avril 2014 - 16:15:00
Dernière modification le : mardi 19 octobre 2021 - 11:02:48
Archivage à long terme le : : mardi 8 juillet 2014 - 10:46:25

Fichier

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

Identifiants

  • HAL Id : hal-00935464, version 1

Collections

Citation

Pietro Belotti, Sonia Cafieri, Jon Lee, Leo Liberti. On feasibility based bounds tightening. 2012. ⟨hal-00935464⟩

Partager

Métriques

Consultations de la notice

305

Téléchargements de fichiers

952