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 metadatas

Cited literature [2 references]  Display  Hide  Download

https://hal-enac.archives-ouvertes.fr/hal-00934795
Contributor : Laurence Porte <>
Submitted on : Tuesday, April 15, 2014 - 2:29:43 PM
Last modification on : Tuesday, October 20, 2020 - 10:32:06 AM
Long-term archiving on: : Tuesday, July 15, 2014 - 10:37:30 AM

File

171.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

536

Files downloads

72