Skip to Main content Skip to Navigation
Conference papers

On the convergence of feasibility based bounds tightening

Abstract : Global Optimization and Mixed-Integer Nonlinear Programming problems such as min{f(x) | gL ≤ g(x) ≤ gU ∧ xL ≤ x ≤ xU ∧ ∀j ∈ Z (xj ∈ Z)}, where f : Rn → R, g : Rn → Rm, gL, gU ∈ Rm, xL, x, xU ∈ Rn and Z ⊆ {1, . . . , n},are usually solved to "-guaranteed approximation by the spatial Branch-and-Bound (sBB) algorithm [2], a variant of the usual Branch-and-Bound for dealing with nonlinear, possibly nonconvex f, g. Since the gap between the original problem P and its convex relaxation ¯ P is due both to integral variable restrictions being lifted as well as nonconvex functions being replaced by a convex relaxation, sBB is able to branch at continuous variables as well as integer ones. If ¯x solves ¯ P, the standard disjunction used at a node in the sBB search tree is xj ≤ ¯xj ∨xj ≥ ¯xj , the more usual one xj ≤ ⌊¯xj⌋∨xj ≥ ⌈¯xj⌉ being used only if j ∈ Z.
Document type :
Conference papers
Complete list of metadatas
Contributor : Laurence Porte <>
Submitted on : Tuesday, March 25, 2014 - 11:50:11 AM
Last modification on : Tuesday, October 20, 2020 - 10:32:06 AM
Long-term archiving on: : Wednesday, June 25, 2014 - 10:38:35 AM


Files produced by the author(s)


  • HAL Id : hal-00940949, version 1



Pietro Belotti, Sonia Cafieri, Jon Lee, Leo Liberti. On the convergence of feasibility based bounds tightening. CTW 2010, 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, May 2010, Cologne, Germany. pp xxxx. ⟨hal-00940949⟩



Record views


Files downloads