Notes de version de OR-Tools

Cette page répertorie les modifications apportées aux outils OU, y compris les nouvelles fonctionnalités, les corrections de bugs et les améliorations du code et des procédures d'installation.

Si vous rencontrez des problèmes lors de l'installation des outils OU, consultez la section Dépannage dans les instructions d'installation des outils OU. Si votre problème ne figure pas dans la liste, consultez la liste des problèmes sur GitHub ou n'hésitez pas à en ouvrir un nouveau. Nous serons ravis de vous aider.

Vous trouverez ci-dessous les notes de version pour OR-Tools, en commençant par la dernière version.

Mai 2024

Sortie d'OR-Tools v9.10

Nous avons lancé la version 9.10 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Les notes de version sont disponibles sur GitHub.

Mars 2024

Sortie d'OR-Tools v9.9

Nous avons lancé la version 9.9 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Les notes de version sont disponibles sur GitHub.

Novembre 2023

Sortie d'OR-Tools v9.8

Nous avons lancé la version 9.8 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Modifications des plates-formes

  • Ajoutez Python 3.12.
  • Ajouter la prise en charge d'Ubuntu 23.10

Solveur linéaire

  • Portez ModelBuilder vers .Net.
  • LogCallback a été renommé MbLogCallback pour éviter toute collision avec SAT LogCallback.
  • Extension de l'API ModelBuilder :
    • Ajoutez des contraintes d'indicateur.
    • Prise en charge des indications.
    • Ajouter le clonage de modèle.

Optique mathématique

  • Retouches approfondies.

Routage

  • Ajoutez l'état ROUTING_OPTIMAL.
  • Faites en sorte que RoutingModel ne puisse pas être copié ni déplaçable.
  • Correction de la boucle infinie dans les opérateurs de recherche locaux.
  • Ajoutez une structure interne PickupDeliveryPosition.
  • Ajout des méthodes IsPickup() et IsDelivery().

SAM

  • Réduisez l'encombrement de la mémoire pour les grands modèles.
  • Amélioration de la recherche de planning.
  • ajoutez packing_precedences_lns.
  • optimiser et corriger le saut de faisabilité.
  • optimiser la résolution linéaire et améliorer la journalisation des présols.
  • Amélioration de presolve pour int_abs, int_mod, int_prod et lin_max.
  • Améliorer la prise en charge de Panda
  • Quelques corrections de bugs.

Journal des modifications GitHub

août 2023

Sortie d'OR-Tools v9.7

Nous avons lancé la version 9.7 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Modifications des plates-formes

  • Suppression de Centos-8 (Fin de vie).
  • Suppression de Debian 10.
  • Déposez Fedora [33, 36] (EOL).
  • Suppression d'Ubuntu 18.04 LTS (EOL).
  • Suppression de Python 3.7 (EOL).
  • Désactivation de la prise en charge de netcore3.1 dans CMake (EOL).

Outil de création de modèles Python

  • Autorise l'utilisation de DataFrames et de séries Pandas pour créer des variables.
  • Compléter les informations de saisie

Protection contre la perte de données

  • diverses mises à jour.

CP-SAT

  • Amélioration des performances (feasibility_jump, lin_max)
  • Améliorer la gestion des plans
  • Nouveau nœud de calcul "object_sadding_search" dédié à l'amélioration de la limite inférieure de l'objectif (en cas de réduction)
  • Saisir des annotations pour le fichier Python cp_model.py
  • Compatibilité partielle expérimentale avec pandas dans cp_model.py
  • Nœuds de calcul expérimentaux basés sur une violation de la recherche à proximité :
    • activé avec les paramètres suivants: num_violation_ls:xxx
    • optimisé pour le modèle linéaire (linear, bool_or, bool_and, at_most_one, exactly_one)
    • fonctionne correctement avec lin_max, product, division
    • prend en charge les valeurs "no_overlap", "cumulative", "circuit" et "routes"
    • désactivé avec no_overlap_2d
    • Nombre recommandé de nœuds de calcul ls: num_workers -> num_violation_ls : (8, 1), (16, 2) (24, 3), (32, 4)

Journal des modifications GitHub

March 2023

Sortie d'OR-Tools v9.6

Lancement de la version 9.6 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Modifications des plates-formes

  • Ajout de la prise en charge de Fedora 37 et 38.
  • Suppression de Python 3.6 (non compatible avec protobuf).
  • Suppression de Python 3.7 sous macOS (non compatible avec scipy).
  • Prise en charge de net7.0 dans CMake (utilisez -DUSE_DOTNET_7=ON).
  • Déposer netcore3.1 dans les packages nuget .org

Dépendances

  • SCIP v801 -> v803 (remarque: SCIP utilise désormais une licence compatible OSI)
  • abseil 20220623.1 -> 20230105.0
  • Protobuf v21.5 -> v21.12
  • SWIG 4.1.1
  • JNA Java 5.11.0 -> 5.12.1

Bazel

  • Prise en charge de pybind11.
  • Prise en charge du wrapper Java.

Solveurs

  • PDLP: wrapper Python dd.
  • CP-SAT: amélioration des performances
  • GLOP: Tweak presolve.
  • ModelBuilder – Python : amélioration de la prise en charge de Numpy.
  • Routage: amélioration des performances (recherche à proximité)

Problèmes connus :

  • CP-SAT: si le subsolver pseudo_costs est ignoré, il renvoie les paramètres non valides (voir la section #3706).

Novembre 2022

Sortie d'OR-Tools v9.5

Nous avons lancé la version 9.5 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Modifications des plates-formes

  • Prise en charge de Debian Sid.
  • Ajout de la prise en charge de Fedora 35 et 36.
  • Ajout de la compatibilité avec Ubuntu 22.10.
  • Suppression de Python 3.6 sous macOS.
  • Ajout de la compatibilité avec Python 3.11.

Mise à jour des dépendances

  • Protobuf v19.4 -> v21.5.
  • Solveur SCIP v800 -> v801.

CP-SAT

  • Améliorations apportées à la résolution: max(array), contraintes booléennes et contraintes linéaires.
  • La recherche entrelacée doit être déterministe en parallèle.
  • Coupes linéaires: nettoyage des coupes carrées et int_prod ; réécriture du pipeline "cut"
  • Modèle et solution d'entrée de l'empreinte numérique (visibles dans le journal)
  • Améliorations de la programmation.
  • Les corrections de bugs habituelles (plantages lors de la résolution, plantage en cas de coupure, solutions impossibles à mettre en œuvre, modèles impossibles à exécuter dans LNS)

GLOP

  • Accélérer le rythme en réécrivant l'algèbre linéaire ainsi que la règle de sélection du tableau croisé dynamique.

Solveur linéaire

  • Ajout de knapsack_interface.cc.
  • Déplacement de l'API model_builder dans le répertoire linear_solver (en-têtes et exemples).
  • Ajout de la prise en charge de Gurobi 10.

Routage

  • Libérez quelques analyseurs pour différents défis de routage.

Août 2022

Sortie d'OR-Tools v9.4

Nous avons lancé la version 9.4 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Plates-formes

  • Ajout de la compatibilité avec Debian-10 (voir #3029).
  • Ajout de la compatibilité avec Ubuntu 22.04 LTS (voir #3276). Remarque: l'application ne sera pas compatible avec .Net 3.1 (voir dotnet/core#7038).
  • Suppression de la compatibilité avec Ubuntu 21.10.

Divers :

  • Fractionnement de l'archive par langage et ajout de la configuration CMake à celle de C++ (problème n° 3200).

Graphique

Diviser ortools.graph.pywrapgraph comme suit:

  • ortools.graph.python.linear_sum_assignment.
  • ortools.graph.python.max_flow.
  • ortools.graph.python.min_cost_flow.

Cela permet d’utiliser Numpy pour accélérer la configuration des problèmes.

CP-SAT

Quelques améliorations:

  • la planification (propagation, coupures, limites inférieures).
  • MaxSAT (presolve, core-based heuristiques).
  • Performances MIP (presolve, cuts).

Mars 2022

Sortie d'OR-Tools v9.3

Nous avons lancé la version 9.3 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Modifications des plates-formes

  • Fin de la compatibilité avec Debian-10.
  • Fin de la compatibilité avec Ubuntu-16.04.
  • Suppression de .NET Framework 4.5.2.

Mise à jour des dépendances

  • Ajout d'Eigen 3.4.0.
  • Ajout de Google Re2 2021-11-01.
  • Protobuf 3.19.1 -> 3.19.4.
  • SCIP 7.0.1 -> v800.

Python

  • Ajoutez pybind11.

Caractéristiques

  • Ajout de PDLP comme expérimental.
  • Ajout de MathOpt comme expérimental.

CP-SAT

  • Changement de nom : quelques API ont été renommées dans un souci de cohérence, par exemple LinearExpr.ScalProd. -> LinearExpr.WeightedSum..
  • Ajout des méthodes AddAtLeastOne/AddAtMostOne/AddExactlyOne.
  • Ajouter AddMultiplicationConstraint(z, x, y) dans toutes les langues.
  • Ajouter AddMultipleCircuit() dans toutes les langues.

C++

  • Acteur explicite IntVar(BoolVar).
  • Suppression de LinearExpr::Add* et remplacement par l'opérateur LinearExpr +=, par exemple.
  • Ajout d'opérateurs arithmétiques à une expression linéaire.
  • Suppression de LinearExpr::BooleanSum/BooleanScalProd. Utilisez Sum/WeightedSum.
  • Ajoutez CpModelBuilder::FixVariable() pour remplacer le domaine de la variable par une valeur unique.

Java

  • Réécrivez LinearExpr et ajoutez une classe de compilateur incrémentielle : LinearExpr.newBuilder().add(x).addSum(<array of variables>).build().
  • Suivi de l'API C++: Circuit, MultipleCircuit, Cumulative, Reservoir, AllowedAssignment et ForbiddenAssignment renvoient désormais une classe spécialisée avec une API incrémentielle pour ajouter de nouvelles variables, conditions, demandes...

C

  • Documentez toutes les méthodes.
  • Suivi de l'API C++: Circuit, MultipleCircuit, Cumulative, Reservoir, AllowedAssignment et ForbiddenAssignment renvoient désormais une classe spécialisée avec une API incrémentielle pour ajouter de nouvelles variables, conditions, demandes...
  • Ajout de la classe LinearExprBuilder pour créer des expressions de manière incrémentielle.

Système de compilation

CMake

  • Nécessite au moins CMake 3.18 ou version ultérieure.

Marque

  • Utilisez maintenant le build basé sur CMake en interne.

Décembre 2021

Sortie d'OR-Tools v9.2

Nous avons lancé la version 9.2 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Modifications des plates-formes

  • Prise en charge d'Ubuntu 21:10 (dernière version glissante).

Mise à jour des dépendances

  • Mise à jour .Net TFM net5.0 -> net6.0 (nécessite .Net SDK 6.0 LTS et .Net SDK 3.1 LTS).
  • abseil-cpp 20210324.2 -> 20211102.0.
  • Protobuf 3.18.0 à 3.19.1.
  • Googletest 1.10.0 à 1.11.0.
  • Python: ajoutez numpy >= 1.13.3.
  • Sous macOS, compilez Coin-OR dans -O1 pour éviter le plantage des exécuteurs.

Routage

  • Amélioration des filtres.
  • Améliorer la première heuristique de la solution
  • Améliorez le placement des coupures temporelles.

CP-SAT

Modifications destructives

  • Le tampon de protocole sous-jacent n'est pas compatible avec les versions précédentes. Tout tampon de protocole stocké devra être généré à nouveau avec les API de compilateur mises à jour (en C++, Python, Java et .NET).
  • En particulier, l'intervalle protobuf a été nettoyé, car nous avons supprimé les anciens champs (start, size et end) et renommé les nouveaux (à l'aide de _view) pour utiliser le nom des champs supprimés.

Nouvelles fonctionnalités

  • Les contraintes all_different, reservoir, modulo, multiplication et division acceptent les expressions affine (a * var + b) partout où des variables entières sont requises.
  • L'objectif accepte les coefficients à virgule flottante (consultez la classe DoubleLinearExpr en C++/Java/.NET). Consultez l'exemple knapsack_2d_sat.py en Python.
  • La contrainte no_overlap_2d accepte les intervalles facultatifs.
  • L'API C++ implémente les opérateurs + et * pour créer des expressions.

Améliorations

  • Amélioration du code de prérésolution.
  • Outil de vérification de modèle plus serré
  • Préparer la contrainte de réservoir.
  • Ajoutez des coupes dynamiques à la contrainte no_overlap_2d.
  • Amélioration de l'assouplissement linéaire des contraintes d'encodage (literal implies var == value).

Méthodes obsolètes et supprimées

  • Abandon de C++ BooleanSum et BooleanScalProd. Utilisez simplement Sum et ScalProd.
  • Suppression de C++ AddLinMinEquality et AddLinMaxEquality. Utilisez simplement AddMinEquality et AddMaxEquality.

Incompatibilités futures

  • À un moment donné, nous réécrirons la couche de modélisation Java pour qu'elle soit plus proche de la couche C++.
  • Dans la couche de modélisation C++, nous allons rendre explicite le ctor IntVar(BoolVar var).
  • Nous envisageons de rendre l'API Python compatible avec PEP 8 (en utilisant les noms snake_case). Dans ce cas, nous fournissons un fichier sed pour transférer le code.

Système de compilation

Bazel

  • Correction du build Windows.

CMake

  • Ajout de l'option FETCH_PYTHON_DEPS (ON par défaut).
  • Ajout facultatif de la compatibilité avec le résolveur GPLK (-DUSE_GLPK=OFF par défaut).

Python

  • Prend en charge les entiers numpy dans la plupart de l'API CP-SAT.
  • Correction du problème de __version__ manquant.

Septembre 2021

Sortie d'OR-Tools v9.1

Nous avons lancé la version 9.1 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Modifications des plates-formes

  • Python: utilisez l'image manylinux2014 (voir PEP 599).
  • Python: prise en charge de Linux aarch64 à l'aide de l'image manylinux2014_aarch64.
  • .Net: ajouter la compatibilité avec .Net 5.0.

Mise à jour des dépendances

  • abseil-cpp 20210324.1 -> 20210324.2.
  • Protobuf 3.15.8 à 3.18.0.
  • SCIP 7.0.1 -> maître.
  • Googletest 1.8.0 -> 1.10.0.
  • Python: utilisation de warning dans cp_model.py (voir #2530).
  • python: absl-py 0.11 -> 0.13.

CMake

  • Passer la version minimale requise : 3.14 -> 3.15 (voir #2528).
  • Python : repoussez la version minimale requise : 3.14 -> 3.18 (voir #2774).

Marque

Le build basé sur Make est obsolète. Veuillez migrer vers CMake ou Bazel pour compiler à partir de la source.

Java

  • Amélioration de la robustesse du chargeur de bibliothèque natif (voir la section #2742).
  • Correction du plantage du récupérateur de mémoire JVM lors de la suppression du modèle de routage ou de la suppression de contraintes (voir #2091) (voir #2466).
  • Correction du plantage lié au rappel de la journalisation CP-SAT lors de l'utilisation de plusieurs nœuds de calcul (voir la section #2775).

CP-SAT

  • Amélioration de la robustesse du code LNS (voir #2525).
  • Amélioration du code de planification: nouvelles méthodes de fabrique pour créer des intervalles de taille fixe, nouvelles heuristiques de recherche, une meilleure résolution et de nouvelles coupes linéaires.
  • Amélioration du code de routage: nouveau LNS dédié.
  • Amélioration de l'outil de vérification de modèles Elle est désormais plus pédante, surtout avec des dépassements potentiels.
  • Amélioration du code MIP: meilleure résolution et améliorations multiples de l'assouplissement linéaire des modèles MIP et CP.
  • Diversifiez vos recherches. Lorsque vous utilisez plus de 12 nœuds de calcul, ajoutez des nœuds de calcul dédiés à l'amélioration de la limite inférieure de l'objectif.
  • Passez au code de parallélisme: par défaut, le résolveur utilise désormais tous les cœurs disponibles. Utilisez num_search_parameters pour spécifier le niveau de parallélisme.
  • Abandon de SearchAllSolutions et SolveWithSolutionCallback.
  • API Python: contrôles plus pédiques en cas d'utilisation de var == ... ou var != ... en dehors d'un appel model.Add().

Avril 2021

Sortie d'OR-Tools v9.0

Nous avons lancé la version 9.0 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Mises à jour des dépendances

  • Abseil-cpp 20200923.3, mis à jour vers 20210324.1 LTS.
  • Protobuf 3.15.3 a été mis à jour vers la version 3.15.8.
  • Java: jna-platform 5.5.0 mis à jour vers la version 5.8.0

Java

Corrections de bugs

  • Amélioration du multithreading lors de l'utilisation du résolveur CP-SAT (voir #1588).
  • Correction de la compatibilité du wrapper Python avec std::vector&ltstd::string&gt (voir la section #2453).
  • Améliorer la compatibilité avec CPLEX (voir #2470)

Modification destructive connue

  • Ajout de l'accès à l'enregistreur en Python, Java et .Net (voir #2245)
  • Remplacement de tous les types Google personnalisés par ceux fournis dans cstdint.

CP-SAT

  • Les méthodes SearchForAllSolutions(), SearchAllSolutions() et SolveWithSolutionCallback() sont obsolètes. Veuillez utiliser Solve() à la place.
  • Amélioration de la compatibilité avec les opérateurs standards Python. Cela peut rompre le code existant incorrect.

Mars 2021

Sortie d'OR-Tools v8.2

Nous avons lancé la version 8.2 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Mises à jour des dépendances

  • Abseil-cpp 20200923.2, mis à jour vers la version 20200923.3 LTS.
  • Protobuf 3.14.0 a été mis à jour vers la version 3.15.3.

Routage

  • Ajout de RoutingModel.RegisterTransitMatrix() et de RoutingModel.RegisterUnaryTransitVector().
  • Remplacez le retour de RoutingModel.AddVectorDimension() et RoutingModel.AddMatrixDimension() par std::pair&ltint, bool&gt dont l'int est l'ID de l'évaluateur des transports en commun.

Décembre 2020

Sortie d'OR-Tools v8.1

Nous avons lancé la version 8.1 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Mises à jour des dépendances

  • Abseil-cpp 20200923, mis à jour vers 20200923.2 LTS.
  • Protobuf 3.13.0 a été mis à jour vers la version 3.14.
  • Ajouter la prise en charge de Gurobi 9.1.0
  • Dépendance GLog supprimée (remplacée par une implémentation personnalisée selon les indicateurs abseil-cpp)
  • Dépendance GFlag (remplacée par le composant abseil-cpp)

Corrections de bugs

  • Correction du double comptage de la licence flottante Gurobi (voir #2227).
  • Correction de la compilation Windows (voir #2200).

octobre 2020

Sortie d'OR-Tools v8.0

Nous avons lancé la version 8.0 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Modifications des plates-formes

  • Ajout de la compatibilité avec Python 3.9. (#2187)
  • Abandon de la compatibilité avec Python 3.5 (#2186) <!-- Waiting Microsoft dotnet-sdk support, could be generate after the release is out...
    • Ajout de la prise en charge d'Ubuntu 20.10 (#2188). -->
  • Abandon de la compatibilité avec Ubuntu 16.04 LTS. (#2188)
  • Abandon de la compatibilité avec Ubuntu 19.10. (#2188)

Mises à jour des dépendances

  • Abseil-cpp 20200225.2, mis à jour vers 20200923 LTS.
  • Protobuf 3.12.2 mis à jour vers la version 3.13.0.

Modification destructive connue

  • À présent, le routage et le code source CP-SAT utilisent certaines fonctionnalités de C++17. Avertissement: Si vous fournissez votre propre version de abseil-cpp, veuillez vérifier qu'elle est également compilée avec C++17.
  • La signature MPSolver::CreateSolver a été modifiée. L'argument du nom du modèle a été supprimé.

CMake

  • Correction de la désactivation de la compatibilité SCIP lors de l'utilisation de -DUSE_SCIP=OFF (voir la section #2129).
  • Intégrez des exemples au système de compilation CMake. Remarque: vous pouvez la désactiver à l'aide de -DBUILD_SAMPLES=OFF et de -DBUILD_EXAMPLES=OFF. Remarque: Il peut être désactivé pour une langue spécifique à l'aide de -DBUILD_<LANG>_SAMPLES=OFF ou -DBUILD_<LANG>_EXAMPLES=OFF.
    • Avec <LANG> parmi:
    • CXX,
    • PYTHON,
    • JAVA et
    • DOTNET.

Marque

  • Nécessite Make >= 4.3 (utilisation de la fonction d'évaluation Make).
  • Nécessite CMake >= 3.14 (utilisation de l'option --verbose de CMake).
  • Ajout d'une option permettant de désactiver la compatibilité SCIP à l'aide de -DUSE_SCIP=OFF (voir la section #2134).
  • Ajout d'une option permettant de désactiver la compatibilité CLP et CBC à l'aide de -DUSE_COINOR=OFF.

Java

  • Les outils OR génèrent maintenant des packages Maven (voir #202).

Corrections de bugs

  • Correction du build C++ et Python sous FreeBSD (voir #2126).
  • Correction de la compilation dans le débogage sous Windows (voir #2077).
  • Correction des plantages de longue durée en parallèle sur CP-SAT sous Windows (voir #2001, #2019).

Juillet 2020

Sortie d'OR-Tools v7.8

Nous avons lancé la version 7.8 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Mises à jour des dépendances

  • Gurobi 9.0.2 est désormais pré-intégré dans les binaires prédéfinis. Elle recherchera la bibliothèque partagée gurobi 90 dans le chemin d'installation par défaut des programmes d'installation Gurobi sur MAC OS X et Windows, ou dans le répertoire GUROBI_HOME.
  • SCIP 7.0.1 est désormais intégré aux binaires prédéfinis. Veuillez vous assurer qu'elle est conforme à la licence SCIP avant de l'utiliser.
  • Ajout de la prise en charge de Xpress Solver 8.9.0 (facultatif).

Solveur linéaire

  • Ajout d'une méthode LinearSolver::CreateSolver() statique pour simplifier la vérification de la compatibilité des backends de solutions linéaires intégrés. Il fonctionne dans toutes les langues.

Corrections de bugs

  • Correction du build basé sur CMake sur FreeBSD.
  • Correction du tri CP-SAT lors de la génération de coupes cumulatives.
  • Correction de la fuite de mémoire du résolveur linéaire dans le wrapper .Net.

Juin 2020

Sortie d'OR-Tools v7.7

Lancement de la version 7.7 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Mises à jour des dépendances

  • Abseil-cpp b832dce mis à jour vers c51510d (LTS 20200225.2).
  • Protobuf 3.11.4 a été mis à jour vers la version 3.12.2.

Nouvelles fonctionnalités et améliorations

  • Le résolveur CP-SAT renvoie désormais Optimal au lieu de Feasible dans un modèle de satisfaction (c'est-à-dire sans objectif).
  • Ajout de l'heuristique de pompe de faisabilité de la communauté MIP.

Corrections de bugs

Correction du plantage du multithreading CP-SAT (voir #2005).

Avril 2020

Sortie d'OR-Tools v7.6

Lancement de la version 7.6 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Nouvelles fonctionnalités CP-SAT

Nous avons ajouté les nouvelles fonctionnalités suivantes au résolveur CP-SAT:

  • Amélioration de la gestion des plans de coupe pour les pages de destination.
  • Outils de débogage

Mises à jour des dépendances

Abseil-cpp 8ba96a8 mis à jour vers b832dce (LTS 20200225).

Corrections de bugs

  • Correction du bug CP-SAT UNSAT dans presolve (voir #1908).
  • Correction de l'URL swigwin.exe.
  • Correction de la gestion des mappages de types SWIG pour Java et .Net.

Janvier 2020

Sortie d'OR-Tools v7.5

Nous avons lancé la version 7.5 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Modifications des plates-formes

  • Ajout de la compatibilité avec Python 3.8. (#1719)
  • Suppression de la compilation de la prise en charge à partir des sources de Visual Studio 2017. (#1852)
  • Mise à jour de la compatibilité de Centos 7 vers Centos 8. (#1827)

Mise à jour de la dépendance

Corrections de bugs

Les problèmes suivants ont été résolus dans la version 7.5 des outils OR (pour obtenir la liste complète, consultez Jalon version 7.5).

En particulier :

  • Correction du chargement de l'assemblage. Consultez la section #1421.
  • Exposition des méthodes GetStartIndex() et GetEndIndex() de RouteIndexManager. (#1843)
  • Correction de SWIG pour supprimer les méthodes défectueuses. (#1838, #1276)

octobre 2019

Sortie d'OR-Tools v7.4

Nous avons lancé la version 7.4 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Nouvelles fonctionnalités et améliorations

  • Le résolveur CP-SAT recherche à présent les contraintes qui ne sont pas compatibles avec les littéraux d'application. Le vérificateur de modèle renvoie une erreur avant de résoudre le problème si une telle contrainte est associée à un littéral d'application.
  • Recherche locale améliorée et plus rapide pour la bibliothèque de routage.
  • Le résolveur linéaire est désormais compatible avec le logiciel tiers Xpress-MP. Vous devrez recompiler OR-Tools à partir de la source pour l'utiliser.
  • L'architecture du package NuGet a été entièrement réécrite. En particulier, il est désormais compatible avec .NET Framework 4.5.2 ou version ultérieure sur les plates-formes Windows.

Plate-forme obsolète

Comme annoncé dans les notes de version de juillet 2019, OR-Tools n'est plus compatible avec Python 2.7.

Mise à jour de la dépendance

La version 3.9.0 de Protobuf a été mise à jour vers la version 3.10.0.

Août 2019

Sortie d'OR-Tools v7.3

Nous avons lancé la version 7.3 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Plate-forme obsolète

Dans le cadre de la migration de Google vers Python 3, nous abandonnons la prise en charge de Python 2.7. Il s'agit de la dernière version des outils OR prenant en charge Python 2.7.

Mise à jour de la dépendance

La version 3.8.0 de Protobuf a été mise à jour vers la version 3.9.0.

Corrections de bugs

Les problèmes suivants ont été résolus dans la version 7.3 des outils OR. (Pour obtenir la liste complète, consultez Kanban v7.3.)

En particulier :

  • Correction du problème de diffusion init/int64 sous Java. (#1448)
  • Correction de la vérification de presolve lors du traitement de contraintes cumulées vides.

Juillet 2019

Sortie d'OR-Tools v7.2

Nous avons lancé la version 7.2 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Modifications des plates-formes

  • Dans le cadre de la migration de Google vers Python 3, nous abandonnons la prise en charge de Python 2.7. Il existera au maximum une version supplémentaire des outils OR prenant en charge Python 2.7.
  • Ubuntu 18.10 a été mis à jour vers Ubuntu 19.04.
  • Ajout de la prise en charge de la compilation à partir de sources dans Visual Studio 2019.
  • Python 3.5 n'est plus pris en charge sous Windows. Veuillez utiliser Python 3.6 ou une version ultérieure.

Mises à jour des dépendances

  • Nous ciblons désormais CBC 2.10.3.
  • Nous ciblons désormais Protobuf 3.8.0.

CP-SAT

  • Nous avons apporté plusieurs améliorations à la recherche, au parallélisme et à l'assouplissement linéaire.
  • Ajout des API LinearExpr.Sum() et LinearExpr.ScalProd() dans Python.
  • Abandon des API IntVar[].Sum() et IntVar[].ScalProd() en C#.
  • C++: suppression de SolveWithModel(), car il s'agissait d'un doublon de SolveCpModel().
  • Ajout des méthodes CpModel.addGreaterThan() et CpModel.addLessThan() à l'API Java.

Solutionneur linéaire

  • Ajout de MPSolver.SetHint() pour Python, Java et C# (compatible avec SCIP et Gurobi).
  • Ajout de MPSolver.SetNumThreads() pour Python, Java et C# (compatible avec CBC, Gurobi et SCIP).
  • Réécriture de la compatibilité avec SCIP 6.0.1

Documentation de référence

  • Nous avons ajouté des manuels de référence basés sur Doxygen et pdoc3 pour tous les langages et tous les outils (algorithmes, routage, graphe, linear_solver et CP-SAT). Consultez les manuels de référence des outils OR.
  • La documentation de référence est complète pour C++ (tous les produits) et CP-SAT (C++, Python, Java).
  • Nous sommes en train d'exporter toute la documentation C++ vers Python et Java.
  • Il manque la documentation .NET, et nous n'avons pas de solution dans un avenir proche pour améliorer cela. Nous l'avons conservé, car il affiche toujours l'API disponible.

Mai 2019

Sortie d'OR-Tools v7.1

Nous avons lancé la version 7.1 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Modifications apportées aux dépendances requises

OR-Tools v7.1 comporte les nouvelles dépendances suivantes et celles mises à jour:

  • v0.3.5 de glog mise à jour vers v0.4.0
  • v3.6.1 de protobuf mis à jour vers la révision 3.7.1
  • Mise à jour de la version 2.9.9 de Cbc vers la version 2.10.1
  • La version 0.59.10 de Cgl a été mise à jour vers la version 0.60.1.
  • La version 1.16.11 de Clp a été mise à jour vers la version 1.77.1.
  • Osi 0.107.9 mis à jour vers la version 0.108.1
  • Version 2.10.14 de CoinUtils mise à jour vers la version 2.11.1

Modifications apportées à l'API CP-SAT

Les sections suivantes décrivent les modifications apportées à l'API CP-SAT dans OR-Tools 7.1.

Utiliser Domain pour créer des variables

Les exemples suivants montrent comment créer une variable entière avec des domaines non contigus. Cette opération remplace la méthode supprimée NewEnumeratedIntVar(). Ici, la variable x peut être l'une des valeurs suivantes : 1, 3, 4 ou 6 :

Python

model.NewIntVarFromDomain(cp_model.Domain.FromValues([1, 3, 4, 6]), 'x')

C++

model.NewIntVar(Domain::FromValues({1, 3, 4, 6}));

Java

model.newIntVarFromDomain(Domain.fromValues(new long[] {1, 3, 4, 6}), "x");

C#

model.NewIntVarFromDomain(Domain.FromValues(new long[] {1, 3, 4, 6}), "x");

Vous pouvez également créer des variables à l'aide d'une liste d'intervalles. Ci-dessous, la variable x est limitée à 1, 2, 4, 5 ou 6:

Python

model.NewIntVarFromDomain(cp_model.Domain.FromIntervals([[1, 2], [4, 6]]), 'x')

C++

model.NewIntVar(Domain::FromIntervals({ {1, 2}, {4, 6} }));

Java

model.newIntVarFromDomain(Domain.fromIntervals(new long[][] { {1, 2}, {4, 6} }), "x");

C#

model.NewIntVarFromDomain(Domain.FromIntervals(new long[][] { new long[] {1, 2}, new long[] {4, 6} }), "x");

Utiliser "Domain" dans une expression linéaire

Les exemples suivants montrent comment limiter une expression linéaire sur un domaine non contigu. Ici, l'expression linéaire linear_expr est définie sur 5, 6, 8, 9 et 10:

Python

model.AddLinearExpressionInDomain(linear_expr, cp_model.Domain.FromIntervals([(5, 6), (8, 10)]))

C++

model.AddLinearConstraint(linear_expr, Domain::FromIntervals({ {5, 6}, {8, 10} }))

Java

model.addLinearExpressionInDomain(linear_expr, Domain.fromIntervals(new long[][] { {5, 6}, {8, 10} }))

.NET

model.AddLinearExpressionInDomain(linear_expr, Domain.FromIntervals(new long[][] {new long[] {5, 6}, new long[] {8, 10} }));

Utiliser des assistants d'expression linéaire

Les exemples suivants montrent comment utiliser les méthodes d'assistance pour créer des sommes et des produits scalaires. Voici des exemples où x + y == 20 et 4 * x + 2 * y = 56:\

Python

model.Add(x + y == 20)
model.Add(4 * x + 2 * y == 56)

C++

cp_model.AddEquality(LinearExpr::Sum({x, y}), 20);
cp_model.AddEquality(LinearExpr::ScalProd({x, y}, {4, 2}), 56);

Java

model.addEquality(LinearExpr.sum(new IntVar[] {x, y}), 20);
model.addEquality(LinearExpr.scalProd(new IntVar[] {x, y}, new long[] {4, 2}), 56);

.NET

model.Add(x + y == 20);
model.Add(4 * x + 2 * y == 56);

Mars 2019

Sortie d'OR-Tools v7.0

Nous avons lancé la version 7.0 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Modifications apportées aux plates-formes compatibles

OR-Tools v7.0 n'est plus compatible avec les plates-formes suivantes:

  • Visual C++ 2015
  • Ubuntu 14.04
  • Python 3.4 sur Linux

Si vous utilisez l'une de ces plates-formes, vous pouvez toujours installer OR-Tools v6.10.

Modifications apportées aux dépendances requises

OR-Tools v7.0 dispose des nouvelles dépendances suivantes et de celles mises à jour:

Les sections suivantes décrivent les nouvelles fonctionnalités et améliorations de OR-Tools 7.0.

Nouveau gestionnaire d'index pour les programmes de routage

Dans la version 7.0 de OR-Tools, les programmes de calcul d'itinéraires de véhicules doivent utiliser le nouveau RoutingIndexManager. Cela garantit que les index standards des emplacements sont cohérents avec les index internes utilisés par le résolveur et permet d'éviter les erreurs dans votre code.

Le nouveau RoutingIndexManager nécessite des modifications mineures des programmes de routage, décrites dans les sections suivantes:

Inclure/Importer RoutingIndexManager

Dans OR-Tools 7.0, les programmes de routage en C++ et Java doivent inclure ou importer RoutingIndexManager, comme indiqué dans les exemples ci-dessous:

C++

#include "ortools/constraint_solver/routing_index_manager.h"

Java

import com.google.ortools.constraintsolver.RoutingIndexManager;

Les importations Python et C# restent inchangées.

Déclarer RoutingIndexManager

Dans la version 7.0 des outils de routage, les programmes de routage doivent déclarer le RoutingIndexManager et créer le modèle de routage, comme illustré dans les exemples suivants:

Python

manager = pywrapcp.RoutingIndexManager(num_locations, num_vehicles, depot)
routing = pywrapcp.RoutingModel(manager)

C++

RoutingIndexManager manager(num_locations, num_vehicles, depot);
RoutingModel routing(manager);

Java

RoutingIndexManager manager = new RoutingIndexManager(numLocations, numVehicles, depot);
RoutingModel routing = new RoutingModel(manager);

.NET

RoutingIndexManager manager = new RoutingIndexManager(numLocations, numVehicles, depot);
RoutingModel routing = new RoutingModel(manager);

Les arguments de RoutingIndexManager sont les suivants:

  • le nombre d'établissements ;
  • Le nombre de véhicules
  • L'indice du dépôt (points de départ et d'arrivée pour tous les véhicules)

Rappels

Dans la version 7.0 des outils OR, vous devez utiliser RoutingIndexManager pour créer des rappels, tels que le rappel de distance, que vous transmettez ensuite au résolveur. Les exemples suivants montrent comment créer un rappel de distance.

Python

    def distance_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data["distance_matrix"][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

C++

  const int transit_callback_index = routing.RegisterTransitCallback(
      [&data, &manager](const int64_t from_index,
                        const int64_t to_index) -> int64_t {
        // Convert from routing variable Index to distance matrix NodeIndex.
        const int from_node = manager.IndexToNode(from_index).value();
        const int to_node = manager.IndexToNode(to_index).value();
        return data.distance_matrix[from_node][to_node];
      });
  routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);

Java

    final int transitCallbackIndex =
        routing.registerTransitCallback((long fromIndex, long toIndex) -> {
          // Convert from routing variable Index to user NodeIndex.
          int fromNode = manager.indexToNode(fromIndex);
          int toNode = manager.indexToNode(toIndex);
          return data.distanceMatrix[fromNode][toNode];
        });
    routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

.NET

        int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) =>
                                                                   {
                                                                       // Convert from routing variable Index to
                                                                       // distance matrix NodeIndex.
                                                                       var fromNode = manager.IndexToNode(fromIndex);
                                                                       var toNode = manager.IndexToNode(toIndex);
                                                                       return data.DistanceMatrix[fromNode, toNode];
                                                                   });
        routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

La méthode IndexToNode convertit les index de localisation internes utilisés par le résolveur en index standards pour la matrice des distances.

Au lieu de transmettre le rappel directement au résolveur, comme dans les versions précédentes, dans la version 7.0, vous devez d'abord créer transit&nbsp;callback&nbsp;index, une référence au rappel, puis la transmettre au résolveur (dans ce cas avec SetArcCostEvaluatorOfAllVehicles).

Dimensions

Les exemples suivants montrent comment créer une dimension pour les demandes et les capacités, qui permet de résoudre le problème de calcul d'itinéraire des véhicules limité.

Python

    def demand_callback(from_index):
        """Returns the demand of the node."""
        # Convert from routing variable Index to demands NodeIndex.
        from_node = manager.IndexToNode(from_index)
        return data["demands"][from_node]

    demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
    routing.AddDimensionWithVehicleCapacity(
        demand_callback_index,
        0,  # null capacity slack
        data["vehicle_capacities"],  # vehicle maximum capacities
        True,  # start cumul to zero
        "Capacity",
    )

C++

  const int demand_callback_index = routing.RegisterUnaryTransitCallback(
      [&data, &manager](const int64_t from_index) -> int64_t {
        // Convert from routing variable Index to demand NodeIndex.
        const int from_node = manager.IndexToNode(from_index).value();
        return data.demands[from_node];
      });
  routing.AddDimensionWithVehicleCapacity(
      demand_callback_index,    // transit callback index
      int64_t{0},               // null capacity slack
      data.vehicle_capacities,  // vehicle maximum capacities
      true,                     // start cumul to zero
      "Capacity");

Java

    final int demandCallbackIndex = routing.registerUnaryTransitCallback((long fromIndex) -> {
      // Convert from routing variable Index to user NodeIndex.
      int fromNode = manager.indexToNode(fromIndex);
      return data.demands[fromNode];
    });
    routing.addDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack
        data.vehicleCapacities, // vehicle maximum capacities
        true, // start cumul to zero
        "Capacity");

.NET

        int demandCallbackIndex = routing.RegisterUnaryTransitCallback((long fromIndex) =>
                                                                       {
                                                                           // Convert from routing variable Index to
                                                                           // demand NodeIndex.
                                                                           var fromNode =
                                                                               manager.IndexToNode(fromIndex);
                                                                           return data.Demands[fromNode];
                                                                       });
        routing.AddDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack
                                                data.VehicleCapacities, // vehicle maximum capacities
                                                true,                   // start cumul to zero
                                                "Capacity");

Solutions d'impression

Dans OR-Tools v7.0, vous devez utiliser RoutingIndexManager pour afficher les itinéraires des véhicules dans une solution. Les exemples suivants montrent comment imprimer des solutions dans tous les langages compatibles.

Python

def print_solution(manager, routing, solution):
    """Prints solution on console."""
    print(f"Objective: {solution.ObjectiveValue()}")
    index = routing.Start(0)
    plan_output = "Route for vehicle 0:\n"
    route_distance = 0
    while not routing.IsEnd(index):
        plan_output += f" {manager.IndexToNode(index)} ->"
        previous_index = index
        index = solution.Value(routing.NextVar(index))
        route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
    plan_output += f" {manager.IndexToNode(index)}\n"
    plan_output += f"Distance of the route: {route_distance}m\n"
    print(plan_output)

C++

//! @brief Print the solution
//! @param[in] manager Index manager used.
//! @param[in] routing Routing solver used.
//! @param[in] solution Solution found by the solver.
void PrintSolution(const RoutingIndexManager& manager,
                   const RoutingModel& routing, const Assignment& solution) {
  LOG(INFO) << "Objective: " << solution.ObjectiveValue();
  // Inspect solution.
  int64_t index = routing.Start(0);
  LOG(INFO) << "Route for Vehicle 0:";
  int64_t distance{0};
  std::stringstream route;
  while (!routing.IsEnd(index)) {
    route << manager.IndexToNode(index).value() << " -> ";
    const int64_t previous_index = index;
    index = solution.Value(routing.NextVar(index));
    distance += routing.GetArcCostForVehicle(previous_index, index, int64_t{0});
  }
  LOG(INFO) << route.str() << manager.IndexToNode(index).value();
  LOG(INFO) << "Distance of the route: " << distance << "m";
  LOG(INFO) << "";
  LOG(INFO) << "Advanced usage:";
  LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}

Java

  /// @brief Print the solution.
  static void printSolution(
      DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
    // Solution cost.
    logger.info("Objective : " + solution.objectiveValue());
    // Inspect solution.
    logger.info("Route for Vehicle 0:");
    long routeDistance = 0;
    String route = "";
    long index = routing.start(0);
    while (!routing.isEnd(index)) {
      route += manager.indexToNode(index) + " -> ";
      long previousIndex = index;
      index = solution.value(routing.nextVar(index));
      routeDistance += routing.getArcCostForVehicle(previousIndex, index, 0);
    }
    route += manager.indexToNode(routing.end(0));
    logger.info(route);
    logger.info("Distance of the route: " + routeDistance + "m");
  }

.NET

    /// <summary>
    ///   Print the solution.
    /// </summary>
    static void PrintSolution(in RoutingModel routing, in RoutingIndexManager manager, in Assignment solution)
    {
        Console.WriteLine("Objective: {0}", solution.ObjectiveValue());
        // Inspect solution.
        Console.WriteLine("Route for Vehicle 0:");
        long routeDistance = 0;
        var index = routing.Start(0);
        while (routing.IsEnd(index) == false)
        {
            Console.Write("{0} -> ", manager.IndexToNode((int)index));
            var previousIndex = index;
            index = solution.Value(routing.NextVar(index));
            routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0);
        }
        Console.WriteLine("{0}", manager.IndexToNode((int)index));
        Console.WriteLine("Distance of the route: {0}m", routeDistance);
    }

Assistance pour les VRP avec retrait et livraison

OR-Tools v7.0 permet de résoudre les problèmes d'itinéraire de véhicules (VRP) avec les retraits et les livraisons, l'objectif étant de trouver les itinéraires les plus courts pour un parc de véhicules qui récupèrent et livrent des articles à différents endroits. Vous configurez le problème de la même manière qu'un VRP standard, mais en plus, vous spécifiez une paire (i, j) de lieux pour chaque article, où "i" correspond au lieu de prise en charge et "j" au lieu de dépôt. Le résolveur d'itinéraire renvoie les itinéraires du véhicule de sorte que pour chaque paire (i, j), i et j se trouvent sur le même itinéraire, et que le véhicule passe à i avant j.

Pour voir un exemple qui résout ce type de problème, consultez la section Itinéraires de véhicules avec retraits et livraisons.

Compatibilité avec les fonctions lambda

La version 7.0 de OR-Tools prend désormais en charge les fonctions lambda en C# et Java (en plus de C++ et Python, qui étaient déjà compatibles). Les fonctions lambda offrent un moyen pratique de définir des rappels dans les programmes de routage. Toutefois, vous pouvez définir des rappels à l'aide de fonctions standards si vous pensez que cela améliore la lisibilité de votre code.

Les exemples de rappel C# et Java ci-dessus montrent comment définir des rappels à l'aide des fonctions lambda.

novembre 2018

Sortie de la version 6.10

Nous avons lancé la version 6.10 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Les sections suivantes décrivent les nouvelles fonctionnalités et améliorations apportées dans la version 6.10.

Des commandes simplifiées pour la création et l'exécution de programmes

Dans la version 6.10, vous pouvez créer et exécuter des programmes en saisissant des commandes comme celles-ci :

make run SOURCE=relative/path/to/program.cc
, où <var>relative/path/to</var> est le chemin d'accès au répertoire contenant le programme.

Pour créer un programme sans l'exécuter, saisissez : 

make build SOURCE=relative/path/to/program.cc
Consultez la section Premiers pas avec les outils OR pour obtenir des instructions spécifiques sur l'exécution de programmes par langage.

Compatibilité avec SCIP 6.0.0

Les outils OR sont désormais compatibles avec SCIP 6.0.0.

Binaires

Les distributions binaires ont été créées à l'aide de Java JDK 8 (JDK 7 pour Ubuntu 14.04).

Solveur CP-SAT

Mettre à jour l'API

  • Ajout de l'API C++ CP-SAT CpModelBuilder.

Exemples

Certains exemples ont été déplacés.

  • Déplacer les exemples de la communauté vers examples/contrib.
  • Déplacez quelques exemples vers ortools/<var>component</var>/samples (ex. : ortools/linear_solver/samples/simple_program.java).

Septembre 2018

Sortie de la version 6.9

Nous avons lancé la version 6.9 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Dépendances mises à jour

  • Protobuf 3.5.1 -> 3.6.1.
  • SCIP 4.0 -> 6.0.

Solveur CP-SAT

  • Modifications importantes apportées à l'API (en savoir plus) :
  • SolveWithSolutionObserver a été renommé SolveWithSolutionCallback dans Python.

  • NewSolution a été renommé OnSolutionCallback dans la classe CpSolverSolutionCallback en Python. L'exemple suivant vous montre la nouvelle façon de créer un rappel de solution en Python. 

    class MySolutionCallback(cp_model.CpSolverSolutionCallback):
def init(self):
cpmodel.CpSolverSolutionCallback.init(self)
self._solution_count = 0
    


    def OnSolutionCallback(self):
print('Solution {}, time = {}s, objective = {}, makespan = {}'.format(
  self.solution_count,
  self.WallTime(),
  self.ObjectiveValue(),
  self.Value(makespan)))
self.solution_count += 1

  • Exposition de StopSearch sur le rappel de solution en Python, Java et C#. Cliquez ici pour consulter la documentation.

  • Exposez ModelStats et CpSolverResponseStats dans Python, Java et C#.

  • Amélioration de la documentation Python sur les docstrings. Cliquez ici pour consulter la documentation.

  • Mises à jour de l'implémentation Java de l'interface du résolveur et du livre de recettes.

  • Implémentez le modulo.

  • Modifiez l'implémentation du réservoir: ajoutez une API avec des valeurs booléennes pour spécifier les événements de drainage/remplissage facultatifs.

Solveur linéaire

  • Exposez InterruptSolve en Java et C#.

Solutionneur CP

  • Exposition du directeur SolutionCollector en C#.

Python

  • Ajout de la prise en charge de Python 3.7.
  • Lors de la compilation à partir de la source, préférez python3 à python2 lors de la détection de Python.

.NET

  • Réécriture complète de la couche .NET.
  • Fournissez un package Nuget NetStandard 2.0 Google.OrTools compatible avec l'identifiant d'exécution win-x64, linux-x64 et osx-x64.
  • Fournissez un package Nuget Google.OrTools.FSharp.
  • Ajoutez un fichier de projet pour tous les exemples .NET.
  • Mettez à jour tous les exemples de scripts F# (.fsx) vers un projet F# standard (.fs).
  • Pour ajouter de la documentation sur la génération de compilation de packages .NET, cliquez ici.

Flatzinc

  • Prise en charge des ensembles dans flatzinc (à l'aide de nosets.mzn).

Contributions

  • Prise en charge de Binder. Merci à Kevin Mader.
  • Définissez DecisionVisitor comme type de directeur dans les liaisons Java. Merci à Jeremy Apthorp.

Juillet 2018

Sortie de la version 6.8

Nous avons lancé la version 6.8 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Annonce du résolveur CP-SAT

Le résolveur CP-SAT est un nouveau résolveur pour la programmation de contraintes. Le résolveur CP-SAT est plus rapide que le résolveur CP d'origine et doit être privilégié pour les problèmes CP.

Pour obtenir des exemples utilisant le résolveur CP-SAT, recherchez dans le répertoire examples des fichiers dont le nom contient _sat.

Le résolveur de CP d'origine sera conservé pendant un certain temps afin de prendre en charge le code existant, mais il est obsolète.

Nouvelles options pour le résolveur CP-SAT

Les options suivantes du résolveur CP-SAT sont nouvelles dans cette version:

  • Recherche de quartiers locaux (LNS): utilisez l'option SatParameters.use_lns pour activer les LNS.
  • Recherche parallèle: utilisez l'option SatParameters.num_search_workers pour activer plusieurs threads lors d'une recherche. Chaque thread peut avoir différents paramètres et différentes valeurs de graine aléatoires. Cela maximise la diversité et la probabilité qu'au moins un thread trouve des solutions.

Amélioration des performances pour les résolveurs

Nous avons amélioré les performances des résolveurs CP-SAT et Glop.

Mars 2018

Sortie de la version 6.7

Nous avons lancé la version 6.7 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de Installation des outils OR.

Mise à jour des dépendances requises

  • Protobuf 3.5.0 -> 3.5.1.

Divers :

  • Refactorisez la base pour préparer l'intégration abseil-cpp.
  • Utilisation des services Travis CI et d'intégration continue (CI) Appveyor

SAM

  • Amélioration des performances.
  • Améliore l'API Python.
  • Ajout de l'API C#, également appelée CpSolver.cs (EXPERIMENTAL).

Glope

  • Refactorisation de code.
  • Amélioration des performances.

Prise en charge de CMake (EXPERIMENTAL)

  • Prise en charge de CMake avec C++ OR-Tools.
  • Vous serez capable de créer des outils OR en tant que projet CMake autonome.
  • Être capable d'intégrer des outils OU dans un projet CMake existant
  • Ajout d'une compilation basée sur CMake pour Python OU-Tools.
  • Générez un package Python (wheel) à l'aide de CMake.

Contributions

  • Correction de la redéfinition de winsock2.h sous Windows. Un grand merci à Florent Tollin de Rivarol.
  • Ajout de la prise en charge de F# (EXPÉRIMENTAL). Merci à Matthew Moore. Remarque: disponible uniquement avec le compilateur Makefile.
  • Ajout de la compatibilité standard .NET (EXPERIMENTAL). Merci à Ziad El Malki. Remarque: disponible uniquement avec le compilateur Makefile.

Novembre 2017

Sortie de la version 6.6

Nous avons lancé la version 6.6 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Mises à jour des dépendances requises

  • Protobuf vers 3.3.0 -> 3.5.0.
  • gflags vers la version 2.2.0 à la version 2.2.1.
  • CBC 2.9.8 -> 2.9.9.
  • Ajout du module Python six (1.10) comme dépendance requise pour Python.

Correction de bugs

  • Demande d'extraction n° 494 Refactorisation de nom. Ajouter des commentaires pour IntelliSense dans certains éditeurs Merci à Matthew Moore.
  • Instruction de demande d'extraction n° 516 pour le binaire autonome F#. Merci à Matthew Moore.
  • Améliorer la précision dans Glop.

Solutionneur SAT

  • Améliorer la résolution SAT interne, corriger divers bugs.
  • Ajoutez une contrainte VRP au résolveur SAT, qui est associée au résolveur LP.
  • Modifiez l'observateur de solution dans le résolveur SAT pour utiliser CpSolverResponse comme paramètre.
  • Amélioration de l'utilisation de Glop dans le résolveur SAT.
  • Accélérer la connexion SAT-LP.
  • Ajoutez une contrainte de réservoir au format protobuf cp_model SAT.

SAT/Python

Exemples

  • Réécrivez rcpsp_parser afin d'utiliser le format ProtoBuf pour stocker le problème.
  • Amélioration de l'analyseur RCPSP

octobre 2017

Sortie de la version 6.5

Nous avons lancé la version 6.5 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Variation des plates-formes

  • Le module pypi py3-ortools a été fusionné avec le module ortools. Il ne comporte désormais qu'un seul module: "ortools".
  • Le principal format de ces modules Python est désormais la roue. Pour installer OR-Tools pour Python à partir de pypi, exécutez simplement pip install ortools. Une version récente de pip doit être installée (version 9.0.1 ou ultérieure). Cela devrait permettre d'extraire la dernière version (v6.5).

Bug fixed

Le fichier JAR Protoblé est désormais correctement compilé avec les classes compilées.

Nouveaux exemples

  • D'autres exemples F# ont été ajoutés au répertoire "examples/fsharp". (Merci encore à Matthew Moore.)
  • Des exemples MIP Java ont également été fournis (Thanks Darian).

septembre 2017

Sortie de la version 6.4

Nous avons lancé la version 6.4 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Variation des plates-formes

  • Les modules Pypi sur les plates-formes Linux sont désormais fournis sous forme de fichiers roue à l'aide de la balise manylinux1. Merci à Federico Ficarelli. Avec cette modification, nous avons effectué le suivi des modules par Linux introduits dans la version de juillet 2017.

Nouvelles fonctionnalités

  • Amélioration de la méthode de scaling utilisée dans GLOP.
  • Correction de l'encapsulation des évaluateurs dans la bibliothèque de routage C#. Merci à DevNamedZed.
  • Amélioration des performances du prédé à zinc pour les grands modèles.
  • Utilisez par défaut le SAT pour flatzinc.
  • Amélioration des performances de l'approche basée sur les cœurs pour le solutionneur sat.
  • Correction d'un bug dans l'algorithme d'attribution linéaire qui échouait de manière incorrecte.
  • Ajout d'exemples F# dans ortools/examples/fsharp.
  • Suppression de la vérification des pénalités positives dans la bibliothèque de routage.

Août 2017

Sortie de la version 6.3

Nous avons lancé la version 6.3 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Nouveaux fichiers de téléchargement

Les fichiers Python wheel pour Linux peuvent désormais être téléchargés sur la page des versions OR-Tools, ainsi que les dernières versions de tous les téléchargements.

Solvant minizinc

Cette version contient le code sat et flatzinc final envoyé pour le défi Minizinc 2017.

Juillet 2017

Sortie de la version 6.2

Nous avons lancé la version 6.2 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Variation des plates-formes

  • Nous prenons désormais en charge plusieurs distributions binaires Linux (Ubuntu 14.04, 16.04, 17.04, CentOS 7, Debian 9).
  • Les modules Pypi sur les plates-formes Linux incluent désormais un tag décrivant la distribution (Ubuntu-14.04, Ubuntu-16.04, Ubuntu-17.04, centos-7, debian-9).

Nouvelles fonctionnalités

Docker permet désormais de créer des artefacts Linux. Accédez à or-tools/tools/docker et examinez Makefile pour afficher les cibles possibles (make archive, make pypi et make pypi3).

Ces commandes créeront un sous-répertoire export et y ajouteront des artefacts binaires.

Juin 2017

Sortie de la version 6.1

Nous avons lancé la version 6.1 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Variation des plates-formes

  • Visual Studio 2017 est compatible, mais pas Visual Studio 2013.
  • Les versions 10.9 et ultérieures de macOS sont compatibles.

Nouvelles fonctionnalités

Nous avons ajouté un nouveau format de tampon de protocole pour notre résolveur CP-SAT. Consultez ortools/sat/cp_model.proto pour définir votre modèle et ortools/sat/cp_model_solver.h pour résoudre votre problème.

Correction de bugs

Problème n° 420: nous avons corrigé l'attribut __version__ manquant dans les modules pypi Python sur toutes les plates-formes.

Mai 2017

Sortie de la version 6.0

Nous avons lancé la version 6.0 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Nouvelle structure de répertoires en C++

Nous avons modifié la structure de source/inclusion des outils OR lors de l'utilisation de C++. L'objectif est de fournir une meilleure encapsulation des fichiers d'inclusion C++. Il présente également l'avantage d'aligner les structures de répertoires C++ et Python.

  • src/ est maintenant appelé ortools/.
  • Le préfixe ortools a été ajouté à toutes les commandes #include dans les fichiers C++. #include "constraint/constraint_solver.h" est désormais #include "ortools/constraint/constraint_solver.h".

Nouvelles fonctionnalités

  • Prise en charge de Bazel. Vous pouvez désormais créer des outils OU avec bazel, l'outil de création de Google. Il fonctionne sous Linux et Mac OS X. Après avoir téléchargé Bazel version 0.4.5 ou ultérieure, remplacez le répertoire par "or-tools" et créez les exemples : bazel build examples/cpp/....

Routage

Nous avons intégré une prise en charge des pauses (par exemple, les temps d'arrêt d'un véhicule en raison d'un déjeuner par les conducteurs) dans la bibliothèque d'itinéraires. Cette fonctionnalité est illustrée dans l'exemple cvrptw_with_breaks.cc.

Compatibilité SCIP

Le wrapper de solution linéaire est désormais compatible avec SCIP 4.0. Vous devez d'abord créer SCIP, puis indiquer aux outils que vous allez l'utiliser. Pour obtenir des instructions, cliquez ici.

Compatibilité GLPK

Nous avons également changé la façon de créer avec GLPK. reportez-vous à cet article.

Nettoyage

  • Nous avons supprimé toute utilisation de hash_map et hash_set dans le codebase C++, car ils sont obsolètes. Elles ont été remplacées par unordered_map et unordered_set dans la STL.
  • Nettoyage des fichiers de création C# avec l'aimable autorisation de Michael Powell.

Janvier 2017

Sortie de la version 5.1

Nous avons lancé la version 5.1 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Nouvelles fonctionnalités

Installation

Routage

Implémentation d'un algorithme permettant de calculer la limite inférieure Held-Karp pour les problèmes symétriques du commercial touristique. Cela vous permet de calculer la limite supérieure de l'écart entre le coût d'une solution potentiellement non optimale et le coût de la solution optimale.

  • Ajout d'une nouvelle méthode à la bibliothèque de calcul d'itinéraire des véhicules, RoutingModel::SetBreakIntervalsOfVehicle, qui vous permet d'ajouter des intervalles de break, c'est-à-dire des périodes pendant lesquelles un véhicule ne peut effectuer aucune tâche (se déplacer ou se rendre sur une intersection, par exemple). Pour obtenir un exemple utilisant cette option, consultez cvrptw_with_breaks.cc.

Planification

Solutionneur sat

  • La contrainte cumulative du résolveur SAT accepte désormais des intervalles facultatifs, créés avec la méthode NewOptionalInterval. Pour obtenir un exemple, reportez-vous à https://github.com/google/or-tools/blob/master/examples/cpp/rcpsp_sat.cc.
  • Vous pouvez maintenant résoudre un problème Max-SAT (maximum satisfiability_) en spécifiant l'objectif sous la forme d'une somme pondérée de littéraux. Il n'est plus nécessaire de créer une variable entière intermédiaire.

Amélioration des performances

  • Solutionneur SAT : amélioration des performances du résolveur Sat, en particulier concernant la contrainte cumulative.
  • Résolution glob : amélioration de la robustesse numérique du résolveur glob, qui propose désormais des solutions encore plus précises aux problèmes numériques difficiles.
  • Solvant à base de zinc
  • Amélioration significative des performances du backend Sat pour l'interpréteur flatzinc.
  • Simplification de l'interface flatzinc C#. Pour obtenir un exemple de la nouvelle interface, accédez à https://github.com/google/or-tools/blob/master/examples/csharp/csfz.cs.

Correction de bugs

  • L'utilisation de l'heuristique PathCheapestArc sur les modèles de routage avec un seul véhicule et des contraintes latérales peut parfois entraîner l'exécution du résolveur sur une durée excessive. Ce problème a été résolu en tenant bien compte des contraintes secondaires.
  • En Java, le résolveur d'itinéraires plantait parfois lors de la résolution de problèmes de calcul d'itinéraire d'un véhicule. Ce problème a été corrigé dans la dernière version.

Novembre 2016

Sortie de la version 5.0

Nous avons lancé la version 5.0 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Exemples en cours d'exécution

  • Introduction de cibles spécifiques aux langages qui facilitent la compilation et l'exécution de vos programmes, ainsi que des exemples fournis avec les outils OR.

Sam

FlatZinc

  • Implémentation d'un résolveur SAT pour les problèmes liés à FlatZinc.

Solutionneur de contraintes

Routage

  • Implémentation de AddAtSolutionCallback, qui est un rappel appelé chaque fois qu'une solution est trouvée lors de la recherche.
  • Suppression des constructeurs sans dépôt RoutingModel. Spécifier au moins un dépôt dans le modèle de routage est désormais obligatoire.

Septembre 2016

Sortie de la version 4.4

Nous avons lancé la version 4.4 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Sam

  • API de planification étendue et exemples modifiés (pondéré_tardiness_sat et jobshop_sat) pour l'utiliser

Graphique

  • Ajout de traits d'itérateur aux classes Graph.

Distribution des outils OU

  • Le package Nuget est à nouveau pris en charge.

août 2016

Sortie de la version 4.3

Nous avons lancé la version 4.3 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Solutionneur de contraintes

  • Implémentation de la méthode NotBetween pour contraindre une variable à se trouver en dehors d'un intervalle donné.

Routage

  • Ajout d'une analyse du modèle pour vérifier les contraintes NotMember existantes, comme indiqué dans cet exemple, et les utiliser dans les filtres de recherche locaux.
  • Ajout du profilage de la recherche locale.
  • Correction des déplacements locaux.

Solutionneur linéaire

  • Correction de la création de rapports d'état SCIP.

Sam

  • Mise en œuvre de la méthode SolveWithPresolve pour simplifier l'utilisation du prérésolveur SAT.
  • Utilitaires de recherche regroupés dans src/sat/util.h|cc.
  • Implémentation des contraintes de planification SMT (Lazy Clause Generation) : voir jobshop_sat.cc et weighted_tardiness_sat.cc

Glope

  • Amélioration des performances en exploitant la parcimonie dans plusieurs étapes de calcul.

Flatzinc

  • Correction de bugs détectés par le défi minizinc.

Lp_data

  • Simplification continue des modèles dans les itérateurs

Distribution des outils OU

  • Les assemblys C# sont désormais des noms forts par défaut.
  • Mise à niveau vers Protobuf 3.0.0.
  • Ajout d'un script Python pour vérifier les dépendances de l'archive OR-Tools.

Juillet 2016

Sortie de la version 4.2

Nous avons lancé la version 4.2 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Outil de résolution de contraintes (routage)

  • Une disjonction peut désormais être définie avec une cardinalité, qui correspond au nombre maximal de nœuds pouvant être actifs dans cette disjonction. Par exemple, si vous ajoutez une disjonction composée de n nœuds et d'une cardinalité de k, k nœuds parmi les n nœuds peuvent être actifs. Pour ce faire, vous pouvez utiliser la nouvelle définition de AddDisjunction.
  • Ajout de la prise en charge des disjonctions multiples par nœud. Par exemple, vous pouvez maintenant ajouter un nœud, N1, à de nombreuses disjonctions (D1..Dm). Cela augmente ses chances d'être actif dans l'un d'entre eux. Introduction d'un algorithme de recherche de routage plus rapide pour les problèmes liés aux fenêtres temporelles disjointes.
  • Ajout de paramètres du résolveur de contraintes pour le routage des paramètres du modèle et de log_search pour le routage des paramètres de recherche.
  • L'algorithme de recherche locale résout plus rapidement les problèmes avec des fenêtres temporelles disjointes. Pour en savoir plus, consultez l'exemple cvrp_disjoint_tw.cc.

Glop (optimisation linéaire)

  • Introduction d'un algorithme simplex plus rapide.

Distribution des outils OU

  • Une archive par plate-forme, au lieu d'archives individuelles pour chaque C++, Java et .Net. Les archives Python sont toujours hébergées sur pypi.
  • Sur pypi, nous sommes passés aux modules wheel (.whl) sous Mac OS X et Windows. Introduction d'un schéma de numérotation MAJOR.MINOR. Ces numéros correspondent aux noms des archives, à la version stockée dans les bibliothèques partagées Mac OS X, aux modules Python et aux assemblages .NET. La première version que nous lançons avec ce schéma est la v4.2.

Juin 2016

Sortie de la version v2016-06

Nous avons publié la version v2016-06 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Solutionneur de contraintes

  • Suppression de la plupart des instances de rappels (src/base/callback.h) de la bibliothèque CP.
  • Ajout de NotMemberCt (la variable ne peut pas appartenir à un ensemble d'intervalles).

Bibliothèque de routage

  • MODIFICATION INCOMPATIBLE: pour spécifier la capacité des véhicules dans AddDimensionWithVehicleCapacity, vous devez désormais transmettre un tableau (un vecteur en c++) au lieu d'un rappel.

GLOP

  • Modification de la représentation interne de la matrice creuse.
  • Amélioration des performances

Graphique

  • Réécriture des algorithmes de Dijkstra et de Bellman-Ford pour remplacer les rappels par std::function (C++).
  • Modification de l'API des différentes implémentations de graphiques lors de l'itération sur des arcs et des nœuds.

Sam

  • Supprimez la méthode de base inutilisée (nœuds de résolution).
  • Ajout de Drrat Writer pour vérifier les preuves du caractère insatisfaisant.
  • Ajouter un préprocesseur.

BDP

  • Ajouter des quartiers.

Exemples

  • c++: suppression du lecteur de ligne de fichier dans les exemples
  • Données: ajouter des problèmes de planification sur une seule machine.

Documentation

Avril 2016

Sortie de la version v2016-04

Nous avons publié la version v2016-04 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Dépendances mises à jour

Décembre 2015

Sortie de la version v2015-12

Nous avons lancé la version v2015-12 de OR-Tools. Pour mettre à jour votre version, consultez la section appropriée de la section Installation des outils OR.

Solutionneur de contraintes

  • Incompatibilité au niveau de Large Neighborhood Search dans le résolveur de CP (consultez examples/cpp/ls_api.cc, examples/python/pyls_api.py, examples/csharp/csls_api.cs et examples/com/google/ortools/sample/LsApi.java pour voir la nouvelle API).
  • Nettoyer l'encapsulation de Python. Prise en charge de la décision personnalisée dans l'outil de résolution des problèmes de CP (consultez examples/test/test_cp_api.py pour voir l'API en action).
  • Améliorations diverses et correction de plusieurs bugs.

Septembre 2015

Annonce de la première version sur GitHub.

Les fichiers y seront désormais stockés.

Flatzinc

  • Ajout d'archives binaires pour l'interpréteur flatzinc (voir www.minizinc.org).
  • Contient quelques corrections de la version utilisée dans le défi.