约束编程 - 使用变量作为矩阵索引

Question

我是Or-Tools的新手，我很难使用它，这是我的问题：

假设我们有一张3分'1'，'2'，'3'的地图，并且我们有3个名字'a'，'' b'，'c'。每个要点都可以取所有名称，但必须有一个名称。 因此，我们有一个矩阵，说明所有点与另一个点之间的距离，这些距离说您必须从一个名字转到另一个名称。 目标是找到要设置为每个点的名称，以使其具有最小的距离。

使用代码：

     'Distance matrix'             'Planning matrix'
    '1'     '2'    '3'            'a'     'b'     'c'
'1'  0       10     20         'a' 0       1       3
'2'  10      0      30         'b' 1       0       2
'3'  20      30     0          'c' 3       2       0

在这里我们需要从A到B 1次。 在这里我如何创建变量和约束：

for x in range(len(planning)):
     for y in  range(len(planning)):
         var_list[x, y] = model.NewBoolVar('')

for x in range(len(planning)):
    model.AddExactlyOne(var_list[x, y] for y in range(len(planning)))
for y in range(len(planning)):
    model.AddExactlyOne(var_list[x, y] for x in range(len(planning)))

我们有一个矩阵，其中每一行和列只有一个1 我的想法是使用此矩阵来定义每个点将哪个名称设置为每个点。 矩阵可以是这样的：

    'a''b''c'
'1'  0  1  0
'2'  0  0  1
'3'  1  0  0

这是我尝试求解优化的方式，我将var用作距离矩阵的索引：

terms = []
for index_x in  range(len(planning)):
     for index_y in  range(len(planning)):
         terms.append(planning[index_x, index_y] * distance[np.where(var_list[index_x] == True)[0][0]][np.where(var_list[index_y] == True)[0][0]])
model.Minimize(sum(terms))

但是它不会运行，因为它找不到var_list是正确的

terms.append(planning[index_x, index_y] * distance[np.where(var_list[index_x] == True)[0][0]][np.where(var_list[index_y] == True)[0][0]])
IndexError: index 0 is out of bounds for axis 0 with size 0

索引我直接使用变量的另一个想法，但我的问题不再是线性的：

terms = []
for index_x in  range(len(planning)):
    for index_y in  range(len(planning)):
        terms.append(
            planning[index_x, index_y] *
            sum(
                distance[i, j] * var_list[index_x, i] * var_list[index_y, j] for i in range(len(planning)) for j in range(len(planning))
            )
        )
model.Minimize(sum(terms))

有人知道如何更改代码以使其正常工作？即使我必须使用另一个库。

Answer 1

您可以使用： boolean-logic_product-two-boolean-variables - laurent Perron

距离[i，j] * var_list [index_x，i] * var_list [index_y，j]。我看到常数 * boolvar * boolvar。我告诉你，Boolvar*Boolvar可以用新的Boolvar替换，并在模型中添加了另外3个条款。 - Laurent Perron

在这里如何应用它：

for i in range(size**2):
    for j in range(size**2):
        var_list2[i, j] = model.NewBoolVar('')

for key_entry in range(size):
    for key_exit in range(key_entry+1, size): # I use key_entry+1 to reduce the number of constraint and keep memory because my matrix is mirrored 
        for i in range(size):
            for j in range(size):
                model.AddBoolOr(var_list[key_entry, i].Not(), var_list[key_exit, j].Not(), var_list2[i + size * key_entry, j + size * key_exit])
                model.AddImplication(var_list2[i + size * key_entry, j + size * key_exit], var_list[key_entry, i])
                model.AddImplication(var_list2[i + size * key_entry, j + size * key_exit], var_list[key_exit, j])

for key_entry in range(size):
    for key_exit in range(key_entry+1, size):
        for i in range(size):
            for j in range(size):
                terms.append(planning[key_entry, key_exit] * path_weight[i, j] * var_list2[i + size * key_entry, j + size * key_exit])

model.Minimize(sum(terms))

Answer 2

如果要使用变量索引中访问1D数组中的变量：

def AddElement(self, index, variables, target):
    """Adds the element constraint: variables[index] == target."""

https://developers.google.com/optimization/reference/python/sat/python/cp_model#addelement