Skip to Main content Skip to Navigation
Reports

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é.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00074141
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 2:36:30 PM
Last modification on : Saturday, January 27, 2018 - 1:31:28 AM
Long-term archiving on: : Thursday, March 24, 2011 - 2:22:15 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

187

Files downloads

368