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

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.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal-enac.archives-ouvertes.fr/hal-00940949
Contributeur : Laurence Porte Connectez-vous pour contacter le contributeur
Soumis le : mardi 25 mars 2014 - 11:50:11
Dernière modification le : mardi 19 octobre 2021 - 11:02:49
Archivage à long terme le : : mercredi 25 juin 2014 - 10:38:35

Fichier

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

Identifiants

  • HAL Id : hal-00940949, version 1

Collections

Citation

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⟩

Partager

Métriques

Consultations de la notice

201

Téléchargements de fichiers

117