On the convergence of feasibility based bounds tightening
Résumé
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.
Origine : Fichiers produits par l'(les) auteur(s)