OR-Tools 版本说明

本页面列出了对 OR-Tools 的更改，包括新功能、bug 修复以及对代码和安装过程的改进。

如果您在安装 OR-Tools 时遇到问题，请参阅 OR-Tools 安装说明中的问题排查部分。如果您的问题未列出，请查看 GitHub 上的问题，或者随时提出新问题，我们非常乐意为您提供帮助。

以下是 OR-Tools 的版本说明，从最新版本开始。

2024 年 5 月

宣布推出 OR-Tools v9.10

我们发布了 OR-Tools v9.10。如需更新版本，请参阅 OR 工具安装中的相应部分。

您可以在 GitHub 上找到版本说明。

2024 年 3 月

宣布推出 OR-Tools v9.9

我们发布了 OR-Tools v9.9。如需更新版本，请参阅 OR 工具安装中的相应部分。

您可以在 GitHub 上找到版本说明。

2023 年 11 月

宣布推出 OR-Tools v9.8

我们发布了 OR-Tools v9.8。如需更新版本，请参阅 OR 工具安装中的相应部分。

平台变更

  • 添加 Python 3.12。
  • 添加对 Ubuntu 23.10 的支持

线性求解器

  • 将 ModelBuilder 端口移植到 .Net。
  • 将 LogCallback 重命名为 MbLogCallback，以避免与 SAT LogCallback 发生冲突。
  • 扩展 ModelBuilder API：
    • 添加了指示器约束条件。
    • 添加了提示支持。
    • 添加模型克隆。

数学选项

  • 深度返工。

路由

  • 添加 ROUTING_OPTIMAL 状态。
  • 将 RoutingModel 设为不可复制或不可移动。
  • 修复了本地搜索运算符中存在的一些无限循环问题。
  • 添加一个 PickupDeliveryPosition 内部结构体。
  • 添加了 IsPickup() 和 IsDelivery() 方法。

SAT

  • 减少大型模型的内存占用量。
  • 改进了按计划搜索的功能。
  • 添加 packing_beforences_lns。
  • 优化和修复可行性跳跃问题。
  • 优化线性解析和更好的解析日志记录。
  • 改进了 int_abs、int_mod、int_prod 和 lin_max 的解析。
  • 改进对 Panda 的支持
  • 修复了一些 bug。

GitHub 更新日志

2023 年 8 月

发布 OR-Tools v9.7

我们发布了 OR-Tools v9.7。如需更新版本，请参阅 OR 工具安装中的相应部分。

平台变更

  • 停用 Centos-8 (EOL)。
  • 舍弃 Debian 10。
  • 停用 Fedora [33, 36]（服务终止）。
  • 丢弃 Ubuntu 18.04 LTS (EOL)。
  • 删除 Python 3.7 (EOL)。
  • 在 CMake 中停用 netcore3.1 支持 (EOL)。

模型构建器 Python

  • 允许使用 Pandas DataFrame 和系列创建变量。
  • 填写输入信息

PDLP

  • 各种更新。

CP-SAT

  • 提升了性能。（feasability_jump、lin_max）
  • 改进剪辑管理
  • 新增了 goal_shave_search 工作器，用于提高目标的下限（最小化时）
  • 为 Python cp_model.py 键入注释
  • 在 cp_model.py 中对 Pandas 进行了实验性部分支持
  • 基于实验性本地搜索违规的工作器：
    • 已启用参数：num_violation_ls:xxx
    • 针对线性模型（linear、bool_or、bool_and、at_most_one、exactly_one）进行了优化
    • 可与 lin_max、product、division 正常配合使用
    • 支持无重叠、累计、线路、路由
    • 已使用 no_overlap_2d 停用
    • 建议的 ls 工作器数量：num_workers -> num_violation_ls：(8, 1), (16, 2) (24, 3), (32, 4)

GitHub 更新日志

2023 年 3 月

宣布推出 OR-Tools v9.6

我们发布了 OR-Tools v9.6。如需更新版本，请参阅 OR 工具安装中的相应部分。

平台变更

  • 添加了 Fedora 37、38 支持。
  • 舍弃 Python 3.6（不受 protobuf 支持）。
  • 在 macOS 上删除 Python 3.7（不受 scipy 支持）。
  • 在 CMake 中添加 net7.0 支持（使用 -DUSE_DOTNET_7=ON）
  • 移除了 nuget .org 软件包中的 netcore3.1

依赖项

  • SCIP v801 -> v803（注意：SCIP 现在使用与 OSI 兼容的许可）
  • 绝对值 20220623.1 -> 20230105.0
  • Protobuf v21.5 -> v21.12
  • 切换4.1.1
  • Java JNA 5.11.0 -> 5.12.1

Bazel

  • 添加了 pybind11 支持。
  • 添加了 Java 封装容器支持。

求解器

  • PDLP：dd Python 封装容器。
  • CP-SAT：提升了性能。
  • GLOP：调整 presolve。
  • ModelBuilder：Python：改进 numpy 支持。
  • 路由：性能改进（本地搜索）

已知问题：

  • CP-SAT：忽略 pseudo_costs 子求解器会返回无效参数（请参阅 #3706）。

2022 年 11 月

宣布发布 OR-Tools v9.5

我们发布了 OR-Tools v9.5。如需更新版本，请参阅 OR 工具安装中的相应部分。

平台变更

  • 添加了 Debian Sid 支持。
  • 添加了 Fedora 35、36 支持。
  • 添加 Ubuntu 22.10 支持。
  • 在 macOS 上删除 Python 3.6。
  • 添加了 Python 3.11 支持。

依赖项更新

  • Protobuf v19.4 -> v21.5。
  • SCIP 求解器 v800 -> v801。

CP-SAT

  • 解析改进：max(array)、布尔值约束、线性约束。
  • 交错搜索应该是并行确定的。
  • 线性剪切：清理方形和 int_prod 剪切；重写剪切流水线。
  • 指纹输入模型和解决方案（会在日志中显示）。
  • 改进了时间安排。
  • 常见的一些 bug 修复（解析期间发生崩溃、切割崩溃、不可行的解决方案、LNS 中模型不可行）。

GLOP

  • 通过重写线性代数以及数据透视选择规则，加快速度。

线性求解器

  • 添加 knapsack_interface.cc。
  • 将 model_builder API 移到 linear_solver 目录（标头和示例）下。
  • 添加了对 Gurobi 10 的支持。

路由

  • 释放少量解析器以应对各种路由挑战。

2022 年 8 月

宣布推出 OR-Tools v9.4

我们发布了 OR-Tools v9.4。如需更新版本，请参阅 OR 工具安装中的相应部分。

平台

  • 添加了 Debian-10 支持（请参阅 #3029）。
  • 添加了 Ubuntu 22.04 LTS 支持（请参阅 #3276）。注意：将不支持 .Net 3.1（请参阅 dotnet/core#7038）。
  • 移除了 Ubuntu 21.10 支持。

其他

  • 按语言拆分归档，并将 CMake 配置添加到 C++ 配置 (#3200)。

图表

将“ortools.graph.pywrapgraph”拆分为：

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

这样就可以使用 Numpy 加快问题的设置速度。

CP-SAT

在以下方面做出了一些改进：

  • 安排（传播、剪切、下限）。
  • MaxSAT（预解析，基于核心的启发法）。
  • MIP 性能（预解析、剪切）。

2022 年 3 月

宣布推出 OR-Tools v9.3

我们发布了 OR-Tools v9.3。如需更新版本，请参阅 OR 工具安装中的相应部分。

平台变更

  • 放弃 Debian-10 支持。
  • 放弃 Ubuntu-16.04 支持。
  • 舍弃 .NET Framework 4.5.2。

依赖项更新

  • 添加了 Eigen 3.4.0。
  • 添加了 Google re2 2021-11-01。
  • Protobuf 3.19.1 -> 3.19.4。
  • SCIP 7.0.1 -> v800。

Python

  • 添加 pybind11。

特性

  • 将 PDLP 添加为实验性功能。
  • 将 MathOpt 添加为实验性功能。

CP-SAT

  • 重命名了几个 API 以保持一致性，例如，从 LinearExpr.ScalProd. 重命名为 LinearExpr.WeightedSum.。
  • 添加了 AddAtLeastOne/AddAtMostOne/AddExactlyOne 方法。
  • 以所有语言添加AddMultiplicationConstraint(z, x, y)。
  • 以所有语言添加AddMultipleCircuit()。

C++

  • 显式操作器 IntVar(BoolVar)。
  • 移除了 LinearExpr::Add*，并将其替换为运算符（例如 LinearExpr +=）。
  • 对线性表达式添加算术运算符。
  • 移除了 LinearExpr::BooleanSum/BooleanScalProd，请使用 Sum/WeightedSum。
  • 添加 CpModelBuilder::FixVariable()，用于将变量的网域覆盖为单个值。

Java

  • 重写 LinearExpr，添加增量构建器类：LinearExpr.newBuilder().add(x).addSum(<array of variables>).build()。
  • 遵循 C++ API：Circuit、MultipleCircuit、Cumulative、Reservoir、AllowedAssignment 和 ForbiddenAssignment 现在会返回一个包含增量 API 的专用类，用于添加新变量、术语和需求...

C

  • 记录所有方法。
  • 遵循 C++ API：Circuit、MultipleCircuit、Cumulative、Reservoir、AllowedAssignment 和 ForbiddenAssignment 现在会返回一个包含增量 API 的专用类，用于添加新变量、术语和需求...
  • 添加了 LinearExprBuilder 类，以增量方式构建表达式。

构建系统

CMake

  • 要求至少 CMake 3.18 或更高版本。

制造商

  • 现在，在内部使用基于 CMake 的 build。

2021 年 12 月

宣布推出 OR-Tools v9.2

我们发布了 OR-Tools v9.2。如需更新版本，请参阅 OR 工具安装中的相应部分。

平台变更

  • 添加了对 Ubuntu 21:10（上一个滚动版本）的支持。

依赖项更新

  • .Net TFM 更新 net5.0 -> net6.0（需要 .Net SDK 6.0 LTS 和 .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：添加 numpy >= 1.13.3。
  • 在 MacOS 上，在 -O1 中编译 Coin-OR 以避免运行程序发生崩溃。

路由

  • 改进了过滤条件。
  • 改进了第一个解决方案启发法。
  • 优化广告插播时间点的展示位置。

CP-SAT

重大变更

  • 底层协议缓冲区与以前的版本不兼容。必须使用更新后的构建器 API（C++、Python、Java 和 .NET）重新生成任何已存储的协议缓冲区
  • 特别是，间隔 protobuf 是干净的，因为我们移除了旧字段（start、size 和 end），并重命名了新字段（使用 _view），以使用所移除字段的名称。

新功能

  • all_different、reservoir、modulo、multiplication 和 division 约束条件在需要整数变量的所有位置都接受仿射表达式 (a * var + b)。
  • 目标接受浮点系数（请参阅 C++/Java/.NET 中的 DoubleLinearExpr 类。请参阅 Python 中的 knapsack_2d_sat.py 示例）。
  • no_overlap_2d 约束条件支持可选的间隔。
  • C++ API 通过实现 + 和 * 运算符来构建表达式。

改进

  • 改进了 presolve 代码。
  • 更严格的模型检查工具。
  • 返工水库限制。
  • 为 no_overlap_2d 约束条件添加能量切割。
  • 改进了编码约束的线性放宽 (literal implies var == value)。

已废弃和已移除的方法

  • 废弃了 C++ BooleanSum 和 BooleanScalProd。只需使用 Sum 和 ScalProd 即可。
  • 移除了 C++ AddLinMinEquality 和 AddLinMaxEquality。只需使用 AddMinEquality 和 AddMaxEquality 即可。

未来的不兼容问题

  • 在未来的某个时刻，我们将重写 Java 建模层，使其更接近 C++ 层。
  • 在 C++ 建模层中，我们将显式 IntVar(BoolVar var) ctor。
  • 我们正在考虑使 Python API PEP 8 符合要求（使用 snake_case 名称）。如果发生这种情况，我们将提供一个 sed 文件来移植代码。

构建系统

Bazel

  • 修复了 Windows build。

CMake

  • 添加了 FETCH_PYTHON_DEPS 选项（默认为 ON）。
  • 添加了对 GPLK 求解器的可选支持（默认为 -DUSE_GLPK=OFF）。

Python

  • 在大多数 CP-SAT API 中支持 numpy 整数。
  • 修复了缺少 __version__ 的问题。

2021 年 9 月

宣布推出 OR-Tools v9.1

我们发布了 OR-Tools v9.1。如需更新版本，请参阅 OR 工具安装中的相应部分。

平台变更

  • Python：使用 manylinux2014 映像（请参阅 PEP 599）。
  • Python：使用 manylinux2014_aarch64 映像添加对 aarch64 linux 的支持。
  • .Net：添加了 .Net 5.0 支持。

依赖项更新

  • abseil-cpp 20210324.1 -> 20210324.2。
  • Protobuf 3.15.8 -> 3.18.0。
  • SCIP 7.0.1 -> 主节点。
  • Googletest 1.8.0 -> 1.10.0。
  • python：在 cp_model.py 中使用 warning（请参阅 #2530）。
  • python：absl-py 0.11 -> 0.13。

CMake

  • 最低版本要求为 3.14 -> 3.15（请参阅 #2528）。
  • Python：提升所需的最低版本 3.14 -> 3.18（请参阅 #2774）。

制造商

基于 Make 的 build 已被弃用，请改用 CMake 或 Bazel 以从源代码进行构建。

Java

  • 提高了原生库加载器的稳健性（请参阅 #2742）。
  • 修复了处理路由模型或约束求解器时 JVM 垃圾回收器发生崩溃的问题（请参阅 #2091）（请参阅 #2466）。
  • 修复了使用多个 worker 时 CP-SAT 日志记录回调崩溃的问题（请参阅 #2775）。

CP-SAT

  • 提高了 LNS 代码的稳健性（请参阅 #2525）。
  • 改进了调度代码：新增了用于创建固定大小间隔的工厂方法、新的搜索启发法、经过改进的解析和新的线性剪切。
  • 改进路由代码：新的专用 LNS。
  • 改进了模型检查工具。它现在更冷静，尤其是潜在的溢出。
  • 改进 MIP 代码：更好地解析并多项改进 MIP 和 CP 模型的线性放宽。
  • 提高搜索多样性。如果工作器数量超过 12 个，请添加专门用于提高目标下限的工作器。
  • 更改为并行代码：默认情况下，求解器现在将使用所有可用的核心。使用 num_search_parameters 指定并行级别。
  • 废弃了 SearchAllSolutions 和 SolveWithSolutionCallback。
  • Python API：在 model.Add() 调用之外使用 var == ... 或 var != ... 时，进行更细致的检查。

2021 年 4 月

宣布推出 OR-Tools v9.0

我们发布了 OR-Tools v9.0。如需更新版本，请参阅 OR 工具安装中的相应部分。

依赖项更新

Java

bug 修复

  • 改进了使用 CP-SAT 求解器时的多线程处理（请参阅 #1588）。
  • 修复了 Python 封装容器对 std::vector&ltstd::string&gt 的支持（请参阅 #2453）。
  • 重新设计了 CPLEX 支持（请参阅 #2470）。

已知的破坏性更改

  • 在 Python、Java 和 .Net 中添加了日志记录器访问权限（请参阅 #2245）。
  • 将所有自定义 Google 类型替换为 cstdint 中提供的类型。

CP-SAT

  • 废弃了 SearchForAllSolutions()、SearchAllSolutions() 和 SolveWithSolutionCallback() 方法。请改用 Solve()。
  • 改进了 Python 标准运算符支持。这可能会破坏错误的现有代码。

2021 年 3 月

宣布推出 OR-Tools v8.2

我们发布了 OR-Tools v8.2。如需更新版本，请参阅 OR 工具安装中的相应部分。

依赖项更新

  • Abseil-cpp 20200923.2 已更新为 20200923.3 LTS。
  • Protobuf 3.14.0 已更新至 3.15.3。

路由

  • 添加了 RoutingModel.RegisterTransitMatrix() 和 RoutingModel.RegisterUnaryTransitVector()。
  • 将 RoutingModel.AddVectorDimension() 和 RoutingModel.AddMatrixDimension() 的返回值更改为 std::pair&ltint, bool&gt，其 int 为公交评估程序 ID。

2020 年 12 月

宣布推出 OR-Tools v8.1

我们发布了 OR-Tools v8.1。如需更新版本，请参阅 OR 工具安装中的相应部分。

依赖项更新

  • Abseil-cpp 20200923 已更新为 20200923.2 LTS。
  • Protobuf 3.13.0 已更新至 3.14。
  • 添加对 Gurobi 9.1.0 的支持
  • 舍弃 GLog 依赖项（替换为依赖于 abseil-cpp 标志的自定义实现）
  • 丢弃 GFlag 依赖项（替换为 abseil-cpp flag 组件）

bug 修复

  • 修复了 Gurobi 浮动许可双重计数（请参阅 #2227）。
  • 修复了 Windows build（请参阅 #2200）。

2020 年 10 月

发布 OR-Tools v8.0

我们发布了 OR-Tools v8.0。如需更新版本，请参阅 OR 工具安装中的相应部分。

平台变更

  • 添加了对 Python 3.9 的支持 (#2187)
  • 停止了对 Python 3.5 的支持 (#2186) <!-- 正在等待 Microsoft dotnet-sdk 支持，可能会在版本发布后生成...
    • 添加了对 Ubuntu 20.10 的支持 (#2188) -->
  • 不再支持 Ubuntu 16.04 LTS (#2188)
  • 不再支持 Ubuntu 19.10 (#2188)

依赖项更新

  • Abseil-cpp 20200225.2 已更新为 20200923 LTS。
  • Protobuf 3.12.2 已更新至 3.13.0。

已知的破坏性更改

  • 现在，路由和 CP-SAT 源代码会使用一些 C++17 功能。警告：如果您提供自己的 abseil-cpp 版本，请验证它也是基于 C++17 构建的。
  • MPSolver::CreateSolver 签名已更改。模型名称参数已被舍弃。

CMake

  • 修复了使用 -DUSE_SCIP=OFF 时停用 SCIP 支持的问题（请参阅 #2129）。
  • 将示例和示例集成到 CMake 构建系统。注意：可使用 -DBUILD_SAMPLES=OFF 和 -DBUILD_EXAMPLES=OFF 停用。注意：可以使用 -DBUILD_<LANG>_SAMPLES=OFF 或 -DBUILD_<LANG>_EXAMPLES=OFF 针对特定语言停用该功能。
    • 下列中的 <LANG>：
    • CXX,
    • PYTHON,
    • JAVA和
    • DOTNET.

制造商

  • 需要 Make >= 4.3（使用 Make eval 函数）。
  • 需要 CMake >= 3.14（使用 CMake --verbose 选项）。
  • 添加了使用 -DUSE_SCIP=OFF 停用 SCIP 支持的选项（请参阅 #2134）。
  • 添加了使用 -DUSE_COINOR=OFF 停用 CLP 和 CBC 支持的选项。

Java

  • OR-Tools 现在会生成 Maven 软件包（请参阅 #202）。

bug 修复

  • 修复了基于 FreeBSD 的 C++ 和 Python build（请参阅 #2126）。
  • 修复了 Windows 上的调试中的 build（请参阅 #2077）。
  • 修复了 Windows 上 CP-SAT 上长期并行崩溃问题（请参阅 #2001、#2019）。

2020 年 7 月

发布 OR-Tools v7.8

我们发布了 OR-Tools v7.8。如需更新版本，请参阅 OR 工具安装中的相应部分。

依赖项更新

  • Gurobi 9.0.2 现在已预先集成在预构建二进制文件中。它会在 MAC OS X 和 Windows 上的 Gurobi 安装程序的默认安装路径中或在 GUROBI_HOME 目录中搜索 gurobi 90 共享库。
  • SCIP 7.0.1 现在已集成到预构建二进制文件中。在使用之前，请确保符合 SCIP 许可要求。
  • 添加了对可选 Xpress Solver 8.9.0 的支持。

线性求解器

  • 添加了静态 LinearSolver::CreateSolver() 方法，以简化检查对集成线性求解器后端的支持情况。该工具支持所有语言。

bug 修复

  • 修复了 FreeBSD 上基于 CMake 的 build。
  • 修复了累计剪切生成中的 CP-SAT 排序。
  • 修复了 .Net 封装容器中的线性求解器内存泄漏问题。

2020 年 6 月

发布 OR-Tools v7.7

我们发布了 OR-Tools v7.7。如需更新版本，请参阅 OR 工具安装中的相应部分。

依赖项更新

  • Abseil-cpp b832dce 已更新为 c51510d (LTS 20200225.2)。
  • Protobuf 3.11.4 已更新至 3.12.2。

新功能和改进

  • 在可满足性模型（即没有目标）中，CP-SAT 求解器现在会返回 Optimal，而不是 Feasible。
  • 添加了来自 MIP 社区的可行性泵启发式算法。

bug 修复

修复了 CP-SAT 多线程崩溃问题（请参阅 #2005）。

2020 年 4 月

宣布推出 OR-Tools v7.6

我们发布了 OR-Tools v7.6。如需更新版本，请参阅 OR 工具安装中的相应部分。

CP-SAT 新功能

我们向 CP-SAT 求解器添加了以下新功能：

  • 改进了对 LP 的切割平面管理。
  • 调试工具。

依赖项更新

Abseil-cpp 8ba96a8 已更新为 b832dce (LTS 20200225)。

bug 修复

  • 修复了 presolve 中的 CP-SAT UNSAT bug（请参阅 #1908）。
  • 已修复 swigwin.exe 网址。
  • 修复了 Java 和 .Net 的 SWIG 类型映射管理。

2020 年 1 月

宣布推出 OR-Tools v7.5

我们发布了 OR-Tools v7.5。如需更新版本，请参阅 OR 工具安装中的相应部分。

平台变更

  • 添加了对 Python 3.8 的支持 (#1719)
  • 取消了对 Visual Studio 2017 上的源代码的支持编译 (#1852)。
  • 将支持从 Centos 7 更新到了 Centos 8 (#1827)。

依赖项更新

bug 修复

OR-Tools v7.5 中修复了以下问题（如需查看完整列表，请参阅里程碑 v7.5）。

具体而言：

  • 修复了组件加载问题。请参阅 #1421。
  • 公开了 RouteIndexManager 的 GetStartIndex() 和 GetEndIndex() 方法 (#1843)。
  • 修复了 SWIG，以移除损坏的方法（#1838、#1276）。

2019 年 10 月

发布 OR-Tools v7.4

我们发布了 OR-Tools v7.4。如需更新版本，请参阅 OR 工具安装中的相应部分。

新功能和改进

  • CP-SAT 求解器现在会检查不支持强制执行字面量的约束条件。如果此类限制条件具有强制执行字面量，则模型检查工具将在解决之前返回错误。
  • 更好、更快地对路由库进行本地搜索。
  • 线性求解器现在支持第三方软件 Xpress-MP。您需要从源代码重新构建 OR-Tools 才能使用它。
  • NuGet 软件包的架构已被完全重写。具体而言，它现在支持在 Windows 平台上使用 .NET framework 4.5.2 或更高版本。

已弃用的平台

正如 2019 年 7 月的版本说明中所述，OR-Tools 不再支持 Python 2.7。

依赖项更新

Protobuf 3.9.0 已更新至 3.10.0。

2019 年 8 月

宣布推出 OR-Tools v7.3

我们发布了 OR-Tools v7.3。如需更新版本，请参阅 OR 工具安装中的相应部分。

已弃用的平台

为配合 Google 改用 Python 3 的做法，我们即将弃用对 Python 2.7 的支持。这将是支持 Python 2.7 的 OR-Tools 的最后一个版本。

依赖项更新

Protobuf 3.8.0 已更新至 3.9.0。

bug 修复

OR-Tools v7.3 中已修复以下问题。（如需查看完整列表，请参阅 Kanban v7.3）。

具体而言：

  • 修复了 Java 上的 init/int64 类型转换问题 (#1448)。
  • 修复了处理空累计约束条件的解析检查。

2019 年 7 月

宣布推出 OR-Tools v7.2

我们发布了 OR-Tools v7.2。如需更新版本，请参阅 OR 工具安装中的相应部分。

平台变更

  • 为配合 Google 改用 Python 3 的做法，我们即将弃用对 Python 2.7 的支持。最多还会再推出一个支持 Python 2.7 的 OR-Tools 版本。
  • Ubuntu 18.10 已更新至 Ubuntu 19.04。
  • 添加了对从 Visual Studio 2019 上的源代码进行编译的支持。
  • Windows 不再支持 Python 3.5；请使用 Python 3.6 或更高版本。

依赖项更新

  • 我们现在的目标平台是 CBC 2.10.3。
  • 我们现在以 Protobuf 3.8.0 为目标。

CP-SAT

  • 我们对搜索、并行处理和线性放宽进行了多项改进。
  • 在 Python 中添加了 LinearExpr.Sum() 和 LinearExpr.ScalProd() API。
  • 废弃了 C# 中的 IntVar[].Sum() 和 IntVar[].ScalProd() API。
  • C++：移除了 SolveWithModel()，因为它与 SolveCpModel() 重复。
  • 向 Java API 添加了 CpModel.addGreaterThan() 和 CpModel.addLessThan() 方法。

线性求解器

  • 添加了适用于 Python、Java 和 C# 的 MPSolver.SetHint()（受 SCIP 和 Gurobi 支持）。
  • 为 Python、Java 和 C# 添加了 MPSolver.SetNumThreads()（受 CBC、Gurobi 和 SCIP 支持）。
  • 重新编写了对 SCIP 6.0.1 的支持。

参考文档

  • 我们针对所有语言和所有工具（算法、路线、图表、linear_solver 和 CP-SAT）添加了基于 doxygen 和 pdoc3 的参考手册。请参阅 OR-Tools 参考手册。
  • 我们针对 C++（所有产品）和 CP-SAT（C++、Python、Java）提供了参考文档。
  • 我们正在将所有 C++ 文档导出到 Python 和 Java。
  • 缺少 .NET 文档，而且我们在可预见的未来没有改进此问题的解决方案。我们保留它，因为它仍然显示可用的 API。

2019 年 5 月

宣布推出 OR-Tools v7.1

我们发布了 OR-Tools v7.1。如需更新版本，请参阅 OR 工具安装中的相应部分。

对所需依赖项的更改

OR-Tools v7.1 具有以下新依赖项和更新后的依赖项：

  • glog v0.3.5 已更新至 v0.4.0
  • protobuf v3.6.1 已更新至 v3.7.1
  • Cbc 2.9.9 已更新至 2.10.1
  • Cgl 0.59.10 已更新至 0.60.1
  • Clp 1.16.11 已更新至 1.77.1
  • Osi 0.107.9 已更新至 0.108.1
  • CoinUtils 2.10.14 已更新至 2.11.1

CP-SAT API 变更

以下部分介绍了 OR-Tools 7.1 中 CP-SAT API 的更改。

使用网域创建变量

以下示例展示了如何创建具有非连续网域的整数变量。 这将替换已移除的方法 NewEnumeratedIntVar()。此处，变量 x 可以是 1、3、4 或 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");

您也可以使用间隔列表创建变量。如下所示，变量 x 被约束为 1、2、4、5 或 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");

在线性表达式中使用域

以下示例展示了如何限制非连续领域的线性表达式。 此处，线性表达式 linear_expr 基于 5、6、8、9 和 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} }));

使用线性表达式帮助程序

以下示例展示了如何使用辅助方法创建求和和标量积。在下面的示例中，我们需要 x + y == 20 和 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);

2019 年 3 月

发布 OR-Tools v7.0

我们发布了 OR-Tools v7.0。如需更新版本，请参阅 OR 工具安装中的相应部分。

支持的平台变更

OR-Tools v7.0 不再支持以下平台：

  • Visual C++ 2015
  • Ubuntu 14.04
  • Linux 上的 Python 3.4

如果您使用的是上述平台之一，仍然可以安装 OR-Tools v6.10。

对所需依赖项的更改

OR-Tools v7.0 具有以下新依赖项和更新后的依赖项：

以下部分介绍了 OR-Tools 7.0 中的新功能和改进。

路由节目的新索引管理器

在 OR-Tools v7.0 中，车辆路线程序必须使用新的 RoutingIndexManager。这样可确保位置的标准索引与求解器使用的内部索引一致，并有助于防止代码出错。

新的 RoutingIndexManager 需要对路由程序进行一些细微更改，具体如以下部分所述：

包含/导入 RoutingIndexManager

在 OR-Tools 7.0 中，C++ 和 Java 中的路由程序必须包含或导入 RoutingIndexManager，如以下示例所示：

C++

#include "ortools/constraint_solver/routing_index_manager.h"

Java

import com.google.ortools.constraintsolver.RoutingIndexManager;

Python 和 C# 导入内容保持不变。

声明 RoutingIndexManager

在 OR-Tools v7.0 中，路由程序必须声明 RoutingIndexManager 并创建路由模型，如以下示例所示：

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

RoutingIndexManager 的参数如下：

  • 营业地点数量
  • 车辆数量
  • 仓库索引（所有车辆的起点和终点位置）

回调

在 OR-Tools v7.0 中，您需要使用 RoutingIndexManager 创建回调（例如距离回调），然后传递给求解器。以下示例展示了如何创建距离回调。

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

IndexToNode 方法会将求解器使用的内部位置索引转换为距离矩阵的标准索引。

在 v7.0 中，您不是将回调直接传递给求解器，而是在 v7.0 中先创建 transit&nbsp;callback&nbsp;index（即对回调的引用），并将其传递给求解器（在本示例中是通过 SetArcCostEvaluatorOfAllVehicles）。

尺寸

以下示例展示了如何创建需求和容量的维度，该维度用于解决容量车辆路线问题。

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

打印解决方案

在 OR-Tools v7.0 中，您必须使用 RoutingIndexManager 在解决方案中显示车辆路线。以下示例展示了如何以所有支持的语言输出解决方案。

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

支持提供自提和送货服务的 VRP

OR-Tools v7.0 支持解决有关取货和送货的车辆路线问题 (VRP)，其目标是为车队寻找在不同地点取货和配送物品的最短路线。设置该问题的方法与标准 VRP 类似，但您还需要为每个商品指定一对 (i, j) 位置，其中 i 是上车地点，j 是下车点。路线求解器会返回车辆路线，使每个对的 (i, j)、i 和 j 都位于同一路线上，并且车辆在 j 之前访问 i。

如需查看解决此类问题的示例，请参阅使用取件和送货服务规划车辆路线。

支持 lambda 函数

OR-Tools v7.0 现在支持 C# 和 Java 中的 lambda 函数（除了之前已支持的 C++ 和 Python 之外）。Lambda 函数提供了一种在路由程序中定义回调的便捷方式。不过，如果您认为使用标准函数会提高代码的可读性，则可以使用标准函数定义回调。

上面的 C# 和 Java 回调示例说明了如何使用 lambda 函数定义回调。

2018 年 11 月

发布 v6.10 版本

我们发布了 OR-Tools 版本 6.10。如需更新版本，请参阅 OR 工具安装中的相应部分。

以下部分介绍了版本 6.10 中的新功能和改进。

简化了用于构建和运行程序的命令

在 6.10 版中，您可以通过输入如下命令来构建和运行程序：

make run SOURCE=relative/path/to/program.cc
，其中 <var>relative/path/to</var> 是包含相应程序的目录的路径。

若要在不运行程序的情况下构建程序，请输入： 

make build SOURCE=relative/path/to/program.cc
如需了解按语言运行程序的具体说明，请参阅 OR 工具使用入门。

支持 SCIP 6.0.0

OR-Tools 现在支持 SCIP 6.0.0。

二进制文件

二进制发行版已使用 Java JDK 8（适用于 Ubuntu 14.04 的 JDK 7）构建。

CP-SAT 求解器

更新 API

  • 添加了 C++ CP-SAT CpModelBuilder API。

示例

部分示例已迁移。

  • 将社区示例移至 examples/contrib。
  • 将一些示例移至 ortools/<var>component</var>/samples（例如 ortools/linear_solver/samples/simple_program.java）

2018 年 9 月

发布 v6.9 版本

我们发布了 OR-Tools 6.9 版。如需更新版本，请参阅 OR 工具安装中的相应部分。

已更新的依赖项

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

CP-SAT 求解器

  • API 的重大更改 - 如需了解完整详情，请点击此处：
  • 在 Python 中，将 SolveWithSolutionObserver 重命名为 SolveWithSolutionCallback。

  • 在 Python 的 CpSolverSolutionCallback 类中，将 NewSolution 重命名为 OnSolutionCallback。以下示例展示了在 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

  • 在 Python、Java 和 C# 中对解决方案回调公开 StopSearch。点击此处查看文档。

  • 在 Python、Java 和 C# 中公开了 ModelStats 和 CpSolverResponseStats。

  • 完善了 Python 文档字符串文档。 点击此处查看文档。

  • 更新了求解器接口和实战宝典的 Java 实现。

  • 实现模数。

  • 更改 reservoir 的实现：添加带有布尔值的 API，以指定可选的排空/填充事件。

线性求解器

  • 在 Java 和 C# 中公开 InterruptSolve。

CP 求解器

  • 在 C# 中公开了 SolutionCollector Director。

Python

  • 添加了对 Python 3.7 的支持。
  • 从源代码编译时：在检测 Python 时，请优先使用 python3，而不是 python2。

.NET

  • 完全重写 .NET 层。
  • 提供与运行时标识符 win-x64、linux-x64 和 osx-x64 兼容的 Google.OrTools NetStandard 2.0 Nuget 软件包。
  • 提供 Google.OrTools.FSharp Nuget 软件包。
  • 为所有 .NET 示例添加项目文件。
  • 将所有 F# 脚本示例 (.fsx) 更新为常规 F# 项目 (.fs)。
  • 在此处添加有关 .NET 软件包 build 生成的文档。

扁平锌

  • 在 Flatzinc 中添加了对集的支持（使用 nosets.mzn）。

贡献数量

  • 添加了对 Binder 的支持。 感谢 Kevin Mader。
  • 将 DecisionVisitor 设为 Java 绑定中的总监类型。 感谢 Jeremy Apthorp。

2018 年 7 月

发布 v6.8 版本

我们发布了 OR-Tools 6.8 版。如需更新版本，请参阅 OR 工具安装中的相应部分。

CP-SAT 求解器正式推出

CP-SAT 求解器是用于约束编程的新求解器。CP-SAT 求解器比原始 CP 求解器更快，应优先用于 CP 问题。

如需查看使用 CP-SAT 求解器的示例，请在 GitHub 上的 examples 目录中查找名称中含有 _sat 的文件。

原始 CP 求解器将继续维护一段时间，以支持现有代码，但已废弃。

CP-SAT 求解器的新选项

此版本中新增了以下 CP-SAT 求解器选项：

  • 本地社区搜索 (LNS)：使用 SatParameters.use_lns 选项启用 LNS。
  • 并行搜索：使用 SatParameters.num_search_workers 选项在搜索期间启用多个线程。每个线程可以有不同的参数和不同的随机种子。这样可以最大限度提高多样性，并提高至少一个线程找到解的概率。

改进了求解器的性能

我们对 CP-SAT 和 Glop 求解器的性能进行了改进。

2018 年 3 月

发布 v6.7 版本

我们发布了 OR-Tools 版本 6.7。如需更新版本，请参阅 OR 工具安装中的相应部分。

更新为必需依赖项

  • Protobuf 3.5.0 -> 3.5.1。

其他

  • 重构了基础以准备 abseil-cpp 集成。
  • 使用 Travis CI 和 Appveyor 持续集成 (CI) 服务。

SAT

  • 提升了性能。
  • 改进了 Python API。
  • 添加了 C# API，也称为 CpSolver.cs（实验性）。

Glop

  • 代码重构。
  • 提升了性能。

CMake 支持（实验性）

  • 添加了 C++ OR-Tools CMake 支持。
  • 能够将 OR-Tools 构建为独立的 CMake 项目。
  • 能够将 OR-Tools 合并到现有的 CMake 项目中。
  • 添加 Python OR-Tools 基于 CMake 的 build。
  • 使用 CMake 生成 Python 软件包 (wheel)。

贡献数量

  • 修复了窗口上的 winsock2.h 重新定义问题。 感谢 Florent Tollin de Rivarol。
  • 添加 F# 支持（实验性）。 感谢 Matthew Moore。 注意：仅适用于 Makefile 构建器。
  • 添加了 .NET 标准支持（实验性）。感谢 Ziad El Malki。 注意：仅适用于 Makefile 构建器。

2017 年 11 月

发布 v6.6 版本

我们发布了 OR-Tools 版本 6.6。如需更新版本，请参阅 OR 工具安装中的相应部分。

所需依赖项的更新

  • Protobuf 到 3.3.0 -> 3.5.0。
  • gflag 更改为 2.2.0 -> 2.2.1。
  • CBC 2.9.8 -> 2.9.9。
  • 添加 Python 模块六 (1.10) 作为 Python 的必需依赖项。

bug 修复

  • 拉取请求 #494 名称重构。在某些编辑器中为 IntelliSense 添加注释。 感谢 Matthew Moore。
  • 拉取请求 #516 F# 独立二进制文件的说明。 感谢 Matthew Moore。
  • 提高了 Glop 中的精确度。

SAT 求解器

  • 改进了内部 SAT 求解器、修复了各种错误。
  • 向与 LP 求解器关联的 SAT 求解器添加 VRP 限制条件。
  • 更改 SAT 求解器中的解观察器，以接受 CpSolverResponse 作为参数。
  • 改进了 Glop 在 SAT 求解器中的使用。
  • 加快 SAT-LP 连接。
  • 向 SAT cp_model protobuf 格式添加了 Reservoir 约束条件。

SAT/Python

示例

  • 重写 rcpsp_parser，以使用 ProtoBuf 格式存储问题。
  • 改进了 RCPSP 解析器。

2017 年 10 月

发布 v6.5 版本

我们发布了 OR-Tools 版本 6.5。如需更新版本，请参阅 OR 工具安装中的相应部分。

平台变更

  • pypi 模块 py3-ortools 已合并到 ortools 模块中。现在只有一个模块：“ortools”。
  • 现在，这些 Python 模块的主要格式是 wheel 文件。如需从 pypi 安装适用于 Python 的 OR-Tools，只需运行 pip install ortools 即可。您需要安装最新版本的 pip（9.0.1 及更高版本）。这将拉取最新版本 (v6.5)。

错误已纠正

protobuf jar 文件现在可以使用编译的类正确构建。

新示例

  • 更多 F# 示例已贡献到示例/fsharp 目录中（再次感谢 Matthew Moore）。
  • 开发者也贡献了 Java MIP 示例（谢谢 Darian）。

2017 年 9 月

发布 v6.4 版本

我们发布了 OR-Tools 版本 6.4。如需更新版本，请参阅 OR 工具安装中的相应部分。

平台变更

  • Linux 平台上的 Pypi 模块现在使用 manylinux1 标记，以 wheel 文件的形式提供。感谢 Federico Ficarelli。 进行此更改后，我们回溯了 2017 年 7 月版本中引入的基于 Linux 的模块。

新功能

  • 改进了 GLOP 内使用的缩放方法。
  • 修复了 C# 路由库中评估器的封装问题。感谢 DevNamedZed 的感谢。
  • 提高了大型模型 Flatzinc presolve 的性能。
  • 默认情况下使用 SAT 支持的 Flatzinc。
  • 提高了 sat 求解器基于 Core 方法的性能。
  • 修复了线性分配算法中错误失败的 bug。
  • 在 ortools/examples/fsharp 中添加了 F# 示例。
  • 取消了对路由库中的正向惩罚的检查。

2017 年 8 月

发布 v6.3 版本

我们发布了 OR-Tools 版本 6.3。如需更新版本，请参阅 OR 工具安装中的相应部分。

新下载文件

您现在可以在 OR-工具发布页面中下载适用于 Linux 的 Python wheel 文件，以及所有下载内容的最新版本。

Minizinc 求解器

此版本包含针对 Minzinc 2017 挑战发送的最终 sat 和 Flatzinc 代码。

2017 年 7 月

发布 v6.2 版本

我们发布了 OR-Tools 版本 6.2。如需更新版本，请参阅 OR 工具安装中的相应部分。

平台变更

  • 我们现在支持多个 Linux 二进制发行版（Ubuntu 14.04、16.04、17.04、CentOS 7、Debian 9）。
  • Linux 平台上的 Pypi 模块现在包含一个描述发行版的标记（ubuntu-14.04、ubuntu-16.04、ubuntu-17.04、centos-7、debian-9）。

新功能

我们添加了对 Docker 来构建 Linux 工件的支持。转到 or-tools/tools/docker 并查看 Makefile 以查看可能的目标（make archive、make pypi 和 make pypi3）。

这些命令将创建一个 export 子目录，并在其中添加二进制文件工件。

2017 年 6 月

发布 v6.1 版本

我们发布了 OR-Tools 版本 6.1。如需更新版本，请参阅 OR 工具安装中的相应部分。

平台变更

  • 支持 Visual Studio 2017；不再支持 Visual Studio 2013。
  • 支持 macOS 版本 10.9 及更高版本。

新功能

我们为 CP-SAT 求解器添加了新的 protobuf 格式。请参阅 ortools/sat/cp_model.proto 来定义您的模型，并参阅 ortools/sat/cp_model_solver.h 以解决您的问题。

bug 修复

问题 420：我们修复了所有平台上的 Python pypi 模块上缺少 __version__ 属性的问题。

2017 年 5 月

发布 v6.0 版本

我们发布了 OR-Tools 6.0 版。如需更新版本，请参阅 OR 工具安装中的相应部分。

使用 C++ 实现新的目录结构

我们更改了使用 C++ 时 OR-Tools 的来源/包含结构。目标是更好地封装 C++ include 文件。它还具有使 C++ 和 Python 目录结构保持一致的优势。

  • src/ 已重命名为 ortools/。
  • 现在，C++ 文件中的所有 #include 命令都会添加前缀 ortools。#include "constraint/constraint_solver.h" 现为 #include "ortools/constraint/constraint_solver.h"。

新功能

  • Bazel 支持。 您现在可以使用 Google 的构建工具 bazel 构建 OR 工具。该操作系统可在 Linux 和 Mac OS X 上运行。下载 Bazel 0.4.5 或更高版本后，将目录更改为 or-tools，并构建示例：bazel build examples/cpp/...。

路由

我们在路线库中实现了对休息时间（例如，司机吃午餐导致车辆停工）的支持。此功能如 cvrptw_with_breaks.cc 示例所示。

SCIP 支持

线性求解器封装容器现在支持 SCIP 4.0。现在，您需要先构建 SCIP，然后告知或工具您将使用它。如需查看相关说明，请点击此处。

GLPK 支持

我们还改变了使用 GLPK 进行构建的方式。有关详情，请参阅此处。

清理

  • 在 C++ 代码库中，我们移除了对 hash_map 和 hash_set 的所有使用；因为它们已废弃。它们已替换为 STL 中的 unordered_map 和 unordered_set。
  • 清理了 C# Makefile，由 Michael Powell 提供。

2017 年 1 月

发布 v5.1 版本

我们发布了 OR-Tools 5.1 版。如需更新版本，请参阅 OR 工具安装中的相应部分。

新功能

正在安装

路由

实现了一种算法，针对对称旅行推销员问题计算 Held-Karp 下限。这样，您可以计算潜在非最优解决方案的费用与最佳解决方案的费用之间的差值上限。

调度

周六求解器

提升了性能

  • SAT 求解器 - 提高了 Sat 求解器的性能，尤其是针对累计约束条件。
  • Glop 求解器 - 提高了 Glop 求解器的数值稳健性，它现在可以为硬数值问题返回更准确的解。
  • Flatzinc 求解器
  • 极大地提升了 Flatzinc 解释器的 Sat 后端的性能。
  • 简化了 C# Flatzinc 接口。如需查看新界面的示例，请参阅 https://github.com/google/or-tools/blob/master/examples/csharp/csfz.cs。

bug 修复

  • 对具有单一车辆和侧边约束的路线模型使用 PathCheapestArc 启发法有时会导致求解器运行时间过长。通过正确考虑侧边约束条件，该问题已得到修复。
  • 在 Java 中，在解决车辆路线问题时，路线求解器有时会崩溃。此问题已在最新版本中修复。

2016 年 11 月

发布 v5.0 版本

我们发布了 OR-Tools 5.0 版。如需更新版本，请参阅 OR 工具安装中的相应部分。

运行示例

  • 引入了特定于语言的目标（可让您更轻松地编译和运行程序），以及 OR 工具附带的示例。

周六

FlatZinc

约束求解器

路由

  • 实现了 AddAtSolutionCallback，每次搜索期间找到解决方案时都会调用该回调。
  • 移除了 RoutingModel 无仓库构造函数。现在，必须在路线模型中指定至少一个仓库。

2016 年 9 月

发布 v4.4 版本

我们发布了 OR-Tools 版本 4.4。如需更新版本，请参阅 OR 工具安装中的相应部分。

周六

  • 扩展了调度 API 和修改了使用它的样本（大于 加权的 tardiness_sat 和 jobshop_sat）。

图表

  • 向 Graph 类添加了迭代器 trait。

OR-Tools 分发

  • 再次支持 Nuget 软件包。

2016 年 8 月

发布 v4.3 版本

我们发布了 OR-Tools 版本 4.3。如需更新版本，请参阅 OR 工具安装中的相应部分。

约束求解器

  • 实现了 NotBetween 方法，可将变量限制为在给定时间间隔之外。

汇款路线

  • 添加了模型的解析，以检查现有 NotMember 约束条件（如此示例所示），并在本地搜索过滤器中使用这些约束条件。
  • 添加了本地搜索性能分析。
  • 修复了本地迁移问题。

线性求解器

  • 修复了 SCIP 状态报告。

周六

Glop

  • 在更多计算阶段利用稀疏性提高了性能。

扁平锌

  • 修复了 minizinc 挑战发现的 bug。

Lp_data

  • 持续简化迭代器中的模板。

OR-Tools 分发

  • 现在，默认情况下，C# 程序集具有强命名方式。
  • 已升级到 Protobuf3.0.0。
  • 添加了 Python 脚本以检查 OR-Tools 归档依赖项。

2016 年 7 月

发布 v4.2 版本

我们发布了 OR-Tools 4.2 版。如需更新版本，请参阅 OR 工具安装中的相应部分。

约束求解器（路由）

  • 现在可以使用基数定义析取，基数是此析取中可以处于活动状态的节点的数量上限。例如，如果您添加具有 n 个节点且基数为 k 的析取，则 n 个节点中的 k 个节点可处于活跃状态。为此，您可以使用 AddDisjunction 的新定义。
  • 添加了对每个节点多个析取运算的支持。例如，您现在可以将节点 N1 添加到多个析取运算 (D1..Dm)。这样就可以提高其在上述任一产品中的投放几率。 针对分离时间窗口相关问题引入了更快的路由搜索算法。
  • 向路由模型参数添加了约束求解器参数，并为路由搜索参数添加了 log_search。
  • 本地搜索算法可以更快地解决时间窗口不相交的问题。如需了解详情，请参阅 cvrp_disjoint_tw.cc 示例。

Glop（线性优化）

  • 引入了更快的单纯算法。

OR-Tools 分发

  • 每个平台一个归档，而不是针对每个 C++、Java 和 .Net 分别归档。Python 归档仍托管在 pypi 上。
  • 在 pypi 中，我们已在 Mac OS X 和 Windows 上切换到 wheel (.whl) 模块。 引入了 MAJOR.MINOR 编号架构。这些编号用于归档名称、存储在 Mac OS X 共享库中的版本、Python 模块和 .NET 程序集。我们发布的第一个具有此架构的版本为 v4.2

2016 年 6 月

发布版本 v2016-06

我们发布了 OR-Tools 版本 v2016-06。如需更新版本，请参阅 OR 工具安装中的相应部分。

约束求解器

  • 从 CP 库中移除了大多数回调实例 (src/base/callback.h)。
  • 添加了 NotMemberCt（变量不能属于一组间隔）。

路由库

  • 不兼容的更改：如需在 AddDimensionWithVehicleCapacity 中指定车辆的容量，您现在需要传递数组（c++ 中的矢量）而不是回调。

GLOP

  • 更改稀疏矩阵的内部表示法。
  • 提升了性能。

图表

  • 重写了 Dijkstra 和 Bellman-Ford 算法，以通过 std::function (C++) 替换回调。
  • 更改了在遍历弧线和节点时不同图表实现的 API。

周六

  • 移除未使用的核心方法（解析节点）。
  • 添加了 drat writer，用于检查不符合要求的证明。
  • 添加预处理器。

波普

  • 添加新社区。

示例

  • c++：在示例中去掉了 filelineloader。
  • data：添加单机调度问题。

文档

2016 年 4 月

发布版本 v2016-04

我们发布了 OR-Tools 版本 v2016-04。如需更新版本，请参阅 OR 工具安装中的相应部分。

已更新的依赖项

2015 年 12 月

发布版本 v2015-12

我们发布了 OR-Tools 版本 v2015-12。如需更新版本，请参阅 OR 工具安装中的相应部分。

约束求解器

  • 破坏了 CP 求解器中大型社区搜索的兼容性（请参阅 examples/cpp/ls_api.cc、examples/python/pyls_api.py、examples/csharp/csls_api.cs 和 examples/com/google/ortools/sample/LsApi.java 查看新的 API）。
  • 清理了 Python 封装。在 CP 求解器中支持自定义决策（如需了解 API 的实际运用，请参阅 examples/test/test_cp_api.py）。
  • 各项改进和问题修复。

2015 年 9 月

在 GitHub 上发布第一个版本。

从现在开始，文件就会存储在此处。

扁平锌

  • 为 Flatzinc 解释器添加了二进制文件归档（请参阅 www.minizinc.org）。
  • 对挑战中使用的版本进行了一些修复。