Des personnes d'horizons différents rejoignent l'équipe de recherche opérationnelle de Google. Certains sont diplômés et reconnus dans leur domaine. D'autres sont d'excellents ingénieurs logiciels enthousiastes à l'idée d'apprendre l'optimisation mathématique.
Parfois, les ingénieurs logiciels demandent aux experts OR comment en savoir plus sur l'opérateur OR. Nous avons commencé à recueillir nos réponses dans un document, dont l'extrait ci-dessous contient les réponses. Il s'agit des opinions de Googleurs individuels, et non des approbations officielles de Google. Nous espérons que vous apprécierez les écoutes clandestines de notre équipe !
CLOM
| Cours | Auteur | Remarques | Commentaires |
|---|---|---|---|
| Cours Coursera sur l'optimisation discrète | van Hentenryck | MIP et CP | J'ai adoré. Vous n'avez pas encore terminé l'ensemble de problèmes. |
| Modélisation de base pour une optimisation discrète | Lee et Stuckey | Priorité à la protection des données | |
| Modélisation avancée pour une optimisation discrète | Lee et Stuckey | ||
| Résolution d'algorithmes d'optimisation discrète | Lee et Stuckey | ||
| Modélisation et résolution des problèmes d'IA dans Picat | Barták | ||
| OU(1): Modèles et applications | Kung | Zaphod@: Ces deux exemples constituent une excellente introduction à tout ce qui concerne les pages de destination et les adresses IP. | |
| OU(2): algorithmes d'optimisation | Kung | ||
| OU(3): théorie | Kung |
Principes de base de la page de destination et du MIP
| Reprise | Titre | Auteur | Commentaires |
|---|---|---|---|
 |
Présentation de l'optimisation linéaire | Bertsimas et Tsitsiklis | BlackLotus@: Pour LP (et dans une moindre mesure MIP), je pense que ce livre est le meilleur. Patrick@: Renoncez à Bertsimas-Tsitsiklis, car il s'agit plutôt d'un "Deuxième cours" sur la programmation linéaire, et pour cela, il est probablement plus efficace avec l'Introduction à l'optimisation linéaire. BadBoy@: je dois jeter un œil à celui-ci. En général, je n'aime pas la façon dont ils présentent les choses, mais j'ai peut-être tort. Kvothe@: Les chapitres 10 ("Formules de programmation entières") et 11 ("Méthodes de programmation d'entiers") sont très bien. |
 |
Programmation linéaire | Vanderbei | |
 |
Optimisation combinatoire: polyhédra et efficacité | Schrijver | SpiderWoman@: Je me souviens avoir aimé l'optimisation combinatoire de Schrijver à l'époque, mais c'est très mathématique et je ne le recommanderais pas à quelqu'un qui a rejoint l'équipe, par exemple... |
 |
Théorie de la programmation linéaire et d'entiers | Schrijver | BadBoy@: C'est parfait pour se mettre en valeur dans votre bibliothèque, faire une interview ou impressionner quelqu'un. Vous ne le lirez probablement pas et vous ne l’aimerez pas, à moins que vous ne soyez titulaire d’un doctorat en mathématiques pures et distillées à deux reprises. Ce n'est donc pas l'élément avec lequel
commencer LP ou MIP. Cela dit, elle contient une mine d'indices et d'informations intéressantes. Des choses comme les matrices totalement unimodulaires et ce qu'elles impliquent. De plus, la librairie est extrêmement détaillée, avec des citations dans les langues d'origine. C'est une sorte d'art de la programmation informatique selon Knuth. Seul celui-ci n'est pas digeste. Kvothe@: Je ne l'ai pas lu, mais je me méfie cette personne en se basant uniquement sur sa police de caractères. |
 |
Premier cours sur l'optimisation linéaire | Lee | Disponible sans frais sous une licence CC ! |
 |
Introduction à l'optimisation mathématique | Fischetti | BadBoy@: Je suis passé par la version italienne. Ça a l'air très bien. J'adore ce que fait Fischetti en général. |
 |
Programmation linéaire | Chvatal | BadBoy@: Je n'aime pas ce livre, mais c'est là que j'ai appris tout ce qu'il y a à savoir sur les LP, et la notation est excellente. |
 |
Optimisation combinatoire | Papadimitriou et Steiglitz | BadBoy@: J'ai adoré. Elle est obsolète, mais vous devriez la lire. Kvothe@: Un peu sec à mon goût. |
 |
Programmation d'entiers | Wolsey | Unicorn@: est très succinct, mais couvre la plupart des aspects intéressants du domaine (du point de vue des solutionneurs) |
 |
Programmation d'entiers | Conforti, Cornuéjols et Zambelli | Patrick@: probablement le livre le plus récent sur la théorie et la méthodologie du MIP. |
 |
Attributs de l'optimisation combinatoire | Jünger et Reinelt | Patrick@: Plus d'informations sur le côté théorique et le biais du travail de Martin Grötschel, ancien directeur du ZIB (qui vient de ses 65 ans), mais dont je pense qu'il s'agit de la dernière version de cette enquête informatique MIP: "Tobias Achterberg et Roland Wunderling. Programmation mixte sur les entiers: analyse de 12 ans de progrès". |
 |
50 ans de programmation d'entiers: de 1958 à 2008 | Jünger et al., éd. | Patrick@: Un peu dépassé, mais un excellent résumé de l'histoire et du MIP à la pointe de la technologie. |
 |
Algorithmes de flux réseau | Williamson | Unicorn@: Un bon livre qui présente de nombreux résultats très récents sur les flux réseau, tout en restant intuitif. Mais seulement pour les flux réseau, ce n'est donc pas générique. Examen plus complet en français. |
 |
Algorithmes éclairés: algorithmes pour les problèmes NP-durs | Roughjardin | Unicorn@: Probablement pas le livre le plus avancé du marché ! Il offre néanmoins une introduction à certains algorithmes OR (du point de vue d'un cours sur les algorithmes). Très lisible ! Examen plus complet en français. |
 |
Optimisation pratique | Gill, Murray et Wright | Unicorn@: Ancien livre de référence sur l'optimisation continue. Si vous avez besoin d'explications sur cette famille d'algorithmes, consultez ce livre. (Examen plus complet en français.) |
 |
Introduction à l'optimisation et au calcul semi-différent de Hadamard | Delfour | Unicorn@: Un livre très officiel sur l'optimisation semi-différente, Difficile d'y accéder. Examen plus complet en français. |
 |
Hiérarchie des moments-SOS: cours sur les probabilités, les statistiques, la géométrie computationnelle, le contrôle et les PDE non linéaires | Henrion, Korda et Lasserre | Unicorn@: Si vous optimisez vos performances à l'aide de polynômes ou si vous vous demandez dans quelle mesure vous pouvez les exploiter, vous allez découvrir les bases de la hiérarchie SoS et des applications que vous ne connaissez pas. Examen plus complet en français. |
 |
Introduction à la recherche opérationnelle | Hillier et Lieberman | Un bon mélange de théorie et de pratique. Un bon premier texte pour les personnes qui débutent dans le domaine, avec des exemples et de nombreux exercices, dont certains avec des réponses au verso. Inconvénients: le livre s'efforce un peu trop de diriger les utilisateurs vers son site Web et il utilise des solutions obsolètes. |
Avis des utilisateurs
| Récapitulatif | Auteur | Commentaires |
|---|---|---|
| 175 ans de programmation linéaire | Chandru et Rao | BadBoy@: Cette série d'articles est incroyable. J'y ai été exposé chez IBM
au début des années 1990. Je ne sais pas qui a eu l'idée de présenter une programmation linéaire comme celle-ci, mais Vijay Chandru et Jean-Louis Lassez ont aussi été impliqués. L'avantage, c'est que vous n'avez besoin que d'une algèbre linéaire débutant pour la comprendre, et vous pouvez prouver presque tous les théorèmes importants en LP. La meilleure solution serait de créer un livre sur LP, ainsi que du Chvatal, d'autres Vanderbei, puis des problèmes d'implémentation et des références aux livres concernés. Chvatal et Vanderbei manquent d'un terrain mathématique solide. Il est ancien et devrait bientôt être renommé "200 ans de programmation linéaire". Il est possible qu'il y ait eu des tentatives précédentes. |
Articles de recherche
| Article | Auteur | Commentaires |
|---|---|---|
| Un nouvel algorithme de temps polynomial pour la programmation linéaire | Karmarár | BadBoy@: article de Karmarkar sur son algorithme. L'exemple de la façon dont un article ne doit pas être écrit. Il a fallu des années pour parvenir à une implémentation fonctionnelle, et entre-temps, ils ont découvert qu'il s'agissait d'une autre méthode ponctuelle. |
Modélisation
MIP
| Reprise | Titre | Auteur | Commentaires |
|---|---|---|---|
 |
Création de modèles en programmation mathématique | Williams | Concentrez-vous sur les LP et MIP. Temere@: Je n'ai vraiment pas apprécié cela. La structure est bizarre (elle augmente artificiellement le nombre de pages). Elle est fortement ancrée dans les "applications OR classiques" (axées sur l'économie ou la planification ressemblant à un jouet), avec peu de pertinence par rapport aux modèles MIP habituellement utilisés chez Google. Azalee@: D'accord. BadBoy@: je suis toujours convaincue que le livre était génial à l'époque. J'y ai regardé il y a peut-être deux ans, et voilà. Elle est obsolète. Je connais l'auteur depuis 1990, et nous nous sommes entretenus à l'ISMP en 2015. C'est un gars formidable, à la retraite, qui se rend à des conférences avec son budget et il fait toujours d'excellentes présentations. Ses articles étaient excellents, surtout sur l'élimination de Fourier. Il a une vision très large de ce qu'est LP et a joué un rôle déterminant dans le lancement de XpressMP. |
 |
Applications de l'optimisation avec XpressMP | Guéret, Prins, Sevaux et Heipcke |
Guides de modélisation élaborés par des résolveurs
| Guide | Description | Commentaires |
|---|---|---|
| Livre de recettes de modélisation MOSEK | L'optimisation est axée sur l'optimisation des convexes coniques. | Unicorn@ Une référence pour moi dans le domaine de la modélisation non linéaire. |
| Livre de recettes de la gamme MOSEK | Modèles coniques pour l'optimisation de portefeuille |
Études: MIP
| Récapitulatif | Auteur | Description |
|---|---|---|
| Techniques mixtes de formulation de la programmation linéaire en nombres entiers | Vielma | Se concentre sur l'intensité et la taille de formulations à nombres entiers mixtes pour les unions de fonctions linéaires de type polyhédra. Davantage sur le plan théorique, mais avec certaines techniques pratiques telles que les formulations incrémentielles dans la section 8. |
| Fonctions linéaires non convexes par morceaux: formulations avancées et outils de modélisation simples. | Huchette et Vielma | Techniques plus récentes pour les fonctions linéaires par morceaux qui ne sont pas incluses dans l'article ci-dessus. |
Avis des utilisateurs: MINLP
| Récapitulatif | Auteur | Description |
|---|---|---|
| Représentabilité convexe mixte | Lubin, Vielma et Zadik | Pour les relaxations convexes uniquement. |
Optimisation dans un environnement incertain
Optimisation stochastique
| Reprise | Titre | Auteur | Commentaires |
|---|---|---|---|
 |
Conférences sur la programmation stochastique: modélisation et théorie | Shapiro, Dentcheva et Ruszczynski | |
 |
Introduction à la programmation stochastique | Birge & Louveaux | Unicorn@: Une introduction plus théorique au sujet. Je ne le recommande pas autant que "Cours sur la programmation stochastique". |
Avis des utilisateurs
| Récapitulatif | Auteur |
|---|---|
| Optimisation de la valeur au risque conditionnelle | Rockafellar et Uryasev |
Optimisation robuste
| Reprise | Titre | Auteur | Commentaires |
|---|---|---|---|
 |
Optimisation robuste | Ben-Tal, El Ghaoui et Nemirovski | PDF. Unicorn@: Une excellente référence si les avis ci-dessous ne sont pas assez détaillés. Une grande partie est consacrée à des problèmes non linéaires (qui ne sont généralement pas présentés dans les avis). J'aime beaucoup la section 1.1.2, car elle montre numériquement que de petits écarts de coefficient peuvent rendre de grandes infaisables. |
 |
Optimisation robuste et adaptative | Bertsimas et Dick Den Hertog | PDF. Unicorn@: C'est une excellente référence sur tout ce qui concerne une optimisation efficace ! C'est assez complet, avec un peu plus d'algorithmes. Examen plus complet en français. |
Avis des utilisateurs
| Récapitulatif | Auteur |
|---|---|
| Guide pratique pour une optimisation efficace | Gorissen, Yanıkoğlu et den Hertog |
| Théorie et applications de l'optimisation robuste | Bertsimas, Brown et Caramanis |
Articles de recherche
| Article | Auteur |
|---|---|
| Analyse stochastique traçable dans des dimensions de grande taille grâce à une optimisation robuste (PDF) | Bandi et Bertsimas |
StackExchange
Quels sont les bons ouvrages de référence pour une introduction à la recherche opérationnelle ?