Méthode de gradients en optimisation combinatoire. Applications à un problème de sac à dos et au modèle d'Ising

Résumé : On présente des heuristiques pour l'optimisation combinatoire en variables binaires. Ces heuristiques s'inspirent de descentes de gradients dans un espace des phases randomisé, coordonnée par coordonnée. On considère donc le problème d'optimisation comme un jeu à deux joueurs, le chercheur contre la ${\cal N}$\hspace{-2pt}ature. On obtient un algorithme quadratique pour le problème du sac à dos, extrêmement efficace en pratique. De plus on fournit une interprétation probabiliste à un algorithme de P. Rivière pour le problème d'Ising \cite{Riv}, dont on explique ainsi l'efficacité.
Type de document :
Rapport
RR-2537, INRIA. 1995
Liste complète des métadonnées

https://hal.inria.fr/inria-00074141
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 14:36:30
Dernière modification le : samedi 27 janvier 2018 - 01:31:28
Document(s) archivé(s) le : jeudi 24 mars 2011 - 14:22:15

Fichiers

Identifiants

  • HAL Id : inria-00074141, version 1

Collections

Citation

Stéphane Crepey. Méthode de gradients en optimisation combinatoire. Applications à un problème de sac à dos et au modèle d'Ising. RR-2537, INRIA. 1995. 〈inria-00074141〉

Partager

Métriques

Consultations de la notice

137

Téléchargements de fichiers

216