标签: or-tools

我是 SAT 求解器的新手，需要一些有关以下问题的指导。

考虑到：

? 我在 4*4 网格中选择了 14 个相邻的单元格

? 我有 5 个多联骨牌（A、B、C、D、E），大小分别为 4、2、5、2 和 1

? 这些多联骨是自由的，即它们的形状不是固定的，可以形成不同的图案。

如何使用 SAT 求解器计算所选区域（灰色单元格）内这 5 个自由多联骨牌的所有可能组合？

借用@spinkus 有见地的答案和 OR-tools 文档，我可以制作以下示例代码（在 Jupyter Notebook 中运行）：

from ortools.sat.python import cp_model

import numpy as np
import more_itertools as mit
import matplotlib.pyplot as plt
%matplotlib inline


W, H = 4, 4 #Dimensions of grid
sizes = (4, 2, 5, 2, 1) #Size of each polyomino
labels = np.arange(len(sizes))  #Label of each …

我有一组很多(10000+)项,我必须从中选择20项.我只能选择一个项目.我的项目有利润和成本,以及几个布尔属性(如颜色).

我已阅读并阅读了https://developers.google.com/optimization/mip/integer_opt_cp和https://developers.google.com/optimization/mip/integer_opt中的教程,但我的约束与那些略有不同在那里.

每个项目都表示为一个元组:

item = ('item name', cost, profit, is_blue)

举个例子

vase = ['Ming Vase', 1000, 10000, 0]

plate = ['China Plate', 10, 5, 1]

并且项目的总集是列表列表:

items = [item1, item2, ..., itemN].

我的利润和成本也列出:

profits = [x[2] for x in items]
costs = [x[1] for x in items]

对于所选的每个项目,它需要具有最小值,并且至少5个项目必须将属性(is_blue)标志设置为1.

我想选择具有最高值的20个最便宜的项目,这样其中5个项目的属性标志设置为1.

我在使用谷歌OR工具制定这个问题时遇到了麻烦.

from ortools.linear_solver import pywraplp

solver = pywraplp.Solver('SolveAssignmentProblemMIP',
                       pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

x = {}

for i in range(MAX_ITEMS):
    x[i] = solver.BoolVar('x[%s]' % (i))

#Define the constraints 
total_chosen = 20 …

Google或-tools的一个示例是n-queens问题的解算器. 在底部,它表示可以通过向约束求解器添加对称破坏约束来改进实现.

环顾互联网,我发现n-queens问题的对称性破坏约束,但我不能为我的生活弄清楚如何将这些转换为约束到实现它们的python代码.

编辑:这是一个糟糕的问题,让我们更新......

我试过了什么？

以下是上面第一个链接的设置:

from ortools.constraint_solver import pywrapcp

N = 8
solver = pywrapcp.Solver("n-queens")
# Creates the variables.
# The array index is the column, and the value is the row.
queens = [solver.IntVar(0, N - 1, "x%i" % i) for i in range(N)]
# Creates the constraints.
# All rows must be different.
solver.Add(solver.AllDifferent(queens))
# All columns must be different because the indices of queens are all different.
# No two queens can be on …

我想从 ortools修改总线调度问题，以便每个司机的班次在插槽方面是连续的，如果需要，司机可以同时共享一个班次。

例如，假设我们有以下半小时班次（格式类似于来自 ortools 的原始 bus_scheduling_problem）：

shifts = [
[0, '07:00', '07:30', 420, 450, 30],
[1, '07:30', '08:00', 450, 480, 30],
[2, '08:00', '08:30', 480, 510, 30],
[3, '08:30', '09:00', 510, 540, 30],
[4, '09:00', '09:30', 540, 570, 30],
[5, '09:30', '10:00', 570, 600, 30],
[6, '10:00', '10:30', 600, 630, 30],
[7, '10:30', '11:00', 630, 660, 30],
[8, '11:00', '11:30', 660, 690, 30],
[9, '11:30', '12:00', 690, 720, 30],
[10, '12:00', '12:30', 720, 750, 30],
[11, …

生成一些随机的高斯坐标，我注意到TSP求解器返回了可怕的解，但是对于相同的输入，它又一次又一次地返回了相同的可怕解。

给出以下代码：

import numpy
import math
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2

import matplotlib
%matplotlib inline
from matplotlib import pyplot, pylab
pylab.rcParams['figure.figsize'] = 20, 10


n_points = 200

orders = numpy.random.randn(n_points, 2)
coordinates = orders.tolist()

class Distance:
    def __init__(self, coords):
        self.coords = coords

    def distance(self, x, y):
        return math.sqrt((x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2)

    def __call__(self, x, y):
        return self.distance(self.coords[x], self.coords[y])

distance = Distance(coordinates)

search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.LOCAL_CHEAPEST_ARC)

search_parameters.local_search_metaheuristic = …

我是Java的新手，我想尝试使用Google或工具解决车辆路线问题

只是尝试从这里运行Java示例

但是我有一个例外： java.lang.UnsatisfiedLinkError: no jniortools in java.library.path

有一行代码可以加载系统库“ jniortools”。但是我不知道从哪里得到那个lib。

我正在使用Mac OSX。

有任何想法吗？

是否可以在 IntelliJ Idea 上安装该库？

还是我必须使用 Visual Studio 2017？

如果是这样，我该如何安装它？我发现谷歌文​​档令人困惑。

我有一个列表Employee和一个列表Mission。每个任务都有开始时间和持续时间。

在CP模型（谷歌CpSat，从或工具包），我定义shifts = Dictionary<(int,int),IntVar>，其中shifts[(missionId, employeeId)] == 1当且仅当这个任务是由这名员工来实现。

我需要将每个任务分配给一名员工，显然一名员工无法同时完成两项任务。我已经写了这两个硬约束，它们运行良好。

问题：

现在，有些任务是“链接”在一起的，应该由同一个员工来实现。它们存储如下：

linkedMissions = {{1,2}, {3,4,5}}

在这里，任务1和任务2必须由同一个员工共同实现，任务3、4和5也是如此。

为了编写这最后一个约束，我为每个员工收集了应该链接在一起的所有班次的列表，然后我让它们都相等。

foreach (var employee in listEmployeesIds)
foreach (var missionGroup in linkedMissionsIds)
{
    var linkedShifts = shifts
        .Where(o => o.Key.Item2 == employee
                    && missionGroup.Contains(o.Key.Item1))
        .Select(o => o.Value)
        .ToList();

    for (var i = 0; i < linkedShifts.Count - 1; i++) 
        model.Add(linkedShifts[i] == linkedShifts[i + 1]);
}

然而，求解器告诉我该模型不可行，但我可以用纸和笔轻松找到工作计划。我有 35 名员工和 25 个任务，连接在一起的任务不重叠，所以应该没有任何问题。

编辑：

作为替代方法，正如@Laurent Perron 所建议的，我尝试对所有必须在一起的班次使用相同的布尔变量：

var constraintBools = new …

我已经使用 or-tools 几个月了，但最近遇到了以下问题：

模型：

• 2辆车，每辆车都有一个开始位置s0, s1和一个结束位置t0, t1。
• 2 个参观地点x0, x1。

时间窗口：

[[5400, 5820], [9000, 9420], [5520, 39719], [6420, 43319], [5521, 39720], [6421, 43320]]

持续时间矩阵：

[
   x0: [0, horizon, horizon, horizon, 5400, 5400], 
   x1: [horizon, 0, horizon, horizon, 1800, 1800], 
   s0: [0, 0, horizon, horizon, 0, horizon], 
   s1: [0, 0, horizon, horizon, horizon, 0], 
   t0: [horizon, horizon, horizon, horizon, horizon, horizon],
   t1: [horizon, horizon, horizon, horizon, horizon, horizon]
]

哪里horizon = 86760- 这只是一个很大的价值来驳回这个潜在的任务。 …

我正在使用带有 java 的 google or-tools 进行路线优化。一切正常，直到我更改线程。当我在一个线程中做所有事情时，这很好用。我调用routing.solveWithParameters(searchParameters)了一个新线程。然后，在另一个线程中，当我调用 时routing.getArcCostForVehicle(prevIndex, index, vehicleIndex)，出现错误（它无法在内存中找到值）。

Java frames: (J=compiled Java code, j=interpreted, Vv=VM code)
j  com.google.ortools.constraintsolver.mainJNI.RoutingModel_getArcCostForVehicle(JLcom/google/ortools/constraintsolver/RoutingModel;JJJ)J+0
j  com.google.ortools.constraintsolver.RoutingModel.getArcCostForVehicle(JJJ)J+9