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

Feasibility-Based Bounds Tightening via Fixed Points

Abstract : The search tree size of the spatial Branch-and-Bound algorithm for Mixed-Integer Nonlinear Programming depends on many factors, one of which is the width of the variable ranges at every tree node. A range reduction technique often employed is called Feasibility Based Bounds Tightening, which is known to be practically fast, and is thus deployed at every node of the search tree. From time to time, however, this technique fails to converge to its limit point in finite time, thereby slowing the whole Branch-and-Bound search considerably. In this paper we propose a polynomial time method, based on solving a linear program, for computing the limit point of the Feasibility Based Bounds Tightening algorithm applied to linear equality and inequality constraints.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal-enac.archives-ouvertes.fr/hal-00979219
Contributeur : Céline Smith Connectez-vous pour contacter le contributeur
Soumis le : mardi 15 avril 2014 - 15:28:37
Dernière modification le : mardi 19 octobre 2021 - 11:02:49

Lien texte intégral

Identifiants

Collections

Citation

Pietro Belotti, Sonia Cafieri, Jon Lee, Leo Liberti. Feasibility-Based Bounds Tightening via Fixed Points. COCOA 2010, 4th Annual International Conference on Combinatorial Optimization and Applications, Dec 2010, Kailua-Kona, United States. pp 65-76, ⟨10.1007/978-3-642-17458-2_7⟩. ⟨hal-00979219⟩

Partager

Métriques

Consultations de la notice

95