Portail sur la Recherche Opérationnelle

Quelques pointeurs sur la R.O.

Préambule

Ce site a pour but de proposer quelques URL concernant le thème trés large de la Recherche Opérationnelle, l'optimisation combinatoire et quelques disciplines associées. Les adresses de site (au moins) partiellement francophones sont marquées par un petit drapeau français ().

Compte tenu de l'étendue et de l'aspect multi-disciplinaire de ce domaine, l'ambition même de ce projet ne peut prétendre ni à une couverture complète de la discipline, ni à une justesse des choix effectués sur les liens proposés, ni même à la fiabilité de ces liens !

Cependant, compte tenu d'un besoin local croissant, ce site est appelé à vivre et à se développer dans les mois qui viennent. Il est donc succeptible d'évoluer fortement tant au niveau de son contenu que de son organisation, voire de son objectif même (spécialisation, contributions locales, ...).

Par conséquent, toutes suggestions ou autres remarques sont le bienvenues.

Enfin, urls indiquées étant susceptibles d'être très rapidement périmées, une information de la forme (21/11/2008) indique la date à laquelle la ressource était accessible (et non pas une date de mise à jour du site en question !).

Meta-pointeurs et moteurs

• http://forum.openopt.org (19/12/2008) OpenOpt : nouveau forum d'optimisation numérique
• news:sci.op-research Le forum de R.O
• news:comp.constraints Le forum sur la Programmation par Contrainte
• news:comp.theory
• news:comp.ai.genetic
• developpez.net/algo (21/11/2008) forum francophone chez developpez.net dont une FAQ d'algorithmique
• CitSeer : Scientific Literature Digital Library Excellent moteur biblio !
• optimization-online.org (21/11/2008) Excellente source d'articles pdf en ligne (moteur)
• sciencedirect: European Journal Of Operational Research (moteur et pdf)
• The Collection of Computer Science Bibliographies (moteur)
• www.informs.org/Resources (02/12/05) Portail RO chez Informs

La recherche opérationnelle en générale

• wikipedia.fr: Recherche opérationnelle
• wikipedia.fr: Optimisation Mathématique
• wikipedia: Combinatorial optimization (11/09/2006)
• Tutorial OR-Notes de J E Beasley (11/09/2006) : une personnalité en R.O.
• Decision Tree for Optimization Software (11/09/2006) :trés bonnes sources d'informations
• Global optimisation (11/09/2006) : trés bonnes sources d'informations également
• Operations Research Links (11/09/2006) http://www.opsresearch.com/OR-Links

Quelques organismes ou laboratoires de RO

Annuaires de laboratoires

• dmoz.org quelques organisation de R.O (11/09/2006)
• dmoz.org Centres de recherche en Mathématiques (11/09/2006)
• informs:Research_Groups (11/09/2006) Métapointeur + moteur trés complet en bas de page !

Associations et sociétés savantes

• ROADEF : Société française de RO (http://www.roadef.org) (11/09/2006)
  Le point d'entrée pour toute infos sur la R.O. en France (contacts avec le milieu de la recherche et de l'enseignement, ...)
• EURO : Association of European Operational Research Societies (11/09/2006)
• GdR pour la Recherche Opérationnelle (CNRS) (11/09/2006)

Liste alphabétique

• CAMS : Centre d'Analyse et de Mathématique Sociales (11/09/2006) UMR 8557
• CEDRIC (Equipe O.C.) au CNAM (http://cedric.cnam.fr/oc) (06/07/2007)
  Différents domaines traités, dont la programmation mathématique (linéaire ou non), graphes, tomographie, ...
• CEREMADE : Centre De Recherche en Mathématiques de la Décision (11/09/2006)
  Paris-Dauphine - UMR 7534
• DIMACS : Center for Discrete Mathematics and Theoretical Computer Science (11/09/2006)
• GERAD Groupe d'études et de recherche en analyse des décisions (http://www.gerad.ca/fr/index.php)
  Canada - interuniversitaire
• IMAG/leibniz : Institut d'Informatique et de Math. App. de Grenoble (http://www-leibniz.imag.fr/leibniz) (11/09/2006)
  Avec en particulier :
• DMD : Département de Mathématiques Discrètes
• OPTICOMB : Equipe Optimisation Combinatoire
• RO : Equipe Recherche Opérationnelle
• GRAPH : Equipe de ... (devinez !)
• LAMSADE (11/09/2006) Laboratoire d'Analyse et Modélisation de Systèmes pour l'Aide à la Décision UMR 7024 - Paris-Dauphine
• LIA/RO Laboratoire d'Informatique d'Avignon : R.O et Optimisation (14/11/2008) (Equipe de Philippe Michelon)
• LIAFA : Laboratoire d'Informatique Algorithmique : Fondements et Applications (12/09/2006) Groupe Optimisation
• LIMOS : Laboratoire d'informatique de Modélisation et d'Optimisation des Systèmes (UMR 6158) (27/01/2009)
• LMAH : Laboratoire de Mathématiques Appliquées du Havre (12/10/2006)
• MPI/AG1 : Max-Planck-Institut / Algorithms and Complexity Group (12/10/2006)
• NEOS: Server for optimisation (http://www-neos.mcs.anl.gov) (12/10/2006)
  Propose des outils R.O utilisable en ligne via des format de modélisation standard
• LAMI/OPAL : OPtimisation discrète, ALgorithmique et applications (13/09/2006)
• RealOpt : Reformulation based algorithms for Combinatorial Optimization (22/04/2008)
  INRIA Bordeau
• ROAD : Groupe de travail du LAMIH en R.O. & Aide à la Décision (13/09/2006)
• ROSE (EPFL) : Chaire de Recherche Opérationnelle Sud Est (13/09/2006)
• SysDef : Système d'aide à la décision et à la formation (11/09/2006)
• DESIRE : DÉcision, Systèmes Intelligents et Recherche opérationnelle (14/11/2008)
• ZIB : Zentrum für Informationstechnik Berlin (12/10/2006)

Quelques conférences (récentes ou à venir)

Annuaires de conférences

• ROADEF/Conférences (27/05/2008)
• INFORMS/Conferences (14/11/2008)

Liste chronologique (sélection)

• A faire

Quelques Méthodes et techniques de RO

Théorie des graphes

Liens généraux

• Graphes (http://perso.orange.fr/jean-paul.davalan/liens/liens_graph.html) (19/09/2006)
  Page ludique de Jean-Paul Davalan (voir sa rubrique jeux mathématiques).
• Laboratoire Leibniz, Equipe Graphes (http://www-leibniz.imag.fr/GRAPH/francais/themes.html) (19/11/2008)
  
• Graph Theory - Algorithms - Complexity (http://people.freenet.de/Emden-Weinert/graphs.html) (13/09/2006)
  Nombreux pointeurs sur les graphes par sous thèmes.
• Graph Theory Research (http://www.cs.columbia.edu/~sanders/graphtheory/research) (13/09/2006)
  Nombreuses références biblio les graphes par sous thèmes
• graphdrawing.org (http://www.graphdrawing.org) (10/11/2008)
  Théorie et outils concernant de dessin de graphes (dont le formatGraphMLavec références de livres sur ce sujet).
• Graph Theory by Reinhard Diestel - Third Edition (http://www.math.uni-hamburg.de/home/diestel/books/graph.theory) (13/09/2006)
  Un livre complet en ligne
• Apprendre en ligne : théorie des graphes (http://www.apprendre-en-ligne.net/graphes/) (06/12/2008)
  Présentation très pédagogique de niveau lycée par Didier Müller.

Outils autour des graphes

• LEMON: Library of Efficient Models and Optimization in Networks (https://lemon.cs.elte.hu/) (11/11/2009)
  Bibliothèque C++ de graphes simple à compiler, et couplable avec un solveur linéaire tel que Glpk. Cette biblothèque fair désormais partie du projet COIN-OR
• PIGALE : Public Implementation of a Graph Algorithm Library and Editor (http://pigale.sourceforge.net/) (10/09/2008)
  Editeur de graphes (QT) avec bibliothèque d'algorithme en C++ (orientée dessin de graphes).
• WebGraph (http://webgraph.dsi.unimi.it) (01/02/2008)
  Un framework java pour étudier les (gigantesques !) graphes Web
• iGraph (http://cneurocvs.rmki.kfki.hu/igraph) (22/03/2008)
  Une librairie de graph en C avec interface pour les langagse R et Ruby
• jGrapht (http://www.jgrapht.org) (14/04/2010)
  Une librairie de graphe en an Java (jGraft) avec interface graphique (jGraph)
• RGL (http://rgl.rubyforge.org/rgl) (29/05/2008)
  Ruby Graph Librairy : inspiré du design de la BGL (Boost Graph Library)
• Mascopt: Mascotte Optimization (http://www-sop.inria.fr/mascotte/mascopt) (24/12/2007)
  Bibliothèque de graphes en java.
• Pigale : Public Implementation of a Graph Algorithm Library and Editor (http://pigale.sourceforge.net) (06/07/2007)
  Editeur de graphe, et bibliothèque (C++ et QT4) plutot orientée pour le dessin de graphes

Algorithmique en générale

• The Stony Brook Algorithm Repository (http://www.cs.sunysb.edu/~algorith) (19/11/2008)
  Nombreux algorithmes référencés et/ou décrits (c'est une bonne pub pour son bouquin !).
• Skiena's Algorithms Lectures (http://www.cs.sunysb.edu/~algorith/video-lectures) (19/11/2008)
  Les cours (video/audio et slides) de Steven Skiena
• Voir aussi dans cette page : LIAFA

Relaxation Lagrangienne

• Optimisation convexe et décomposition de Dantzig-Wolfe (http://www.math.u-bordeaux.fr/MAB/ODW) (13/09/2006)
  Equipe à Lemaréchal/Vanderbeck/Vial ; dont un cours post-DEA en ligne de Claude Lemaréchal
• Etat de l'art par Monique Guignard (81 pages - dec 2003) (http://opim.wharton.upenn.edu/~guignard/papers/top11201.pdf) (19/11/2008)
  Version locale ENSTA : Monique.Guignard-top11201.pdf
• RR-5453 - Comparison of Bundle and Classical Column Generation (http://www.inria.fr/rrrt/rr-5453.html) (13/09/2006)
  Rapport INRIA par Briant, O. - Lemaréchal, C. - Meurdesoif, Ph. - Michel, S. - Perrot, N. - Vanderbeck, F

Programmation Par Contraintes (PPC ou CP)

Métapointeurs

• Wikipedia: Programmation par contraintes (20/11/2008)
• Wikipedia: Constraint logic programming (20/11/2008)

Recherche

• AFPC (http://www.afpc-asso.org) (19/11/2008)
  Association francaise pour la programmation par contraintes
• Constraints Archive (bof !) (http://4c.ucc.ie/web/archive) (19/11/2008)
  
  • Les archives de Cork Constraint Computer Center (4c) (pas encore bien fournies)
  • Les anciennes archives (toujours actives)
• CSPlib: a problem library for constraints (http://www.csplib.org) (19/11/2008)
  Très bonne sources d'informations (solvers, benchmarks, ...)
• La page de Roman Bartak (http://kti.mff.cuni.cz/~bartak) (19/11/2008)
  Dont le site constraints avec un excellent cours en ligne
• Constraint Programming and Optimization Laboratory (http://cswww.essex.ac.uk/CSP) (13/09/2006)
  (Univ. of Essex)
• Projet CONTRAINTES à l'INRIA (http://www.inria.fr/recherche/equipes/contraintes.fr.html) (20/11/2008)
  (Equipe à François Fages)

Outils

• Choco Solver (http://www.emn.fr/z-info/choco-solver) (18/12/2009)
  Un solver gratuit pour programmation par contrainte 100% java. Le version majeur 2.0 est sortie le 10 septembre 2008 (avec nouvelles APIs, mais nécessite jdk-1.6)
  • Choco documentation (pdf) : TTB ! Avec le détails des contraintes globales, utilisation avancée, ......
  • Download
  • Source svn sourceforge
  • Forums Sourceforge
  • Sudoku and constraint programming et une Super applet créée avec choco
  • Une page perso de hakanks hemsida (avec de bons exemples)
• GeCode : generic constraint development environment (http://www.gecode.org/) (20/11/2008)
  Très bonne bibliothèque de programmation par contrainte en C++.
  • Gecode/J une interface pour Java
  • Gecode/R une interface pour Ruby pour ceux qui veulent faire du script vraiment objet (sur le site Rubyforge)
• Koalog Constraint Solver (http://www.koalog.com/php/jcs.php) (20/11/2008, indispo au 18/12/2009)
  Solver commercial 100% java, créée par une petite société française.
• Minion (http://minion.sourceforge.net/) (20/11/2008)
  Une librairie C pour la PPC, limitée en nombre de contraintes intégrées, mais qui se veut plus rapide que les solveurs commerciaux !
  (même la couleur du site est agressive, c'est dire !)
• SAT4J : A satisfiability library for Java (http://www.sat4j.org/) (20/11/2008)
  Principe :
  SAT est le prototype des problèmes NP-complets. Tout problème NP-complet peut se réduire à SAT. Donc il suffit de mettre le "paquet" sur les solveurs SAT pour résoudre tout problème NP-complet !
  TODO : créer une rubrique SAT dans la liste des problèmes de cette page ?

Programmation logique

Outils

• Wikipedia : Programmation Logique
• Wikipedia: logic programming (20/11/2008)

Polyédrique

Liens généraux et outils

• PPL : Parma Polyhedra Library (http://www.cs.unipr.it/ppl) (21/11/2008)
  Bibliothèque C++ qui semble bien écrite, maintenue et documentée
• Polylib - A library of polyhedral functions (http://icps.u-strasbg.fr/PolyLib) (21/11/2008)
  Bibliothèque de manipulation de polyhèdres, facile à compiler, sans des miriade de dépendance : à creuser...
• PORTA : POlyhedron Representation Transformation Algorithm (http://www.zib.de/Optimization/Software/Porta) (21/11/2008)
  Exécutable (plus maintenu ?) permettant d'afficher toutes les facette d'un polyhèdre
  TODO : essayer de trouver/écrire un éxécutable simulaire basé sur les bibliothèques PPL ou Polylib)
• Polymake (http://www.math.tu-berlin.de/polymake) (21/11/2008)
  Bibliothèque de manipulation et d'affichage polyhédrale (+/- usine à gaz, mais à tester)
  Polymake started out as a tool for the algorithmic treatment of convex polyhedra. By now it also deals with finite simplicial complexes, tight spans of finite metric spaces, polyhedral surfaces, and other objects.

Programmation linéaire

Liens généraux

• Wikipedia : Programmation Linéaire (21/11/2008)
• Wikipedia : Linear Programming (21/11/2008)
• Wikipedia : Simplex Algorithm (21/11/2008)
• FAQ de Programmation Linéaire (http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html) (13/09/2006)
  Très complète, mais plutôt ancienne !

Outils

• Voir quelques outils open source de programmation linéaire dans cette page et en particulier
  COIN, Lp_solve, GLPK, QSopt-Exact (calcul rationnel exact)
• Description dy format MPS (13/09/2006)

Points intérieurs

Liens généraux

• Interieur Point Method Online (http://www-unix.mcs.anl.gov/otc/InteriorPoint) (21/11/2008)
  Northwestern University of Chicago

Outils

• Page de Jacek Gondzio (http://www.maths.ed.ac.uk/~gondzio) (21/11/2008)
  Travaille sur des problèmes non linéaires de grande taille, et en particulier sur :
• HOPDM: Higher Order Primal-Dual Method (http://www.maths.ed.ac.uk/~gondzio/software/hopdm.html) (21/11/2008)
  Exécutable et librairie pour résoudre des Pogrammes linéaires ou convexe de grande taille (librairie fortran et C)
• LIPSOL (Linear-programming Interior Point SOLvers) (http://www.caam.rice.edu/~zhang/lipsol) (21/11/2008)
  Extension à Matlab par Yin Zhang http://www.caam.rice.edu/~zhang/. Il en existe une extension pour Scilab (de 2006)

---

Les liens postérieurs à cette ligne sont en cours de révision

---

Programmation semi-définie

Liens généraux SDP

• Semidefinite Programming (http://www-user.tu-chemnitz.de/~helmberg/semidef.html) (14/09/2006)
  Avec nombreux pointeurs sur le sujet par Christoph Helmberg

Outils SDP

• SDP Software (14/09/2006) Une liste de logiciels dédiés au problèmes SDP

• SDPLIB (http://infohost.nmt.edu/~sdplib/) (14/09/2006)
  Une collection d'instances de problèmes SDP au format SDPA (creux).

• SDP_S (http://semidef.free.fr/SDPS/SDP_S.html) (16/12/2008)
  Un Outil pour formuler et résoudre des relaxations Semidéfinies pour les problèmes Quadratiques à Variables Bivalentes.

• CSDP, A C Library for Semidefinite Programming (https://projects.coin-or.org/Csdp/) (14/09/2006)
  Ce logiciel est en cours d'intégration à l'environnement COIN.
  L'ancienne page reste accessible en http://www.nmt.edu/~borchers/csdp.html
• DSDP : Software for Semidefinite Programming (http://www-unix.mcs.anl.gov/DSDP/) (14/09/2006)
  Voici une page de tests
• PENON : PENalty method for NONlinear and sdp (http://www2.am.uni-erlangen.de/~kocvara/pennon/) (14/09/2006)
  (autre logiciel SDP commercial non testé)

Programmation stochastique

• Stochastic Programming Community Home Page (http://www.stoprog.org/) (16/01/2007)
• COIN-OR Stochastic Modeling Interface (https://projects.coin-or.org/Smi) (16/01/2007)

Algorithmes génétiques

Liens généraux

• Optimisation et algorithmes génétiques (http://magnin.plil.net/spip.php?rubrique8) (14/09/2006)
  Très bon cours de Vincent Magnin (Polytch'Lille et IEMN)
• Intelligence artificielle : portail collaboratif (14/09/2006) (http://www.a525g.com/intelligence-artificielle/algorithme-genetique.php)
• Genetic Algorithms (http://www.geneticprogramming.com/ga/) (14/09/2006) (23/03/2007 : plus accessible ??)
  Un portail sur les algorithmes génétiques.
• Genetic Programming (http://www.genetic-programming.com/) (14/09/2006)
  Ambition : créer un programme automatiquement pour résoudre un problème. Tout un domaine...

Outils pour le génétique

• GAlib (http://lancet.mit.edu/ga/) (14/09/2006)
  A C++ Library of Genetic Algorithm Components
• GAA (http://www.aridolan.com/ofiles/ga/gaa/gaa.aspx) (14/09/2006)
  Un environnement Java pour les algo génétiques

Personnes

• Page de Laetita Jourdan (INRIA) (14/09/2006)

Colonies de fourmis

• Ant Colony Optimization Home Page (http://iridia.ulb.ac.be/~mdorigo/ACO) (14/09/2006)
  Très bon site.
• Page de Marco Dorigo (http://iridia.ulb.ac.be/~mdorigo/) (14/09/2006) Auteur des colonies de fourmis

Essaim de particule (PSO=Swarm Particle Optimization)

• wikipedia PSO (en)    OEP (fr)
• Particle Swarm Central (http://www.particleswarm.info/) (24/04/2007)
  Le site de référence.
• XPS - eXtended Particle Swarms Project (http://xps-swarm.essex.ac.uk) (25/04/2007)
• Page de Maurice Clerk (http://clerc.maurice.free.fr/pso/) (24/04/2007)

Théorie des jeux

• A COMMENCER ... (14/09/2006)

Quelques classes de problèmes

Voyageur de commerce (TSP)

• Traveling Salesman Problems (http://www.tsp.gatech.edu/) (14/09/2006)
  La page de référence par les maitres du domaine.
  Voyez en particulier concorde le solveur open source de référence (record du monde) pour la résolution exacte du voyageur de commerce et ses variantes.
• LKH : effective implementation of the Lin-Kernighan heuristic for solving the TSP (http://www.akira.ruc.dk/~keld/research/LKH) (25/11/2009)
  Implémente la meilleure heuristique connue pour le TSP. Compile facilement mais pas pratique d'utilisation car pas de lecture d'options : il faut écrire un fichier de paramètre.
  Ceci dit le résultat est impressionnant !
• TSPLIB (http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/) (14/09/2006)
  La librairie de référence pour le problème TSP et ses variante.
• 8th DIMACS Implementation Challenge : The Traveling Salesman Problem (http://www.research.att.com/~dsj/chtsp/) (14/09/2006)
• Traveler (de Kent Paul Dolan) (http://www.well.com/user/xanthian/java/TravellerDoc.html/) (14/09/2006)
  Avec programme java dont une solution à base d'algo génétiques
• Exact Java Traveling Salesman Problem (TSP) (http://home.planet.nl/~onno.waalewijn/tspx.html) (14/09/2006)
  Applet java efficace (solution exacte pour 150 villes en 9 à 30 secondes sur mon powerbook) Fast JAVA Traveling Salesman Problem (TSP) (http://home.planet.nl/~onno.waalewijn/tspfast.html)

Plus court chemin et chemin optimal (SP)

• 9th DIMACS Implementation Challenge : The Shortest Paths Problem (http://www.dis.uniroma1.it/~challenge9//) (14/09/2006)
• Page de Andrew V. Goldberg (http://www.avglab.com/andrew/) (14/09/2006)
  En particulier :
  • andrew/soft.html contient différentes implémentations d'algo de plus court chemin (entre autre)
  • andrew/#slides propose une série de transparents sur les différents algo, en particulier sur l'algorithme A*
• Page de Ernesto Martin (http://www.mat.uc.pt/~eqvm/OPP/shortestpath.html) (14/09/2006)
  Quelques pointeurs sur ce problème
• K-th Shortest Path Problem (http://www.mat.uc.pt/~eqvm/OPP/KSPP/KSPP.html) (14/09/2006)
  Une bonne formulation du problème et de ses variantes

Problèmes de flow

• CATS Maximum Flow Page (http://www.avglab.com/andrew/CATS/maxflow.htm) (14/09/2006)
  Test et algorithmes sur les problèmes de flots
• Minimum Cost Flow Problem Instances Generated by NETGEN (http://ftp.zib.de/pub/mp-testdata/mincost/netg) (16/02/2010)
  Générateurs et instances de problèmes de flot à coût min.

Problèmes de Tournées

• Challenge Traveling Tournament Instances (http://mat.gsia.cmu.edu/TOURN) (14/09/2006)
  Problème de tournées d'équipes sportives

Affectation de Fréquences (FAP)

• Challenge ROADEF'2001 (http://uma.ensta.fr/conf/roadef-2001-challenge)
  Problème d'Affectation de Fréquence avec Polarisation
• Frequency Assignment Problems (http://www.fap.ema.fr/) (14/09/2006)
• FAP web - A website about Frequency Assignment Problems (http://fap.zib.de/) (14/09/2006)

Problèmes d'affectation généralisées (GAP)

• http://www.al.cm.is.nagoya-u.ac.jp/~yagiura/gap/ (http://www.al.cm.is.nagoya-u.ac.jp/~yagiura/gap) (14/09/2006)

Problèmes d'affectation quadratiques (QAP)

• QAPLIB - A Quadratic Assignment Problem Library (http://www.opt.math.tu-graz.ac.at/qaplib) (14/09/2006)
  La librairie de référence pour les instances de ce type de problèmes

Problèmes de coloration

• Graph Coloring Page by Joseph Culberson (http://web.cs.ualberta.ca/~joe/Coloring/index.html) (14/09/2006)
  Un bon point de départ sur ce sujet.
• COLOR02/03/04: Graph Coloring and its Generalizations (http://mat.gsia.cmu.edu/COLORING02) (14/09/2006)
  Avec des instances de problèmes de coloration.
• Graph Coloring Problems (19/09/2006) Voir en particulier les nombreux sous-problèmes

Problèmes de gestion de générateurs (UCP = Unit Commitment Problem)

• Unit Commitment's Archive (http://gear.kku.ac.th/~thana/unitcom.html)
  (14/09/2006) lien mort : pas de remplacent trouvé
  (C'était) le seul lien générique que j'ai trouvé sur UCP.
• GSEE Electric Energy Systems Group (publications) (http://www.uclm.es/area/gsee/Web/publications.htm) (14/09/2006)
  (pas mal de publications en ligne)
• Unit commitment for combined heat and power production - Using simulated annealing (14/09/2006) Master thesis 2003 by Thorhallur Ingi Halldorsson
• Relaxation Lagrangienne et filtrage par coûts réduits appliqués à la production d'électricité (http://uma.ensta.fr/labo/publication.php?id=3) (14/09/2006)
  Couplage d'une relaxation lagrangienne avec la programmation par contraintes... J'aime bien ce rapport de janv. 2005 (;-)
  Transparents antérieurs au rapport : roadef2003_ucp

Ordonnancement

• GOThA (Groupe de recherche en Ordonnancement Théorique et Appliqué)
  (http://www-poleia.lip6.fr/~sourd/gotha/gt.html) (14/09/2006)
• Gestion de projet à contraintes de ressources
  Site du sous-groupe du GOThA dédié au problème RCPSP (14/09/2006)
• Jobshop Quelques pointeurs chez Francis Sourd (14/09/2006)
• The PSPLIB : Project Scheduling Problem LIBrary (http://www.bwl.uni-kiel.de/Prod/psplib) (14/09/2006)
  Une description des problèmes de type RCPSP (Resource-Constrainded Project Scheduling Problem) et dérivés, avec quelques instances de référence à télécharger
• Project Generator ProGen/max and PSP/max-library (14/09/2006)
  Un ensemble de benchs (avec le générateur) pour les problèmes type RCPSP
  (dont RCPSP/max MRCPSP/max, RIP/max et PLP/max)
• Quelques Scheduling instances (14/09/2006) sur la page de Eric Taillard (Flow shop, Job shop, Open shop)

Divers

Règle de Golomb

• wikipedia : Règle_de_Golomb (14/09/2006)
• Golomb rulers (IBM) (14/09/2006)
• projet OGR : Optimal Golomb Rule (14/09/2006)

Complexité

• A compendium of NP optimization problems (http://www.csc.kth.se/~viggo/problemlist) (18/09/2006)
  EXCELLENT recueil de problèmes NP-complets - Copie local ENSTA 28/08/05
• The Complexity Zoo (http://qwiki.caltech.edu/wiki/Complexity_Zoo) (18/09/2006)
  Définition de 460 classes de complexité !! Voir aussi le Glossaire
• Complexité des problèmes d'ordonnancement (http://www.mathematik.uni-osnabrueck.de/research/OR/class/) (18/09/2006)
  très détaillé pour ces problème.
• http://public.research.att.com/~dsj/columns/ (18/09/2006)

Langages spécialisés pour la RO

Langage AMPL

AMPL est un langage de modélisation de haut niveau développé au Bell Laboratories. Il permet de modéliser des problèmes linéaires ou non linéaires, continus ou discrets, et de sous traiter le travail de résolution à divers solveurs spécialisés.

• Langage AMPL (18/09/2006) la page de référence.
• AMPL FAQ (18/09/2006)

Question (09/11/2006) quelle est la différence avec le Langage GAMS (General Algebraic Modeling System) ? Synonyme ? Concurrent ??

Langage GMPL (MathProg)

C'est la version GNU d'un sous ensemble de AMPL. Il est intégré au projet GLPK

Langage Claire

Prototype de langage spécialisé en optimisation combinatoire.

• eXpert soLution (http://www.claire-language.com) : (18/09/2006)
  La société (à Bordeaux) créé pour assurer un support commercial de Claire

Langage PROLOG

Langage très apprécié par ceux qui l'aiment...

• GNU Prolog (par l'INRIA) (http://gprolog.inria.fr/) (18/09/2006)
  distrib FTP (ftp://ftp.inria.fr/INRIA/contraintes/gprolog) (18/09/2006 mais pas pressé !)
• http://vl.fmnet.info/logic-prog/#Prolog (13/09/2006)

Langage Mosel

Egalement appelé Xpress-Mosel (13/09/2006), Mosel est un autre langage de modélisation de haut niveau pour les problèmes d'optimisation.
Voici une présentation de 20 pages : mosel.pdf

Quelques outils de R.O.

Annuaires ou serveurs d'outils

• Optimization Software (13/09/2006) (http://www-fp.mcs.anl.gov/otc/Guide/SoftwareGuide)
  Une liste de (nombreux, mais plus à jour) logiciels dédiés à l'optimisation.
• COIN-OR related resources (13/09/2006)
  Une liste d'outils open-source logiciels pour la Recherche Opérationnelle.
• NEOS: Server for optimisation (12/09/2006) (http://www-neos.mcs.anl.gov)
  Propose des serveurs de logiciel R.O utilisables en ligne via des formats de modélisation standard (AMPL, ...)

Outils par ordre alphabétique

• ABACUS - A Branch-And-CUt System (http://www.informatik.uni-koeln.de/abacus/) (13/09/2006)
  Une librairie C++ pour utiliser faire du "Branch and Xxxx" avec des solvers existants (au formay OSI)
• COIN-OR (http://www.coin-or.org/) (14/09/2006) download/binary (16/01/2007)
  COmputational INfrastructure for Operations Research Projet Open source, ambitieux, d'origine IBM (C++)
• Glop - Generic Linear Optimization Package   (18/03/2008)
  Glop propose une abstraction en C et C++ des API des principaux solveurs linéaires (glpk, lp_solve, clp de coin-or, cplex et xpress).
• GLPK (GNU Linear Programming Kit)   (distrib) (14/09/2006)
  La bibliothèque Glpk est livrée avec un solveur autonome (glpsol), capable de traiter des problèmes linéaires (continus ou en nombre entier) par des méthodes de simplexe ou de Points Intérieur.
  Ces problèmes peuvent être modélisés dans différents langages, dont l'excellent GMPL (clone de AMPL).
  Voir aussi la Mailing list dédiée à GLPK  Version mail-archive
  Voir aussi le wiki book en construction
• Graphviz (http://www.graphviz.org/) (16/04/2008)
  Logiciel permettant d'afficher automatiquement un graphe à partir de formats de description textuels simples.
  • dotguide.pdf : Manuel (pdf) du format ".dot"
  • webdot Le programme CGI écrit en TCL utilisé pour créer les exemples suivant.
  • demo.html Nombreux exemples avec pour chacun différents le fichier dot d'entrée, et diffrent format de sortie pour plusieurs algorithme de routage.
  • Grappa : un port en java d'une partie de Graphviz (vieux)
  • jGraphViz : une interface de Graphviz pour Java (30/01/2009)
  • Ajax/Graphviz : page web permettant de construire à la volée l'image gif d'un graphe à partir d'un text au format dot (EXCELLENT)
  • Automatiser la création de graphiques avec Graphviz : excellent totorial français illustrant la création de graphe manuellement avec Graphviz. Version locale ENSTA
• GSL (http://www.gnu.org/software/gsl/) (13/09/2006)
  La Gnu Scientific Library est une librairie scientifique d'usage général écrite en C
• JUNG : Java Universal Network/Graph (http://jung.sourceforge.net) (24/10/2009)
  Jung est un framework JAVA sous licence BSD permettant de manipuler, analyser et visionner des graphes. JUNG est basé sur (et inclue) les bibliothèques java Jakarta/collection du projet Apache, et COLT du Cern.
• LP_Solve (http://groups.yahoo.com/group/lp_solve/) (13/09/2006)
  Nécessite un enregistrement (gratuit)
  • Doc de Lp_solve
  • distribution de Lp_solve
• Operations Research - Java object (http://OpsResearch.com/OR-Objects) (11/09/2006)
  Librairie JAVA pour (petits) problèmes de R.O. Utilisation gratuite, mais sources non accessibles. Ne semble plus maintenue, mais reste intéressante pour les API.
• Paradiseo (http://paradiseo.gforge.inria.fr) (14/03/2008)
  Un Framework multiplatforme orienté objet pour la conception flexible de méthaheuristiques (de voisinage, de population, ...)
• QSopt-Exact Home Page (http://www.dii.uchile.cl/~daespino/) (13/11/2007)
  Solveur linéaire avec calculs exacts (car rationnels), basé sur la librairie GMP (Gnu Multi Precision)
  Une description comptète de ce solveur fait l'objet de la Thèse de Daniel Espinoza
• SCILAB (http://www.scilab.org/) (11/09/2006) L'environnement de calcul scientifique open-source de référence.
• SCIP (httphttp://scip.zib.de) (20/05/2010) Solving Constraint Integer Programs : un des frameworks non commeriaux les plus efficace pour la PLNE (Branch Cut and Price...)
• SYMPHONY (http://www.coin-or.org/SYMPHONY/) (13/11/2009) Framework et outil autonome pour faire du Branch and X.
  Bien que Symphony soit une partie intégrante du projet COIN-OR, il mérite une place à part de par son aspect outil autonome. Il semble faire tout ce que fait GLPK : à creuser.
• ScheViz (http://www.lix.polytechnique.fr/~savourey/scheviz.html) (16/02/2009)
  Un outil java de visualisation dédié à l'ordonnancement (tout récent : à surveiller !).

Quelques sociétés commerciales

• ARTELYS (http://www.artelys.com/) (18/09/2006)
  Société spécialisée en optimisation - formation (anciens élèves Ensta :-)
  Par ailleurs, Artelys propose désormais Artelys Kalis un environnement (librairie C++ ou java) de Programmation par Contraintes exploitable avec le langage de modélisation Xpress-Mosel.
• Dash optimization (http://www.dash.co.uk/) (18/09/2006)
  Propose l'outil Xpress-MP
  
• Dynadec (http://www.dynadec.com) (01/02/2009)
  Dynatec propose COMET, un framework multiplatforme associant la programmation par contraintes, la programmation mathématique et la recherche locale contrainte (une version d'évaluation et universitaire est disponible).
• EURODECISION (http://www.eurodecision.com) (18/09/2006)
  réalise des applications d'aide à la décision par intégration de technologies d'optimisation et de simulation. Les principaux domaines d'application sont : la logistique, les ressources humaines, la production, le transport, les achats, les télécommunications.
• GUROBI (http://gurobi.com/) (01/12/2009)
  Société récente (2008) créée suite au rachat de ILOG par IBM qui propose (au printemps 2009...) des outils d'optimisation linéaires et en nombre entier (y compris pour MacOSX Snow Leopard 64 bit). Version gratuite pour l'éducation/recherche.
• IBM/ILOG (http://www-01.ibm.com/software/fr/websphere/optimisation) (25/03/2010)
  Propose des outils de référence (tant au niveau de la qualité que du prix !) dans le domaine de l'optimisation comme ILOG/Cplex pour la programmation linéaire et quadratique et ILOG/CP Optimizer pour la Programmation par contraintes.
• INRO (http://www.inro.ca/fr/produits/) (18/09/2006)
  L'INRO est spécialisée dans les logiciels de planification des transports : EMME/2 et Dynameq.
  
• Koalog (http://www.koalog.com/php/jcs.php) (18/09/2006 .. 25/03/2010)
  Site web inaccessible le 25/03/2010 (n'existe plus ??)
  Cette société française propose entre autre un Solveur par contraintes écrit 100% en java, avec formation...
  Une application permettant le choix d'une configuration d' options d'automobile .

Benchmarks et données tests

• NEOS server for Optimization! (http://www-neos.mcs.anl.gov/neos/server-solvers-in.html) (18/09/2006)
  Serveur de solveurs en lignes gratuit.
  Conçu pour permettre la comparaison de différents solveurs (de problème d'optimisation), ce serveur (web) permet de tester différents outils existants sur vosfr / propres instances de problème avec un certain choix dans les formats acceptés.
• OR-Library (http://people.brunel.ac.uk/~mastjjb/jeb/info.html) (18/09/2006)
  TTB : Une collection de tests maintenue par John E Beasley pour toute sorte de problemes de RO !
• CATS: Combinatorial Algorithms Test Sets (http://www.jea.acm.org/CATS/) (18/09/2006 : semble abondonné...ou en instance de renaissance ?)
• MP-TESTDATA (http://elib.zib.de/pub/Packages/mp-testdata/)
  Une collection de tests pour math et RO
• princeton testProblems (15/06/2007) (http://titan.princeton.edu/TestProblems)
  Plusieurs catégories d'instances de problèmes d'optimisation au format GAMS
• Benchmarks for Optimization Software (11/09/2006) (http://plato.asu.edu/bench.html) de Hans Mittelmann
  Des instances et benchmarks pour les différentes branches de la R.O.

Revues et journaux électroniques

• Open Journal Systems from Public Knowledge Project (18/09/2006)
  Une liste de journaux gratuits en ligne.

• 4OR: A Quarterly Journal of Operations Research (18/09/2006) Springer Berlin / Heidelberg
• Applied Mathematics and Optimization (18/09/2006) Springer New York
• JMMA: Journal of Mathematical Modelling and Algorithms (18/09/2006) Springer Netherlands (Computer Science and Mathematics and Statistics)
  
• Discrete Mathematics and Theoretical Computer Science (18/09/2006) (http://www.dmtcs.org)
  Open Journal Systems : journal gratuit hébergé par le LORIA (INRIA/Lorraine)
• Discrete Optimization (18/09/2006)
  The Journal of Combinatorial Operations Research
• Fuzzy Optimization and Decision Making (13/09/2006) Springer Netherlands
• Journal of Combinatorial Optimization (18/09/2006) Springer Netherlands
• Constraint (13/09/2006) Springer Netherlands
• Journal of Global Optimization (18/09/2006) Springer Netherlands
• Optimization and Engineering (18/09/2006) Springer Netherlands
• RAIRO - Operations Research (18/09/2006)
  An international journal on operations research
• SIAM Journal on Optimization (SIOPT) (18/09/2006)
  

./

retour ENSTA / ~diam / ro /      modif : 19/12/2008      URL originale : http://www.ensta.fr/~diam/ro Auteur : Maurice Diamantini      URL originale : http://www.ensta.fr/~diam/ro    modif : 19/12/2008