标签: or-tools

I am currently evaluating googles or-tools and just noticed that it's not really a solver on its own but mainly an interface to other solvers. What I'd like to know is which solvers this framework uses for constraint and routing problems.

I have already looked thoroughly through https://developers.google.com/optimization/, but only found that

• for linear optimization Google's "in-house, open-source GLOP" is used
• for network flow optimization an own solver seems to be used ("OR-Tools provides several solvers for network flow …

我正在使用ORTOOLS库来解决 VRP 问题。我给它一个初始可行的解决方案来解决我的问题，满足我的问题的所有约束，但不是最优的。然后 ORTOOLS 执行 GUIDED_LOCAL_SEARCH 启发式，不断扰乱我的解决方案的一部分（有时可能使其不可行），直到它有望达到比我的初始解决方案更好的解决方案。

为什么要使用约束规划求解器？我的理解是，经典的约束规划从一个不可行（可能为空）的解决方案开始，传播约束以缩小我的变量的域，直到达到静止状态，然后做出决定。然后它再次迭代，直到解决问题或在到达死胡同时回溯（想想数独）。

在进行小扰动时，这些能力（传播、回溯）以什么方式需要？

我目前正在研究 MiniZinc，并且我一直在使用 MiniZinc 中集成的两个求解器运行我的模型：Gecode 和 Chuffed。我一直在 IDE 中运行它，但我知道它也可以在 bash 中运行（使用minizinc命令）。

但我想测试我的模型如何使用 Google 的 CP 求解器，称为 OR-Tools。但我真的不知道怎么做。我在 Ubuntu 18.04 中安装了 MiniZinc snap，但我可以下载 MiniZinc 的新目录并在本地运行它，并在那里配置求解器（而不是在 snap 安装中，因为 snap 目录无法修改）。

我需要一种方法来安装 OR-Tools 并使其至少在终端中工作（但从 IDE 运行它会很完美）。

我当时正在开发一个示例 MIP 程序，该程序选择了男女混合运动队的首发阵容，并发现了一个在 Google OR 工具中得出非最佳结果的小示例。

基础知识：从 n>5 名玩家组成的团队中选择 5 名首发。至少两名首发必须是女性。被划伤的玩家无法启动。目标函数是初学者技能水平的简单总和。代码是：

import pandas as pd
from ortools.linear_solver import pywraplp

# %% Read the data from an external file
pname   = ["Tom", "Joe", "Bill", "Mike", "Frank", "Mary", "Sue", "JoAnn"]
skill   = [ 11.0,  13.0,   11.0,   12.0,    14.0,   10.0,  10.0,     7.0]
female  = [    0,     0,      0,      0,       0,      1,     1,       1]
scratch = [    0,     0,      0,      0,       1,      0,     0,       0]

# %% Create the mip solver with the SCIP …

mvn install后生成jar。无法在 Windows 上使用 Loader.loadNativeLibraries()。

ortools的版本是9.0.9048。我在windows上用过。我将以下两个 jar 添加到项目中，并按照链接所述添加它们。

然后这两个jar就在IDEA的这里了。

pom文件如下：

然后我就可以在IDEA中正常运行程序了。但是当我 mvn install 生成 jar 文件并通过 'java -jar jarfile.jar' 运行 jar 时，出现错误：

它说 java.nio.file.NoSuchFileException: /BOOT-INF/lib/ortools-win32-9.0.jar!/win32-x86-64/ ，但是当我在 winrar 中打开 jar 时，它存在。

有谁知道原因吗？

我尝试使用 cmake 在本地构建 ORTools github 包，并且构建没有任何错误。然而，我们计划最终使用的环境没有出站网络连接。我看到的问题是https://github.com/google/or-tools/blob/v9.4/cmake/dependency/CMakeLists.txt执行 Git 克隆来下载依赖项并添加它们。由于没有出站网络访问，此步骤失败，我无法构建依赖关系。为了避免这种情况，我们计划手动下载依赖项并将其添加到https://github.com/google/or-tools/blob/v9.4/cmake/dependency/文件夹中。我对 CMake 还很陌生，我不确定需要进行哪些更改才能适应这一点。

例如，如果我克隆 Zlib v1.2.11 存储库并将其添加到https://github.com/google/or-tools/blob/v9.4/cmake/dependency/，则以下代码片段需要更改为什么？

# ##############################################################################
# ZLIB
# ##############################################################################
if(BUILD_ZLIB)
  message(CHECK_START "Fetching ZLIB")
  list(APPEND CMAKE_MESSAGE_INDENT "  ")
  FetchContent_Declare(
    zlib
    GIT_REPOSITORY "https://github.com/madler/ZLIB.git"
    GIT_TAG "v1.2.11"
    PATCH_COMMAND git apply --ignore-whitespace "${CMAKE_CURRENT_LIST_DIR}/../../patches/ZLIB.patch")
  FetchContent_MakeAvailable(zlib)
  list(POP_BACK CMAKE_MESSAGE_INDENT)
  message(CHECK_PASS "fetched")
endif()

FetchContent_Declare 可用于指向已包含源文件的目录吗？还有什么选择呢？

我一直在使用 Google OR-tools 并尝试遵循他们的示例来解决调度问题。然而，python 文档有时很难理解，更复杂的例子 ( https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py ) 没有很好地描述。

我希望能够对员工的轮班工作量设置硬限制和软限制。在上面的例子中，我相信这个函数add_soft_sum_constraint()（我已经把它的确切代码放在下面）做了我想做的事情。我想复制它的功能，但我不明白它是如何做到的。

在 2 if 语句中，我不确定delta和excess变量代表什么，以及为什么它们要添加更多约束，而不是仅向 2 个成本列表添加更多约束，这将在稍后最小化目标时使用。

如果有人对此示例有任何见解，我将不胜感激，谢谢。

def add_soft_sum_constraint(model, works, hard_min, soft_min, min_cost,
                        soft_max, hard_max, max_cost, prefix):

cost_variables = []
cost_coefficients = []
sum_var = model.NewIntVar(hard_min, hard_max, '')
# This adds the hard constraints on the sum.
model.Add(sum_var == sum(works))

# Penalize sums below the soft_min target.
if soft_min > hard_min and min_cost > 0:
    delta = model.NewIntVar(-len(works), len(works), '')
    model.Add(delta == soft_min - …

我有一个问题，我有一组具有给定生产能力的仓库，它们以给定的成本将一些产品发送给客户列表。我试图将发送产品的总成本降至最低，以便满足每个客户的需求。那部分是排序的。

现在我需要添加一个新的目标（或约束），我尝试以最低的成本满足所有客户的需求，同时尽可能使用最少的仓库数量。假设从 5 个仓库开始，如果问题是不可能的，则尝试 6、7、8 等，直到找到解决方案，如果我使用尽可能少的仓库数量来满足所有需求。

我如何使用 or-tool 约束编程模块来解决这个问题？甚至有可能吗？我仔细查看了文档，但找不到任何似乎符合这个想法的约束或函数。

我有一个优化问题，我有一个“BoolVar”对象列表的列表。所以像这样：

[[BoolVar1,BoolVar2],[BoolVar3, BoolVar4],[BoolVar5,BoolVar6]]

我需要评估以下内容：

(BoolVar1 && BoolVar2) || (BoolVar3 && BoolVar4) || (BoolVar5 && BoolVar6)

我是否必须按如下方式执行此操作：

and12 = model.NewBoolVar("and12")
model.Add(and12 == True).OnlyEnforceIf([BoolVar1,BoolVar2])
and34 = model.NewBoolVar("and34")
model.Add(and34 == True).OnlyEnforceIf([BoolVar3,BoolVar4])
and56 = model.NewBoolVar("and56")
model.Add(and56 == True).OnlyEnforceIf([BoolVar5,BoolVar6])
model.AddBoolOr([and12,and34,and56])

我已经尝试过这段代码，它似乎有效，但由于“OnlyEnforceIf”功能，我对此表示怀疑。如果不强制执行会怎样？那么 and12 是否设置为 False，或者可以是 False 或 True，因为此后该等式不再强制执行？我根据这篇文章找到了这段代码。

我有一组U用户和一组S服务器。我想最大化分配给服务器的用户数量，同时最小化使用的服务器数量（这意味着我有两个目标函数）。

每个用户都有一些需求w ，每个服务器的总容量为C。

求解器变量如下：

# x[i,j] = True if user u[j] is allocated to server s[i]
# x[i,j] = False otherwise

# y[i] = True if server s[i] is used to serve users
# y[i] = False otherwise

如前所述，我想最大化x[i,j]，同时最小化y[i]

限制如下：

• 容量约束：由于每台服务器i都有一定的容量，因此分配的j个用户不得超过该容量
• 邻近约束：只有位于服务器范围内的用户才能分配给它。一个用户可以位于多个服务器的重叠范围内
• 约束系列：确保每个用户最多分配到一台服务器。

使用这个库

from ortools.sat.python import cp_model

到目前为止我已经做了：

• 创建求解器变量（它们是布尔值）
• 创建约束
• 最大化 x[i,j] 变量
• 获取目标函数

例如，如果我有 10 个用户和 4 台服务器，则所有 10 个用户都分配到 4 台服务器中

我需要但未能完成的事情：

• 最大化x[i,j] …