Revisiting subgradient techniques applied to 3d linear assignment problem

Alexandre Tusera 1 Dominique Fortin 1
1 ARCHI - Architecture
INRIA Rocquencourt
Abstract : A subgradient technique which relies on a local approximation of AP3 polytope is proposed. On the one hand, it improves over standard subgradient enhanced with a whole class of facets, since it requires far less facets; furthermore, the selected facets are more accurate with respect to the gap between a relaxed solution and a feasible one. On the other hand, it compares favorably to Bundle-Trust method which is based on a subgradient approximation. Apart from this method, a Monge sequence is devised on a substructure local to relaxed/feasible gap, that affords us to recover from zig-zagging in some pathological cases.
Type de document :
[Research Report] RR-2266, INRIA. 1994
Liste complète des métadonnées

Littérature citée [2 références]  Voir  Masquer  Télécharger
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 15:14:21
Dernière modification le : vendredi 16 septembre 2016 - 15:13:22
Document(s) archivé(s) le : mardi 12 avril 2011 - 16:52:58



  • HAL Id : inria-00074405, version 1



Alexandre Tusera, Dominique Fortin. Revisiting subgradient techniques applied to 3d linear assignment problem. [Research Report] RR-2266, INRIA. 1994. 〈inria-00074405〉



Consultations de la notice


Téléchargements de fichiers