Notas de la versión de las herramientas OR

En esta página, se enumeran los cambios realizados en las herramientas OR, lo que incluye funciones nuevas, correcciones de errores y mejoras en el código y los procedimientos de instalación.

Si tienes problemas para instalar las herramientas OR, consulta la sección Solución de problemas de las instrucciones de instalación de las herramientas OR. Si tu problema no aparece allí, verifica los problemas en GitHub o no dudes en abrir uno nuevo, y con gusto te ayudaremos.

A continuación, se incluyen las notas de la versión de las herramientas del operador OR, que comienzan con la versión más reciente.

Marzo de 2024

Anuncio del lanzamiento de la versión 9.9 de OR-Tools

Lanzamos OR-Tools v9.9. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas OR.

Puedes encontrar la nota de la versión en GitHub.

Noviembre de 2023

Anuncio del lanzamiento de la versión 9.8 de las herramientas OR

Lanzamos OR-Tools v9.8. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas OR.

Cambios en la plataforma

  • Agrega Python 3.12.
  • Cómo agregar compatibilidad con Ubuntu 23.10

Servicio de resolución lineal

  • Puerto ModelBuilder a .NET.
  • Se cambió el nombre de LogCallback a MbLogCallback para evitar la colisión con SAT LogCallback.
  • Extiende la API de ModelBuilder:
    • Agrega restricciones de indicadores.
    • Agrega compatibilidad con sugerencias.
    • Agrega clonación de modelos.

Opción matemática

  • Revisión profunda.

Enrutamiento

  • Agrega el estado ROUTING_OPTIMAL.
  • Se hizo que RoutingModel no se pueda copiar ni mover.
  • Se corrigieron algunos bucles infinitos en los operadores de búsqueda local.
  • Agrega un struct interno PickupDeliveryPosition.
  • Se agregaron los métodos IsPickup() y IsDelivery().

SÁB

  • Reduce el uso de memoria para modelos grandes.
  • Se mejoró la programación de la búsqueda.
  • agrega packing_precedences_lns.
  • optimizar y corregir el salto de viabilidad.
  • optimizar el registro de resolución lineal y mejor resolución.
  • Se mejoró la resolución para int_abs, int_mod, int_prod y lin_max.
  • Mejora la compatibilidad con Panda
  • Pocos correcciones de errores.

Registro de cambios de GitHub

Agosto de 2023

Anuncio del lanzamiento de la versión 9.7 de OR-Tools

Lanzamos OR-Tools v9.7. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas OR.

Cambios en la plataforma

  • Descartar Centos-8 (EOL).
  • Deja Debian 10.
  • Soltar el sombrero [33, 36] (EOL)
  • Baja Ubuntu 18.04 LTS (EOL).
  • Descartar Python 3.7 (EOL).
  • Inhabilita la compatibilidad de netcore3.1 en CMake (EOL).

Python del compilador de modelos

  • Permite el uso de DataFrames y series de Pandas para crear variables.
  • Completa la información de escritura

PDLP

  • varias actualizaciones.

CP-SAT

  • Se implementaron mejoras en el rendimiento. (feasibility_jump, lin_max)
  • Mejora la administración de cortes
  • Se agregó un nuevo trabajador objetivo_s tener_search dedicado a mejorar el límite inferior del objetivo (cuando se lo minimiza).
  • Escribir anotaciones para cp_model.py de Python
  • Compatibilidad parcial experimental para Pandas en cp_model.py
  • Trabajadores basados en incumplimientos de la búsqueda local experimental:
    • habilitada con el parámetro num_violation_ls:xxx
    • Optimizado para un modelo lineal (linear, bool_or, bool_and, at_most_one, exactly_one)
    • funciona correctamente con lin_max, product, division
    • admite no_superlap, cumulative, circuito, routes
    • inhabilitado con no_overlap_2d
    • Cantidad recomendada de trabajadores ls: num_workers -> num_violation_ls: (8, 1), (16, 2) (24, 3), (32, 4)

Registro de cambios de GitHub

Marzo de 2023

Anuncio del lanzamiento de las herramientas OR v9.6

Lanzamos OR-Tools v9.6. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas OR.

Cambios en la plataforma

  • Se agregó compatibilidad con Fedora 37, 38.
  • Drop Python 3.6 (no compatible con protobuf).
  • Descartar Python 3.7 en macOS (no compatible con scipy).
  • Se agregó compatibilidad con net7.0 en CMake (usa -DUSE_DOTNET_7=ON).
  • Suelta netcore3.1 en paquetes nuget .org

Dependencias

  • SCIP v801 -> v803 (nota: ahora SCIP usa una licencia compatible con OSI)
  • ábseil 20220623.1 -> 20230105.0
  • Protobuf v21.5 -> v21.12
  • SWIG 4.1.1
  • JNA de Java 5.11.0 -> 5.12.1

Bazel

  • Agrega compatibilidad con pybind11.
  • Se agregó compatibilidad con wrapper de Java.

Resolutores

  • PDLP: dd python wrapper
  • CP-SAT: Mejoras en el rendimiento
  • GLOP: Ajusta la resolución.
  • ModelBuilder: Python: mejora la compatibilidad con NumPy.
  • Enrutamiento: Mejoras en el rendimiento (búsqueda local)

Problemas conocidos:

  • CP-SAT: Si se ignora el subencargado de pseudo_costs, se muestran parámetros no válidos (consulta #3706).

Noviembre de 2022

Anuncio del lanzamiento de la versión 9.5 de las herramientas OR

Lanzamos OR-Tools v9.5. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas OR.

Cambios en la plataforma

  • Agrega compatibilidad con Debian Sid.
  • Agrega compatibilidad con Fedora 35, 36
  • Agrega compatibilidad con Ubuntu 22.10.
  • Lanzar Python 3.6 en macOS
  • Agrega compatibilidad con Python 3.11.

Actualización de dependencias

  • Protobuf v19.4 -> v21.5.
  • Resolución de SCIP v800 -> v801.

CP-SAT

  • Mejoras para resolver problemas: max(array), restricciones booleanas, restricciones lineales.
  • La búsqueda intercalada debe ser determinística en paralelo.
  • Cortes lineales: Cortes de cortes int_prod y cuadrado de limpieza; reescritura de la canalización de cortes
  • Modelo de entrada de huella digital y solución (visible en el registro).
  • Se están programando las mejoras.
  • El conjunto habitual de correcciones de errores (fallas durante la resolución de problemas, fallas en los cortes, soluciones inviables, modelos inviables en LNS)

GLOP

  • Acelera mediante la reescritura de álgebra lineal y la regla de selección de eje.

Servicio de resolución lineal

  • Se agregó knapsack_interface.cc,
  • Traslada la API de model_builder al directorio linear_solver (encabezados y muestras).
  • Agrega compatibilidad con Gurobi 10.

Enrutamiento

  • Liberar pocos analizadores para varios desafíos de enrutamiento

Agosto de 2022

Anuncio del lanzamiento de la versión 9.4 de las herramientas OR

Lanzamos OR-Tools v9.4. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas OR.

Plataformas

  • Agrega compatibilidad con Debian-10 (consulta #3029).
  • Agrega compatibilidad con Ubuntu 22.04 LTS (consulta #3276). Nota: No tendrá compatibilidad con .NET 3.1 (consulta dotnet/core#7038).
  • Se quitó la compatibilidad con Ubuntu 21.10.

Varios

  • Divide el archivo por idiomas y agrega la configuración de CMake a la de C++ (#3200).

Graph

Dividir ortools.graph.pywrapgraph en:

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

Esto permite usar NumPy para agilizar la configuración de los problemas.

CP-SAT

Algunas mejoras en lo siguiente:

  • programación (propagación, cortes, límites inferiores).
  • MaxSAT (presolver, heurística basada en núcleo).
  • Rendimiento del MIP (presolver, cortes).

Marzo de 2022

Anuncio del lanzamiento de la versión 9.3 de las herramientas OR

Lanzamos OR-Tools v9.3. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas OR.

Cambios en la plataforma

  • Quita la compatibilidad con Debian-10.
  • Deja de ser compatible con Ubuntu-16.04.
  • Descartar .NET Framework 4.5.2.

Actualización de dependencias

  • Agrega Eigen 3.4.0.
  • Agrega Google re2 2021-11-01.
  • Protobuf 3.19.1 -> 3.19.4.
  • SCIP 7.0.1 -> v800.

Python

  • Agrega pybind11.

Funciones

  • Se agregó PDLP como experimental.
  • Se agregó MathOpt como experimental.

CP-SAT

  • Se cambió el nombre de algunas API para mantener la coherencia, p. ej., LinearExpr.ScalProd. -> LinearExpr.WeightedSum.
  • Se agregaron los métodos AddAtLeastOne/AddAtMostOne/AddExactlyOne.
  • Agrega AddMultiplicationConstraint(z, x, y) en todos los idiomas.
  • Agrega AddMultipleCircuit() en todos los idiomas.

C++

  • Respuesta explícita IntVar(BoolVar).
  • Se quitó LinearExpr::Add* y se reemplazó por un operador, p.ej., LinearExpr +=.
  • Agrega operadores aritméticos a la expresión lineal.
  • Se quitó LinearExpr::BooleanSum/BooleanScalProd, usa Sum/WeightedSum.
  • Agrega CpModelBuilder::FixVariable(), que reemplaza el dominio de la variable por un solo valor.

Java

  • Vuelve a escribir LinearExpr y agrega una clase de compilador incremental: LinearExpr.newBuilder().add(x).addSum(<array of variables>).build().
  • Sigue la API de C++: Circuit, MultipleCircuit, Cumulative, Reservoir, AllowedAssignment y ForbiddenAssignment ahora muestran una clase especializada con una API incremental para agregar variables, términos y demandas nuevos...

C

  • Documenta todos los métodos.
  • Sigue la API de C++: Circuit, MultipleCircuit, Cumulative, Reservoir, AllowedAssignment y ForbiddenAssignment ahora muestran una clase especializada con una API incremental para agregar variables, términos y demandas nuevos...
  • Agrega la clase LinearExprBuilder para compilar expresiones de forma incremental.

Sistema de compilación

CMake

  • Se requiere al menos CMake >= 3.18.

Marca

  • Ahora, usa la compilación basada en CMake internamente.

Diciembre de 2021

Anuncio del lanzamiento de la versión 9.2 de las herramientas OR

Lanzamos OR-Tools v9.2. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas OR.

Cambios en la plataforma

  • Agrega compatibilidad con Ubuntu 21:10 (última versión progresiva).

Actualización de dependencias

  • Actualización de .NET TFM desde net5.0 a net6.0 (se necesita el SDK de .NET 6.0 LTS y el SDK .NET 3.1 LTS).
  • abseil-cpp 20210324.2 -> 20211102.0.
  • Protobuf 3.18.0 -> 3.19.1.
  • Googletest 1.10.0 a 1.11.0.
  • Python: agrega NumPy >= 1.13.3.
  • En macOS, compila Coin-OR en -O1 para evitar fallas en los ejecutores.

Enrutamiento

  • Mejoras en los filtros
  • Mejorar la heurística de la primera solución
  • Mejore las ubicaciones de las pausas temporales.

CP-SAT

Cambios rotundos

  • El búfer de protocolo subyacente no es compatible con versiones anteriores. Cualquier búfer de protocolo almacenado deberá volver a generarse con las APIs de compilador actualizadas (en C++, Python, Java y .NET).
  • En particular, el protobuf de intervalo estaba limpio, ya que quitamos los campos antiguos (inicio, tamaño y fin) y cambiamos el nombre de los nuevos (con _view) para usar el nombre de los campos que se quitaron.

Funciones nuevas

  • Las restricciones all_different, reservoir, modulo, multiplication y division aceptan expresiones afines (a * var + b) en todos los lugares en los que requirieran variables de número entero.
  • El objetivo acepta coeficientes de punto flotante (consulta la clase DoubleLinearExpr en C++/Java/.NET. Consulta el ejemplo de knapsack_2d_sat.py en Python).
  • La restricción no_overlap_2d admite intervalos opcionales.
  • La API de C++ implementa operadores + y * para compilar expresiones.

Mejoras

  • Se mejoró el código de resolución de problemas.
  • Un verificador de modelos más estricto.
  • Restricción del embalse para rehacer.
  • Se agregaron cortes enérgicos a la restricción no_overlap_2d.
  • Se mejoró la relajación lineal de las restricciones de codificación (literal implies var == value).

Métodos obsoletos y quitados

  • BooleanSum y BooleanScalProd de C++ dejaron de estar disponibles. Solo usa Sum y ScalProd.
  • Se quitaron AddLinMinEquality y AddLinMaxEquality de C++. Solo usa AddMinEquality y AddMaxEquality.

Incompatibilidades futuras

  • En algún momento, volveremos a escribir la capa de modelado de Java para que esté más cerca de la capa de C++.
  • En la capa de modelado de C++, haremos que el controlador IntVar(BoolVar var) sea explícito.
  • Estamos contemplando la posibilidad de que la API de Python cumpla con la PEP 8 (con nombres de snake_case). Si esto sucede, proporcionaremos un archivo sed para portar el código.

Sistema de compilación

Bazel

  • Corrige la compilación de Windows.

CMake

  • Agrega la opción FETCH_PYTHON_DEPS (el valor predeterminado es ON).
  • Se agregó compatibilidad opcional con el solucionador de GPLK (valor predeterminado: -DUSE_GLPK=OFF).

Python

  • Admite números enteros numpy en la mayor parte de la API de CP-SAT.
  • Se corrigió __version__ faltante.

Septiembre de 2021

Anuncio del lanzamiento de la versión 9.1 de las herramientas OR

Lanzamos OR-Tools v9.1. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas OR.

Cambios en la plataforma

  • Python: usa la imagen manylinux2014 (consulta PEP 599).
  • Python: Agrega compatibilidad con aarch64 Linux usando la imagen manylinux2014_aarch64.
  • .NET: agrega compatibilidad con .NET 5.0.

Actualización de dependencias

  • abseil-cpp 20210324.1 -> 20210324.2.
  • Protobuf 3.15.8 -> 3.18.0.
  • SCIP 7.0.1 -> principal.
  • Googletest 1.8.0 -> 1.10.0
  • Python: Uso de warning en cp_model.py (consulta #2530).
  • python: absl-py 0.11 -> 0.13.

CMake

  • Modifica la versión mínima requerida de la versión 3.14 a la 3.15 (consulta #2528).
  • Python: versión mínima requerida de la actualización de la versión 3.14 a la 3.18 (consulta #2774).

Marca

La compilación basada en Make dejó de estar disponible. Migra a CMake o Bazel para compilar desde la fuente.

Java

  • Mejora la solidez del cargador de bibliotecas nativas (consulta #2742).
  • Se corrigió la falla del recolector de elementos no utilizados de JVM cuando se eliminaba el modelo de enrutamiento o el solucionador de restricciones (consulta #2091) (consulta #2466).
  • Se corrigió la falla de devolución de llamada del registro CP-SAT cuando se usan varios trabajadores (consulta #2775).

CP-SAT

  • Mejora la solidez del código LNS (consulta #2525).
  • Se mejoró el código de programación: se agregaron nuevos métodos de fábrica para crear intervalos de tamaño fijo, nuevas heurísticas de búsqueda, mejores presolve y nuevos cortes lineales.
  • Mejorar el código de enrutamiento: nuevo LNS dedicado
  • Mejorar el verificador de modelos Ahora es más pedante, en especial, desbordamientos potenciales de WRT.
  • Se mejoró el código MIP: Mejor prioridad de resolución y varias mejoras en la relajación lineal de los modelos MIP y CP.
  • Mejorar la diversidad en las búsquedas. Cuando uses más de 12 trabajadores, agrega trabajadores dedicados a mejorar el límite inferior del objetivo.
  • Cambia al código de paralelismo: De forma predeterminada, el solucionador ahora usará todos los núcleos disponibles. Usa num_search_parameters para especificar el nivel de paralelismo.
  • SearchAllSolutions y SolveWithSolutionCallback dejaron de estar disponibles.
  • API de Python: verificaciones más pedantes cuando se usa var == ... o var != ... fuera de una llamada a model.Add()

Abril de 2021

Anuncio del lanzamiento de la versión 9.0 de las herramientas OR

Lanzamos OR-Tools v9.0. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas OR.

Actualizaciones de dependencias

Java

Correcciones de errores

  • Se mejoró la capacidad de varios subprocesos cuando se usa el solucionador de problemas CP-SAT (consulta #1588).
  • Se corrigió la compatibilidad del wrapper de Python de std::vector&ltstd::string&gt (consulta #2453).
  • Se repitió la compatibilidad con CPLEX (consulta #2470).

Cambio rotundo conocido

  • Agrega acceso al registrador en Python, Java y .NET (consulta #2245).
  • Reemplaza todos los tipos personalizados de Google por los que se proporcionan en cstdint.

CP-SAT

  • Los métodos SearchForAllSolutions(), SearchAllSolutions() y SolveWithSolutionCallback() dejaron de estar disponibles. En su lugar, usa Solve().
  • Mejora la compatibilidad de los operadores estándar de Python. Esto puede romper el código incorrecto existente.

Marzo de 2021

Anuncio del lanzamiento de las herramientas OR v8.2

Lanzamos OR-Tools v8.2. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas OR.

Actualizaciones de dependencias

  • Abseil-cpp 20200923.2 se actualizó a 20200923.3 LTS.
  • Protobuf 3.14.0 se actualizó a 3.15.3.

Enrutamiento

  • Se agregaron RoutingModel.RegisterTransitMatrix() y RoutingModel.RegisterUnaryTransitVector().
  • Cambia el resultado de RoutingModel.AddVectorDimension() y RoutingModel.AddMatrixDimension() a std::pair&ltint, bool&gt cuyo int es el ID del evaluador de transporte público.

Diciembre de 2020

Anuncio del lanzamiento de las herramientas OR v8.1

Ya lanzamos OR-Tools v8.1. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas OR.

Actualizaciones de dependencias

  • Abseil-cpp 20200923 actualizado a 20200923.2 LTS
  • Protobuf 3.13.0 se actualizó a 3.14.
  • Cómo agregar compatibilidad con Gurobi 9.1.0
  • Eliminar dependencia de GLog (se reemplazó por una implementación personalizada según las marcas abseil-cpp)
  • Dejar la dependencia de GFlag (reemplazada por el componente de marcas abseil-cpp)

Correcciones de errores

  • Se corrigió el recuento doble de la licencia flotante de Gurobi (consulta #2227).
  • Corrige la compilación de Windows (consulta #2200).

Octubre de 2020

Anuncio del lanzamiento de las herramientas OR v8.0

Ya lanzamos OR-Tools v8.0. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas OR.

Cambios en la plataforma

  • Se agregó compatibilidad con Python 3.9 (#2187).
  • Se interrumpió la compatibilidad con Python 3.5 (#2186) <!-- Waiting Microsoft dotnet-sdk support, could be generate after the release is out...
    • Se agregó compatibilidad con Ubuntu 20.10 (#2188) -->
  • Se interrumpió la compatibilidad con Ubuntu 16.04 LTS (#2188).
  • Se interrumpió la compatibilidad con Ubuntu 19.10 (#2188).

Actualizaciones de dependencias

  • Abseil-cpp 20200225.2 se actualizó a 20200923 LTS
  • Protobuf 3.12.2 se actualizó a 3.13.0.

Cambio rotundo conocido

  • Ahora, el enrutamiento y el código fuente CP-SAT usan algunas funciones de C++17. Advertencia: Si proporcionas tu propia versión de abseil-cpp, verifica que también esté compilada en C++17.
  • Se cambió la firma MPSolver::CreateSolver. Se descartó el argumento de nombre del modelo.

CMake

  • Se corrigió la inhabilitación de la compatibilidad con SCIP cuando se usa -DUSE_SCIP=OFF (consulta #2129).
  • Integra muestras y ejemplos al sistema de compilación de CMake. Nota: Se pueden inhabilitar con -DBUILD_SAMPLES=OFF y -DBUILD_EXAMPLES=OFF. Nota: Se puede inhabilitar para un idioma específico mediante -DBUILD_<LANG>_SAMPLES=OFF o -DBUILD_<LANG>_EXAMPLES=OFF.
    • Con <LANG> entre:
    • CXX,
    • PYTHON,
    • JAVA y
    • DOTNET.

Marca

  • Requiere Make >= 4.3 (uso de la función de evaluación Make).
  • Requerir CMake >= 3.14 (uso de la opción --verbose de CMake).
  • Se agregó la opción para inhabilitar la compatibilidad con SCIP con -DUSE_SCIP=OFF (consulta #2134).
  • Se agregó una opción para inhabilitar la compatibilidad con CLP y CBC mediante -DUSE_COINOR=OFF

Java

  • Las herramientas OR ahora generan paquetes de Maven (consulta #202).

Correcciones de errores

  • Se corrigió la compilación de C++ y Python en FreeBSD (consulta #2126).
  • Corrige la compilación de la depuración en Windows (consulta #2077).
  • Se corrigió la falla permanente en paralelo en CP-SAT en Windows (consulta #2001 y #2019).

Julio de 2020

Anuncio del lanzamiento de OR-Tools v7.8

Lanzamos OR-Tools v7.8. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas OR.

Actualizaciones de dependencias

  • Gurobi 9.0.2 ahora está preintegrado en objetos binarios compilados previamente. Buscará la biblioteca compartida gurobi 90 en la ruta de instalación predeterminada de los instaladores de Gurobi en MAC OS X y Windows, o en el directorio GUROBI_HOME.
  • SCIP 7.0.1 ahora está integrado en objetos binarios compilados previamente. Asegúrate de cumplir con la licencia de SCIP antes de usarla.
  • Se agregó compatibilidad con la resolución opcional Xpress 8.9.0.

Servicio de resolución lineal

  • Se agregó un método LinearSolver::CreateSolver() estático para simplificar la verificación de la compatibilidad de los backends de resolución lineal integrados. Funciona en todos los idiomas.

Correcciones de errores

  • Se corrigió CMake con la compilación en FreeBSD.
  • Se corrigió la ordenación de CP-SAT en la generación de cortes acumulativos.
  • Se corrigió la fuga de memoria del solucionador de problemas lineal en el wrapper .NET.

Junio de 2020

Anuncio del lanzamiento de OR-Tools v7.7

Lanzamos OR-Tools v7.7. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas OR.

Actualizaciones de dependencias

  • Se actualizó Abseil-cpp b832dce a c51510d (LTS 20200225.2).
  • Protobuf 3.11.4 se actualizó a 3.12.2.

Nuevas funciones y mejoras

  • El solucionador de problemas CP-SAT ahora muestra Optimal en lugar de Feasible en un modelo de satisfacción (es decir, sin objetivo).
  • Se agregó la heurística de la bomba de viabilidad de la comunidad del MIP.

Correcciones de errores

Se corrigió la falla de varios subprocesos de CP-SAT (consulta #2005).

Abril de 2020

Anuncio del lanzamiento de las herramientas OR v7.6

Lanzamos OR-Tools v7.6. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas OR.

Nuevas funciones del CP-SAT

Agregamos las siguientes funciones nuevas al solucionador de problemas CP-SAT:

  • Se mejoró la administración de los aviones de corte para los LP.
  • Herramientas de depuración.

Actualizaciones de dependencias

Se actualizó Abseil-cpp 8ba96a8 a b832dce (LTS 20200225).

Correcciones de errores

  • Se corrigió el error CP-SAT UNSAT en presolve (consulta #1908).
  • Se corrigió la URL de swigwin.exe.
  • Se corrigió la administración de mapas de tipos SWIG para Java y .NET.

Enero de 2020

Anuncio del lanzamiento de OR-Tools v7.5

Lanzamos OR-Tools v7.5. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas OR.

Cambios en la plataforma

  • Se agregó compatibilidad con Python 3.8 (#1719).
  • Se dio de baja la compilación de compatibilidad de fuentes en Visual Studio 2017 (#1852).
  • Se actualizó la compatibilidad de Centos 7 a Centos 8 (#1827).

Actualización de dependencia

Correcciones de errores

Se corrigieron los siguientes problemas en las herramientas OR v7.5 (para obtener una lista completa, consulta Milestone v7.5).

En particular, considera lo siguiente:

  • Se corrigió la carga del ensamblaje. Consulta el #1421.
  • Se expusieron los métodos GetStartIndex() y GetEndIndex() de RouteIndexManager (#1843).
  • Se corrigió SWIG para quitar métodos dañados (#1838, #1276).

octubre de 2019

Anuncio del lanzamiento de las herramientas OR v7.4

Lanzamos OR-Tools v7.4. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas OR.

Nuevas funciones y mejoras

  • El solucionador de problemas CP-SAT ahora comprueba si hay restricciones que no admitan literales de aplicación. El verificador de modelos mostrará un error antes de resolverlo si esa restricción tiene un literal de aplicación.
  • Búsqueda local mejorada y más rápida para la biblioteca de enrutamiento.
  • El solucionador de problemas lineal ahora admite el software de terceros Xpress-MP. Deberás volver a compilar las herramientas del operador OR desde el origen para usarlas.
  • La arquitectura del paquete NuGet se reescribió por completo. En particular, ahora es compatible con .NET Framework >= 4.5.2 en plataformas Windows.

Plataforma obsoleta

Como se anunció en las notas de la versión de julio de 2019, OR-Tools ya no es compatible con Python 2.7.

Actualización de dependencia

Se actualizó Protobuf 3.9.0 a 3.10.0.

Agosto de 2019

Anuncio del lanzamiento de las herramientas OR v7.3

Lanzamos OR-Tools v7.3. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas OR.

Plataforma obsoleta

Python 2.7 dejará de ser compatible con la migración de Google a Python 3. Esta será la última versión de las herramientas del operador OR compatibles con Python 2.7.

Actualización de dependencia

Se actualizó Protobuf 3.8.0 a 3.9.0.

Correcciones de errores

Los siguientes problemas se corrigieron en las herramientas OR v7.3. (para obtener una lista completa, consulta Kanban v7.3).

En particular, considera lo siguiente:

  • Se corrigió el error de transmisión init/int64 en Java (#1448).
  • Se corrigió la verificación de salida cuando se procesan restricciones acumulativas vacías.

Julio de 2019

Anuncio del lanzamiento de las herramientas OR v7.2

Lanzamos OR-Tools v7.2. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas OR.

Cambios en la plataforma

  • Python 2.7 dejará de ser compatible con la migración de Google a Python 3. Como máximo, habrá una actualización más de las herramientas del operador OR compatibles con Python 2.7.
  • Ubuntu 18.10 actualizado a Ubuntu 19.04.
  • Se agregó compatibilidad para la compilación de fuentes en Visual Studio 2019.
  • Python 3.5 ya no es compatible con Windows. Utiliza Python 3.6 o una versión posterior.

Actualizaciones de dependencias

  • Ahora la orientación es CBC 2.10.3.
  • Ahora nos orientamos a Protobuf 3.8.0.

CP-SAT

  • Realizamos varias mejoras en la búsqueda, el paralelismo y la relajación lineal.
  • Se agregaron las APIs de LinearExpr.Sum() y LinearExpr.ScalProd() en Python.
  • Las APIs de IntVar[].Sum() y IntVar[].ScalProd() dejaron de estar disponibles en C#
  • C++: Se quitó SolveWithModel() porque era un duplicado de SolveCpModel().
  • Se agregaron los métodos CpModel.addGreaterThan() y CpModel.addLessThan() a la API de Java.

Resolución de problemas lineales

  • Se agregó MPSolver.SetHint() para Python, Java y C# (compatible con SCIP y Gurobi).
  • Se agregó MPSolver.SetNumThreads() para Python, Java y C# (compatible con CBC, Guurobi y SCIP).
  • Se reescribió la compatibilidad con SCIP 6.0.1.

Documentación de referencia

  • Agregamos manuales de referencia basados en doxygen y pdoc3 para todos los lenguajes y todas las herramientas (algoritmos, enrutamiento, grafo, linear_solver y CP-SAT). Consulta Manuales de referencia de las herramientas OR.
  • La documentación de referencia está completa para C++ (todos los productos) y CP-SAT (C++, Python y Java).
  • Estamos en proceso de exportar toda la documentación de C++ a Python y Java.
  • Falta la documentación de .NET y no tenemos una solución en el futuro inmediato para mejorarla. Lo mantuvimos, ya que todavía muestra la API disponible.

Mayo de 2019

Anuncio del lanzamiento de las herramientas OR v7.1

Lanzamos OR-Tools v7.1. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas OR.

Cambios en las dependencias requeridas

OR-Tools v7.1 tiene las siguientes dependencias nuevas y actualizadas:

  • glog v0.3.5 se actualizó a v0.4.0
  • protobuf v3.6.1 actualizado a v3.7.1
  • Cbc 2.9.9 se actualizó a 2.10.1
  • Cgl 0.59.10 actualizado a 0.60.1
  • Clp 1.16.11 actualizado a 1.77.1
  • Osi 0.107.9 actualizado a 0.108.1
  • CoinUtils 2.10.14 se actualizó a 2.11.1

Cambios en la API de CP-SAT

En las siguientes secciones, se describen los cambios realizados en la API de CP-SAT en las herramientas OR 7.1.

Usa un dominio para crear variables

En los siguientes ejemplos, se muestra cómo crear una variable de número entero con dominios no contiguos. Esto reemplaza el método NewEnumeratedIntVar() que se quitó. Aquí, la variable x puede ser cualquiera de 1, 3, 4 o 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");

Las variables también se pueden crear usando una lista de intervalos. Debajo, la variable x está restringida a 1, 2, 4, 5 o 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");

Cómo usar Domain en una expresión lineal

En los siguientes ejemplos, se muestra cómo limitar una expresión lineal en un dominio no contiguo. Aquí, la expresión lineal linear_expr se define en 5, 6, 8, 9 y 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} }));

Cómo usar asistentes de expresiones lineales

En los siguientes ejemplos, se muestra cómo usar métodos auxiliares para crear sumas y productos escalares. Aquí, se muestra un ejemplo en el que queremos x + y == 20 y 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);

Marzo de 2019

Anuncio del lanzamiento de las herramientas OR v7.0

Lanzamos OR-Tools v7.0. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas OR.

Cambios en las plataformas compatibles

OR-Tools v7.0 ya no es compatible con las siguientes plataformas:

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

Si utilizas una de estas plataformas, aún puedes instalar OR-Tools v6.10.

Cambios en las dependencias requeridas

OR-Tools v7.0 tiene las siguientes dependencias nuevas y actualizadas:

En las siguientes secciones, se describen las nuevas funciones y mejoras en las herramientas OR 7.0.

Nuevo administrador de índices para programas de enrutamiento

En las herramientas de OR versión 7.0, los programas de planificación de ruta de vehículos deben usar el nuevo RoutingIndexManager. Esto garantiza que los índices estándar de las ubicaciones sean coherentes con los índices internos que usa el solucionador y ayuda a evitar errores en tu código.

El nuevo RoutingIndexManager requiere algunos cambios menores para enrutar los programas, que se describen en las siguientes secciones:

Incluir/importar RoutingIndexManager

En OR-Tools 7.0, los programas de enrutamiento en C++ y Java deben incluir o importar RoutingIndexManager como se muestra en los siguientes ejemplos:

C++

#include "ortools/constraint_solver/routing_index_manager.h"

Java

import com.google.ortools.constraintsolver.RoutingIndexManager;

Las importaciones de Python y C# no se modifican.

Declara RoutingIndexManager

En las Herramientas del operador v7.0, los programas de enrutamiento deben declarar el RoutingIndexManager y crear el modelo de enrutamiento, como se muestra en los siguientes ejemplos:

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);

Los argumentos de RoutingIndexManager son los siguientes:

  • La cantidad de ubicaciones
  • La cantidad de vehículos
  • El índice del depósito (ubicación de partida y de finalización para todos los vehículos)

Devoluciones de llamada

En la versión 7.0 de las herramientas del OR, debes usar RoutingIndexManager para crear devoluciones de llamada, como la devolución de llamada de distancia, que luego pasas al solucionador. En los siguientes ejemplos, se muestra cómo crear una devolución de llamada de distancia.

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);

El método IndexToNode convierte los índices de ubicación interna que usa el controlador en los índices estándar de la matriz de distancia.

En lugar de pasar la devolución de llamada directamente al solucionador, como en las versiones anteriores, en la versión 7.0, primero debes crear transit&nbsp;callback&nbsp;index, una referencia a la devolución de llamada, y pasarla al solucionador (en este caso, SetArcCostEvaluatorOfAllVehicles).

Dimensiones

En los siguientes ejemplos, se muestra cómo crear una dimensión para las demandas y las capacidades, que se usa con el objetivo de resolver el problema relacionado con las rutas habilitadas para los vehículos.

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");

Soluciones de impresión

En la versión 7.0 de las herramientas del OR, debes usar RoutingIndexManager para mostrar las rutas de los vehículos en una solución. En los siguientes ejemplos, se muestra cómo imprimir soluciones en todos los lenguajes 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);
    }

Compatibilidad con VRP con retiros y entregas

OR-Tools v7.0 proporciona asistencia para resolver problemas de rutas de vehículos (VRP) con retiros y entregas, en los que el objetivo es encontrar las rutas más cortas para una flota de vehículos que recoge y entrega artículos en varias ubicaciones. Configuraste el problema de manera similar a un VRP estándar, pero, además, especificas un par (i, j) de ubicaciones para cada elemento, donde i es el punto de partida y j es el lugar de llegada. La herramienta muestra rutas de vehículos de modo que, para cada par (i, j), i y j están en la misma ruta, y el vehículo visita i antes de j.

Para ver un ejemplo que resuelva este tipo de problema, consulta Rutas de vehículos con retiros y entregas.

Compatibilidad con funciones lambda

OR-Tools v7.0 ahora incluye compatibilidad para funciones lambda en C# y Java (además de C++ y Python, que ya eran compatibles). Las funciones lambda proporcionan una manera conveniente de definir devoluciones de llamada en programas de enrutamiento. Sin embargo, puedes definir devoluciones de llamada con funciones estándar si crees que esto hace que el código sea más legible.

En los ejemplos de devolución de llamada de C# y Java anteriores, se muestra cómo definir devoluciones de llamada con funciones lambda.

noviembre de 2018

Anuncio del lanzamiento de la versión v6.10

Hemos lanzado OR-Tools versión 6.10. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas de OR.

En las siguientes secciones, se describen las nuevas funciones y mejoras de la versión 6.10.

Comandos simplificados para compilar y ejecutar programas

En la versión 6.10, puedes compilar y ejecutar programas ingresando comandos como los siguientes:

make run SOURCE=relative/path/to/program.cc
, en el que <var>relative/path/to</var> es la ruta de acceso al directorio que contiene el programa.

Para compilar un programa sin ejecutarlo, ingresa lo siguiente:

make build SOURCE=relative/path/to/program.cc
Consulta Cómo comenzar a usar las herramientas del operador OR para obtener instrucciones específicas sobre cómo ejecutar programas por lenguaje.

Compatibilidad con SCIP 6.0.0

Las herramientas OR ahora son compatibles con SCIP 6.0.0.

Objetos binarios

Las distribuciones binarias se compilaron con Java JDK 8 (JDK 7 para Ubuntu 14.04).

Resolución de CP-SAT

Actualiza la API

  • Se agregó la API de CpModelBuilder CP-SAT de C++.

Ejemplos

Se movieron algunos ejemplos.

  • Traslada los ejemplos de la comunidad a examples/contrib.
  • Mueve algunos ejemplos a ortools/<var>component</var>/samples (p. ej., ortools/linear_solver/samples/simple_program.java).

Septiembre de 2018

Anuncio del lanzamiento de la versión v6.9

Lanzamiento de OR-Tools en la versión 6.9. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas de OR.

Se actualizaron las dependencias

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

Resolución de CP-SAT

  • Cambios rotundos en la API: Obtén todos los detalles aquí:
  • Cambia el nombre de SolveWithSolutionObserver a SolveWithSolutionCallback en Python.

  • Se cambió el nombre de NewSolution a OnSolutionCallback en la clase CpSolverSolutionCallback en Python. En el siguiente ejemplo, se muestra la nueva manera de crear una devolución de llamada de solución 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

  • Se expuso StopSearch en la devolución de llamada de solución en Python, Java y C#. Consulta la documentación aquí.

  • Expón ModelStats y CpSolverResponseStats en Python, Java y C#.

  • Mejora la documentación de docstring de Python. Consulta la documentación aquí.

  • Se actualizaron la implementación de Java de la interfaz de resolución y la guía de soluciones.

  • Implementa el módulo.

  • Cambia la implementación del reservorio: agrega una API con un valor booleano para especificar eventos opcionales de vaciado o relleno.

Servicio de resolución lineal

  • Se expuso InterruptSolve en Java y C#.

Soluciones de CP

  • Expón el director SolutionCollector en C#.

Python

  • Se agregó compatibilidad con Python 3.7.
  • Si compilas desde la fuente, prioriza python3 en lugar de python2 cuando detectes Python.

.NET

  • Reescritura completa de la capa de .NET.
  • Proporcionar un paquete Google.OrTools de NetStandard 2.0 Nuget compatible con el IDentificador de entorno de ejecución win-x64, linux-x64 y osx-x64.
  • Proporciona un paquete de Nuget de Google.OrTools.FSharp.
  • Agrega un archivo de proyecto para todos los ejemplos de .NET.
  • Actualiza todos los ejemplos de secuencias de comandos de F# (.fsx) a un proyecto de F# normal (.fs).
  • Agrega documentación sobre la generación de compilación de paquetes .NET aquí.

Piso de zinc

  • Se agregó compatibilidad para conjuntos en Flatzinc (con nosets.mzn).

Contribuciones

  • Se agregó compatibilidad con Binder. Gracias a Kevin Mader.
  • Haz que DecisionVisitor sea un tipo de director en las vinculaciones de Java. Agradecimientos a Jeremy Apthorp.

Julio de 2018

Anuncio del lanzamiento de la versión v6.8

Hemos lanzado OR-Tools en la versión 6.8. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas de OR.

Anuncio del solucionador de problemas CP-SAT

El solucionador de problemas CP-SAT es un nuevo solucionador para la programación de restricciones. El solucionador de problemas de CP-SAT es más rápido que el de CP original y es la opción recomendada para estos problemas.

Para ver ejemplos que usen el solucionador de problemas CP-SAT, busca archivos que tengan _sat en el nombre en el directorio examples en GitHub.

El solucionador de problemas de CP original se mantendrá durante un tiempo para admitir el código existente, pero está obsoleto.

Nuevas opciones para el solucionador de problemas CP-SAT

Las siguientes opciones para el solucionador de problemas de CP-SAT son nuevas en esta versión:

  • Búsqueda de vecindarios local (LNS): Usa la opción SatParameters.use_lns para habilitar LNS.
  • Búsqueda paralela: Usa la opción SatParameters.num_search_workers para habilitar varios subprocesos durante una búsqueda. Cada subproceso puede tener diferentes parámetros y diferentes valores iniciales aleatorios. Esto maximiza la diversidad y la probabilidad de que al menos un subproceso encuentre soluciones.

Mejoras en el rendimiento de las soluciones de problemas

Se realizaron mejoras de rendimiento en las soluciones de CP-SAT y Glop.

Marzo de 2018

Anuncio del lanzamiento de la versión v6.7

Hemos lanzado OR-Tools en la versión 6.7. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas OR.

Actualiza a las dependencias requeridas

  • Protobuf 3.5.0 -> 3.5.1.

Varios

  • Refactoriza la base para preparar la integración de abseil-cpp.
  • Uso de los servicios de integración continua (CI) de Travis CI y Appveyor.

SÁB

  • Mejora del rendimiento.
  • Mejora la API de Python.
  • Agrega la API de C#, también conocida como CpSolver.cs (EXPERIMENTAL).

Glop

  • Refactorización del código
  • Mejora del rendimiento.

Compatibilidad con CMake (EXPERIMENTAL)

  • Se agregó compatibilidad con CMake de C++ OR-Tools.
  • Poder compilar las herramientas OR como un proyecto de CMake independiente
  • Poder incorporar las herramientas OR en un proyecto de CMake existente
  • Agrega la compilación basada en CMake con Python OR-Tools.
  • Genera el paquete de Python (wheel) con CMake.

Contribuciones

  • Se corrigió la redefinición de winsock2.h en ventanas. Gracias a Florent Tollin de Rivarol.
  • Agrega asistencia para F# (EXPERIMENTAL). Gracias a Matthew Moore. Nota: Solo está disponible con el compilador de archivos makefile.
  • Agrega la Asistencia estándar de .NET (EXPERIMENTAL). Gracias a Ziad El Malki. Nota: Solo está disponible con el compilador de archivos makefile.

Noviembre de 2017

Anuncio del lanzamiento de la versión v6.6

Hemos lanzado OR-Tools versión 6.6. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas de OR.

Actualizaciones de las dependencias requeridas

  • Protobuf a 3.3.0 -> 3.5.0.
  • gflags a 2.2.0 -> 2.2.1.
  • CBC 2.9.8 a 2.9.9.
  • Agrega el módulo seis de Python (1.10) como dependencia necesaria para Python.

Correcciones de errores

  • Refactorización del nombre de la solicitud de extracción #494. Se agregaron comentarios para IntelliSense en algunos editores. Gracias a Matthew Moore.
  • Instrucción de solicitud de extracción #516 para el objeto binario independiente de F#. Gracias a Matthew Moore.
  • Mejora la precisión en Glop.

Resolutor de SAT

  • Mejorar el solucionador de problemas de SAT interno, corregir varios errores
  • Se agregó una restricción de VRP al solucionador de SAT, vinculado al solucionador de LP.
  • Cambia el observador de la solución en el solucionador de SAT para tomar un CpSolverResponse como parámetro.
  • Se mejoró el uso de Glop en el servicio de resolución de SAT.
  • Acelera la conexión SAT-LP.
  • Se agregó una restricción de reserva al formato de protobuf de cp_model de SAT.

SAT/Python

Ejemplos

  • Vuelve a escribir rcpsp_parser a fin de usar el formato ProtoBuf para almacenar el problema.
  • Se mejoró el analizador de RCPSP.

octubre de 2017

Anuncio de la versión v6.5

Hemos lanzado OR-Tools en la versión 6.5. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas de OR.

Cambio en las plataformas

  • El módulo pypi py3-ortools se combinó con el módulo ortools. Ahora solo hay un módulo: "ortools".
  • Ahora, el formato principal para estos módulos de Python son los archivos wheel. Si quieres instalar las herramientas OR para Python desde pypi, solo ejecuta pip install ortools. Necesitas tener instalada una versión reciente de pip (>= 9.0.1). Esto debería extraer la versión más reciente (v6.5).

Error corregido

El archivo jar de protobuf ahora se compila correctamente con clases compiladas.

Ejemplos nuevos

  • Se agregaron más ejemplos de F# al directorioexamples/fsharp (gracias de nuevo a Matthew Moore).
  • También se aportaron ejemplos de MIP de Java (Gracias, Darian).

septiembre de 2017

Anuncio del lanzamiento de la versión v6.4

Hemos lanzado OR-Tools versión 6.4. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas de OR.

Cambio en las plataformas

  • Los módulos Pypi en plataformas Linux ahora se entregan como archivos de rueda con la etiqueta mucholinux1. Gracias a Federico Ficarelli. Con este cambio, retrocedimos el seguimiento de los módulos por Linux que se introdujeron en la versión de julio de 2017.

Funciones nuevas

  • Se mejoró el método de escalamiento usado dentro de GLOP.
  • Se corrigió la unión de evaluadores en la biblioteca de enrutamiento de C#. Gracias a DevNamedZed.
  • Mejora el rendimiento de la resolución Flatzinc para modelos grandes.
  • Utiliza el SAT respaldado para el zinc de forma predeterminada.
  • Mejora el rendimiento del enfoque basado en Core para el solucionador satisfactorio.
  • Se corrigió el error en el algoritmo de asignación lineal que fallaba incorrectamente.
  • Se agregaron ejemplos de F# en ortools/examples/fsharp.
  • Quita la verificación de penalizaciones positivas en la biblioteca de enrutamiento.

Agosto de 2017

Anuncio del lanzamiento de la versión v6.3

Hemos lanzado OR-Tools versión 6.3. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas de OR.

Nuevos archivos de descarga

Los archivos de la rueda de Python para Linux ahora están disponibles para descargar en la página de versiones de herramientas OR, junto con las versiones más recientes de todas las descargas.

Resolución de minizinc

Esta versión contiene el código final sat y Flatzinc que se envió para el desafío de Minizinc 2017.

Julio de 2017

Anuncio de la versión v6.2

Hemos lanzado OR-Tools versión 6.2. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas de OR.

Cambio en las plataformas

  • Ahora admitimos varias distribuciones binarias de Linux (Ubuntu 14.04, 16.04, 17.04, CentOS 7 y Debian 9).
  • Los módulos Pypi en plataformas Linux ahora incluyen una etiqueta que describe la distribución (ubuntu-14.04, ubuntu-16.04, ubuntu-17.04, centos-7, debian-9).

Funciones nuevas

Se agregó compatibilidad con Docker para compilar artefactos de Linux. Ve a or-tools/tools/docker y observa el Makefile para ver los destinos posibles (make archive, make pypi y make pypi3).

Estos comandos crearán un subdirectorio export y le agregarán artefactos binarios.

Junio de 2017

Anuncio del lanzamiento de la versión v6.1

Hemos lanzado OR-Tools versión 6.1. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas de OR.

Cambio en las plataformas

  • Se admite Visual Studio 2017, pero ya no se admite Visual Studio 2013.
  • Se admiten las versiones 10.9 y posteriores de macOS.

Nuevas funciones

Agregamos un nuevo formato protobuf para nuestro solucionador de problemas CP-SAT. Consulta ortools/sat/cp_model.proto para definir tu modelo y ortools/sat/cp_model_solver.h para resolver tu problema.

Correcciones de errores

Problema #420: Se corrigió el atributo __version__ que faltaba en los módulos pypi de Python en todas las plataformas.

Mayo de 2017

Anuncio de la versión v6.0

Hemos lanzado OR-Tools versión 6.0. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas de OR.

Nueva estructura de directorios en C++

Cambiamos la estructura de origen/inclusión de las herramientas OR cuando se usa C++. El objetivo es proporcionar una mejor encapsulación de los archivos de inclusión de C++. También tiene el beneficio de alinear las estructuras de directorios de C++ y Python.

  • Se cambió el nombre de src/ a ortools/.
  • Todos los comandos #include en archivos C++ ahora tienen el prefijo ortools agregado. #include "constraint/constraint_solver.h" ahora es #include "ortools/constraint/constraint_solver.h".

Funciones nuevas

  • Compatibilidad con Bazel Ahora puedes compilar herramientas del operador OR con bazel, la herramienta de compilación de Google. Funciona en Linux y Mac OS X. Después de descargar Bazel versión 0.4.5 o una versión posterior, cambia el directorio a or-tools y compila los ejemplos: bazel build examples/cpp/....

Enrutamiento

Implementamos asistencia para los descansos (p.ej., tiempo de inactividad en los vehículos debido a que los conductores almorzan) en la biblioteca de rutas. Esta función se muestra en el ejemplo de cvrptw_with_breaks.cc.

Compatibilidad con SCIP

El wrapper del solucionador de problemas lineal ahora admite SCIP 4.0. Primero debes compilar SCIP y, luego, indicarle a las herramientas o herramientas que lo usarás. Las instrucciones están disponibles aquí.

Asistencia de GLPK

También cambiamos el camino para compilar con GLPK. Obtén más información aquí.

Limpieza

  • Se quitó todo el uso de hash_map y hash_set de la base de código de C++, ya que dejaron de estar disponibles. Se reemplazaron por unordered_map y unordered_set de la STL.
  • Limpieza de los archivos makefile en C#, cortesía de Michael Powell.

Enero de 2017

Anuncio de la versión v5.1

Hemos lanzado OR-Tools en la versión 5.1. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas de OR.

Nuevas funciones

Instalación

Enrutamiento

Se implementó un algoritmo para calcular el límite inferior de Held-Karp para los problemas simétricos de vendedores que viajan. Esto te permite calcular un límite superior para la brecha entre el costo de una solución que posiblemente no sea óptima y el costo de la solución óptima.

  • Se agregó un nuevo método a la biblioteca de rutas de vehículos, RoutingModel::SetBreakIntervalsOfVehicle, que te permite agregar intervalos de break, es decir, períodos en los que un vehículo no puede realizar ninguna tarea (como viajar o visitar un nodo). Para ver un ejemplo que use esta opción, consulta cvrptw_with_breaks.cc.

Programación

Resolución de sábados

Mejoras en el rendimiento

  • Resolución de SAT: Se mejoró el rendimiento del agente de resolución de SAT, en particular para la restricción acumulativa.
  • Resolución de problemas de Glop: Se mejoró la solidez numérica del agente de resolución de Glop, que ahora muestra soluciones aún más precisas para problemas numéricos difíciles.
  • Resolución de problemas de Flatzinc
  • Se mejoró considerablemente el rendimiento del backend Sat para el intérprete de Flatzinc.
  • Se simplificó la interfaz plana de C#. Para ver un ejemplo de la interfaz nueva, consulta https://github.com/google/or-tools/blob/master/examples/csharp/csfz.cs.

Correcciones de errores

  • El uso de la heurística de PathCheapestArc en el enrutamiento de modelos con un solo vehículo y restricciones laterales provocaba que el solucionador se ejecutara durante mucho tiempo. Para solucionarlo, se tomaron en cuenta las restricciones complementarias.
  • En Java, el solucionador de problemas de enrutamiento a veces fallaba cuando se resolvían los problemas de enrutamiento de vehículos. Este problema se corrigió en la versión más reciente.

Noviembre de 2016

Anuncio de la versión v5.0

Hemos lanzado OR-Tools versión 5.0. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas de OR.

Ejemplos de ejecución

  • Se introdujeron objetivos específicos del lenguaje que facilitan la compilación y ejecución de tus programas, así como los ejemplos que vienen con las herramientas OR.

Sáb

FlatZinc

Resolución de restricciones

Enrutamiento

  • Se implementó AddAtSolutionCallback, que es una devolución de llamada a la que se llama cada vez que se encuentra una solución durante la búsqueda.
  • Se quitaron los constructores sin depósito de RoutingModel. Ahora es obligatorio especificar al menos un depósito en el modelo de enrutamiento.

(septiembre de 2016)

Anuncio de la versión v4.4

Hemos lanzado OR-Tools versión 4.4. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas de OR.

Sáb

  • API de programación extendida y ejemplos modificados (Weight_tardiness_sat y jobshop_sat) para usarla.

Graph

  • Se agregaron características del iterador a las clases de grafos.

Distribución de las herramientas del operador OR

  • Se volvió a admitir el paquete Nuget.

agosto de 2016

Anuncio del lanzamiento de la versión v4.3

Hemos lanzado OR-Tools versión 4.3. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas de OR.

Resolución de restricciones

  • Se implementó el método NotBetween para restringir una variable a un intervalo determinado.

enrutamiento

  • Se agregó un análisis del modelo para verificar las restricciones NotMember existentes como se muestra en este ejemplo y usarlas en filtros de búsqueda locales.
  • Se agregó la generación de perfiles de búsqueda local.
  • Solución de traslados locales

Resolución de problemas lineales

  • Se corrigieron los informes de estado de SCIP.

Sáb

  • Se implementó el método SolveWithPresolve para simplificar el uso del agente de resolución SAT.
  • Se reagruparon las utilidades de búsqueda en src/sat/util.h|cc.
  • Se implementaron restricciones de programación SMT (generación de cláusulas diferidas): consulta jobshop_sat.cc y weighted_tardiness_sat.cc.

Glop

  • Se mejoró el rendimiento mediante el aprovechamiento de la dispersión en más etapas de procesamiento.

Piso de zinc

  • Se corrigieron errores detectados por el desafío de minizinc.

Lp_data

  • Se simplificó de forma continua las plantillas en los iteradores.

Distribución de las herramientas del operador OR

  • Los ensamblados de C# ahora tienen nombres fuertes de forma predeterminada.
  • Se actualizó a Protobuf3.0.0.
  • Se agregó una secuencia de comandos de Python para verificar las dependencias de archivo de las herramientas del OR.

julio de 2016

Anuncio de la versión v4.2

Hemos lanzado OR-Tools versión 4.2. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas de OR.

Resolución de restricciones (enrutamiento)

  • Una disyunción ahora se puede definir con una cardinalidad, que es la cantidad máxima de nodos que pueden estar activos dentro de esta disyunción. Por ejemplo, si agregas una disyunción con n nodos y una cardinalidad de k, entonces se permite que k nodos entre los n nodos estén activos. Para ello, puedes usar la definición nueva de AddDisjunction.
  • Se agregó compatibilidad con varias disyunciones por nodo. Por ejemplo, ahora puedes agregar un nodo, N1, a muchas disyunciones (D1..Dm). Esto aumenta la probabilidad de estar activo dentro de cualquiera de ellos. Se introdujo un algoritmo de búsqueda de enrutamiento más rápido para problemas relacionados con las ventanas de tiempo disyuntivo.
  • Se agregaron parámetros del solucionador de problemas de restricciones a los parámetros del modelo de enrutamiento y log_search a los parámetros de búsqueda de enrutamiento.
  • El algoritmo de búsqueda local es más rápido a la hora de resolver problemas con períodos inconexos. Consulta el ejemplo cvrp_disjoint_tw.cc para obtener más detalles.

Glop (optimización lineal)

  • Se introdujo un algoritmo simplex más rápido.

Distribución de las herramientas del operador OR

  • Un archivo por plataforma, en lugar de archivos individuales para cada uno de C++, Java y .NET. Los archivos de Python aún se alojan en pypi.
  • En pypi, cambiamos a los módulos wheel (.whl) en Mac OS X y Windows. Se introdujo un esquema de numeración MAJOR.MINOR. Estos números se usan para los nombres de archivo, la versión almacenada en las bibliotecas compartidas de Mac OS X, los módulos de Python y los ensamblados de .NET. La primera versión que lanzaremos es la 4.2, con este esquema.

junio de 2016

Anuncio del lanzamiento de la versión v2016-06

Lanzamos la versión v2016-06 de OR-Tools. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas de OR.

Resolución de restricciones

  • Se quitó la mayoría de las instancias de las devoluciones de llamada (src/base/callback.h) de la biblioteca de CP.
  • Se agregó NotMemberCt (la variable no puede pertenecer a un conjunto de intervalos).

Biblioteca de enrutamiento

  • CAMBIO INCOMPATIBLE: Para especificar la capacidad de los vehículos en AddDimensionWithVehicleCapacity, ahora debes pasar un array (un vector en c++) en lugar de una devolución de llamada.

GLOP

  • Cambia la representación interna de una matriz dispersa.
  • Se implementaron mejoras en el rendimiento.

Graph

  • Se reescribieron los algoritmos Dijkstra y Bellman-Ford para reemplazar las devoluciones de llamada por std::function (C++).
  • Se cambió la API de diferentes implementaciones de grafos cuando se itera en arcos y nodos.

Sáb

  • Quita el método principal sin usar (nodos de resolución).
  • Se agregó un autor dramatizador para verificar pruebas de insatisfacción.
  • Agrega el preprocesador.

Bebop

  • Agrega barrios nuevos.

Ejemplos

  • c++: Cómo deshacerse de filelinereader en ejemplos
  • datos: Agrega problemas de programación de una sola máquina.

Documentación

Abril de 2016

Anuncio del lanzamiento de la versión v2016-04

Lanzamos la versión v2016-04 de OR-Tools. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas de OR.

Se actualizaron las dependencias

Diciembre de 2015

Anuncio del lanzamiento de la versión v2015-12

Lanzamos la versión v2015-12 de OR-Tools. Para actualizar tu versión, consulta la sección correspondiente en Instalación de herramientas de OR.

Resolución de restricciones

  • Se rompió la compatibilidad con Large Neighborhood Search en el solucionador de problemas de PC (consulta examples/cpp/ls_api.cc, examples/python/pyls_api.py, examples/csharp/csls_api.cs y examples/com/google/ortools/sample/LsApi.java para ver la nueva API).
  • Se limpió el ajuste de Python. Admite la decisión personalizada en la resolución de CP (consulta examples/test/test_cp_api.py para ver la API en acción).
  • Diversas mejoras y correcciones de errores.

Septiembre de 2015

Anuncio de la primera versión en GitHub.

A partir de ahora, los archivos se almacenarán allí.

Piso de zinc

  • Se agregaron archivos binarios para el intérprete de Flatzinc (consulta www.minizinc.org).
  • Contiene algunas correcciones de la versión utilizada en el desafío.