标签: or-tools

在 Docker 中，我尝试运行 pip install ortools 但找不到。其他 pip 安装包可以完美运行。我在 Dockerfile 中使用“FROM python:3.6.8-alpine”

bash-4.4# pip install ortools
Collecting ortools
  ERROR: Could not find a version that satisfies the requirement ortools (from versions: none)
ERROR: No matching distribution found for ortools


bash-4.4# pip install --upgrade pip
Requirement already up-to-date: pip in /usr/local/lib/python3.6/site-packages (19.1.1)

根本原因： Gooogle OR 工具不支持 alpine，因为 alpine 不支持 pypi

关注此问题的进展：https://github.com/google/or-tools/issues/756

模型目标的一部分由标量列表中的项目加权。

我通过使用 0-1 范围变量的列表来解决这个问题，然后使用 LinearExpr.ScalProd 对目标进行加权。

有没有办法只用一个整数变量（目标变量除外）来做到这一点，我可以使用 lambda 或其他一些机制来查找表中变量的值？

这是我有的一些示例代码，尽管我试图确定它可以变得更简洁。

def argmax(
    model: cp_model.CpModel, values: List[int]
) -> Tuple[List[cp_model.IntVar], cp_model.IntVar]:
    objective_var = model.NewIntVar(0, 1000000, "objective_var")
    ret_vars = [model.NewIntVar(0, 1, "x(%i)" % i) for i in range(len(values))]
    model.Add(sum(ret_vars) == 1)
    model.Add(objective_var == cp_model.LinearExpr.ScalProd(ret_vars, values))

    return [ret_vars, objective_var]

我正在使用 CP-Sat 求解器来优化我正在制定的时间表。然而，现在这个问题需要很长时间才能解决。是否可以用旧结果为求解器提供种子，作为起点，以减少找到最佳结果所需的时间？

我正在研究路线优化问题，但我发现自己陷入了一些僵局。我正在使用 or-tools 作为具有 .Net 核心的求解器。

问题如下：当我处理时间窗口约束时，可能需要一些等待以适应某个位置时间窗口。这很好。求解器倾向于使用时间窗口约束位置作为第一个节点。这也很好。但是这样我们可能想把车辆的出发日期加上一些完美的延迟。因此，当我将路线持续时间限制设置为 8 小时，并且我们在开始时等待 2 小时，结果我们以 6 小时的工作结束，这不是最佳选择。我不知道如何通知求解器第一个节点等待时间正在增加总持续时间。

这是文档链接：https : //developers.google.com/optimization/routing/vrp

// 这是我的时间维度

        _routingModel.AddDimension(
            evaluator_index: _absoluteTimeCallbackIndex,
            slack_max: (long)TimeSpan.FromDays(1).TotalSeconds,
            capacity: (long)TimeSpan.FromDays(1).TotalSeconds,
            fix_start_cumul_to_zero: true,
            name: PlannerConstants.TIME_DIMENSION_NAME);

// 这段代码是设置时间窗口和持续时间约束

        var timeDimension = _routingModel.GetDimensionOrDie(PlannerConstants.TIME_DIMENSION_NAME);

        for (int locationNodeIndex = 0; locationNodeIndex < _targets.Count; locationNodeIndex++)
        {
            var location = _targets[locationNodeIndex].Location;
            var index = _manager.NodeToIndex(locationNodeIndex);

            var timeWindowMatch = new TimeWindowMatcher(_departureDate, location.TimeSlots.ToList())
                .GetTimeWindowsWithGaps();

            var start = (long)timeWindowMatch.WideTimeRange.From.TotalSeconds;
            var end = (long)timeWindowMatch.WideTimeRange.To.TotalSeconds;

            timeDimension
                .CumulVar(index)
                .SetRange(start, end);

            timeWindowMatch.TimeGaps.ForEach(gap =>
            {
                timeDimension
                    .CumulVar(index)
                    .RemoveInterval((long)gap.From.TotalSeconds, (long)gap.To.TotalSeconds);
            }); …

我正在使用 OR-Tool 来解决 VRP 问题。我已经对文档中的示例问题进行了一些实验，并设法编写了一个正常运行的程序，但是，我不明白 SetGlobalSpanCostCoefficient 的目的以及如何正确设置它。根据该站点，它是全局跨度成本与所有路线中最大和最小尺寸值之间的差异之间的系数。那么，这个全局成本是所有路线成本的总和吗，它是从维度的“容量”参数计算出来的，并像最大容量限制器一样使用。

我的代码中的问题是，除非我手动调整 AddDimension 函数中的容量（最大路线距离）和 globalSpanCostcoefficient，否则不会使用 somme vihecles。我有 1000 个节点： 距离分布（以米为单位）如下所示：

    # Add Distance constraint.
    distance_dimension_name = 'Distance'
    routing.AddDimension(
        transit_callback_index,
        0,  # no slack
        25000,  # vehicle maximum travel distance
        True,  # start cumul to zero
        distance_dimension_name)
    distance_dimension = routing.GetDimensionOrDie(distance_dimension_name)
    distance_dimension.SetGlobalSpanCostCoefficient(100)

在这里，我得到了 2610m 的最大路线距离，有 5 辆和 6 辆汽车，它聚集在两条路线上。我试图添加一个像这里描述的计数维度，但即使对于 100 个节点它也变得太慢，并且结果与 5 辆车相同。

我想知道如何使用 or-tools 定义复杂的目标函数（如果可能的话）。

下面的基本示例展示了如何使用 python 中的 Or-tools 解决基本线性问题：

solver = pywraplp.Solver('lp_pricing_problem', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)

# Define variables with a range from 0 to 1000.
x = solver.NumVar(0, 1000, 'Variable_x')
y = solver.NumVar(0, 1000, 'Variable_y')

# Define some constraints.
solver.Add(x >= 17)
solver.Add(x <= 147)
solver.Add(y >= 61)
solver.Add(y <= 93)

# Minimize 0.5*x + 2*y
objective = solver.Objective()
objective.SetCoefficient(x, 0.5)
objective.SetCoefficient(y, 2)
objective.SetMinimization()

status = solver.Solve()

# Print the solution
if status == solver.OPTIMAL:
    print("x: {}, y: {}".format(x.solution_value(), y.solution_value())) # x: 17.0, …

我正在重新使用 Google 的 OR 工具并尝试（相对）简单的优化。我正在使用 CP SAT 求解器，但我可能在这里遗漏了一些基本内容。我有一些变量 x、y 和一些常量 c。如果 y 小于 c，我希望 x 等于 1，否则等于 0。

from ortools.sat.python import cp_model

solver = cp_model.CpSolver()
model = cp_model.CpModel()
c = 50
x = model.NewBoolVar(name='x')
y = model.NewIntVar(name='y', lb=0, ub=2**10)

model.Add(x == (y < c))

model.Maximize(x+y)

status = solver.Solve(model)

我收到一条错误消息

TypeError: bad operand type for unary -: 'BoundedLinearExpression'

看来我在这里滥用 OR 工具语法来限制我的约束。我很难理解在线 OR 工具的文档，而且我似乎忘记的东西比我想象的要多得多。

我有一个使用 Google 的 OR Tools python 库实现的有效车辆路由问题（带时间窗口）解决方案。我有一个包含 15 个位置的时间矩阵以及每个位置的时间窗口。我还将访问每个地点的持续时间纳入每次访问的费用中。所有值均以秒为单位。我有意只用一辆车来解决这个问题（本质上是解决旅行推销员问题）。

如果位置阻止创建有效的解决方案，我不会尝试添加从解决方案中删除位置的功能。现在，如果我将每次访问的持续时间设置为 3600 秒，则无法访问所有 15 个位置。但是，如果我将每次访问的持续时间设置为 900 秒，那么所有 15 个位置都可以找到解决方案。我想添加一个析取项，以允许在这些较长的持续时间内创建解决方案，并且只需从解决方案中删除一个位置即可避免失败。

我不想从解决方案中删除一些位置，因此我给了它们极大的惩罚以确保它们不会被删除，而其他位置我则指定为零的惩罚。但现在，所有其他地点都被放弃，因为它们的罚款为零 - 我认为这是因为罚款小于交通成本，但我不完全确定这是否确实是原因。我应该如何允许从解决方案中删除位置，但防止其他位置可删除？

现在我添加的唯一代码是：

# Allow to drop nodes.
for node in range(1, len(Penalties)):
  routing.AddDisjunction([manager.NodeToIndex(node)], Penalties[node])

来源

from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2

Matrix = [
  [0, 557, 763, 813, 618, 822, 700, 1527, 112, 1011, 734, 551, 604, 1156, 732],             # Depot
  [523, 0, 598, 934, 607, 658, 535, 1529, 589, 857, 424, 475, …

我正在使用 Google 的 OR-Tools 来解决 VRPtw 问题，并努力思考日志。
我向解算器提供一定数量的访问点和车辆。我不知道这需要多少时间，也就是说，甚至时间的尺度。
我们有什么办法可以获取进度信息吗？
我知道有一个 SearchLog 类（https://developers.google.com/optimization/reference/constraint_solver/constraint_solveri/SearchLog）。但我不明白这能给我我想要的信息。

我正在尝试使用 Google OR-Tools 的 CP-Solver 解决问题。是否可以添加这样的约束： x1 XOR x2 XOR x3 == 0 提前致谢。