如何根据决策变量（一个用于行，一个用于列）从矩阵（Python 中的列表列表）中选择一个元素 | OR-工具，Python

问题描述 投票：0回答：3

我是约束规划和 OR 工具的新手。关于问题的简要说明。有 8 个位置，对于每个位置，我需要决定应选择 A 类型的移动 (move_A) 和 B 类型的移动 (move_B)，以便从 2 个移动的组合（在每个位置）获得的值是最大化。 （但这只是更大问题的一部分）。我想用

AddElement
的方式来进行子设置。

请看下面的尝试

from ortools.sat.python import cp_model
model = cp_model.CpModel()

# value achieved from combination of different moves of type A
# (moves_A (rows)) and different moves of type B (moves_B (columns))
# for e.g. 2nd move of type A and 3rd move of type B will give value = 2
value = [
            [ -1,  5,  3,  2,  2],
            [  2,  4,  2, -1,  1], 
            [  4,  4,  0, -1,  2],
            [  5,  1, -1,  2,  2],
            [  0,  0,  0,  0, 0],
            [  2,  1,  1,  2, 0]
       ]

# 6 moves of type A
num_moves_A = len(value)

# 5 moves of type B
num_moves_B = len(value[0])

num_positions = 8

type_move_A_position = [model.NewIntVar(0, num_moves_A - 1, f"move_A[{i}]") for i in range(num_positions)]

type_move_B_position = [model.NewIntVar(0, num_moves_B - 1, f"move_B[{i}]") for i in range(num_positions)]

value_position = [model.NewIntVar(0, 10, f"value_position[{i}]") for i in range(num_positions)]

# I am getting an error when I run the below
objective_terms = []
for i in range(num_positions):
    model.AddElement(type_move_B_position[i], value[type_move_A_position[i]], value_position[i])
    objective_terms.append(value_position[i])

错误如下：

Traceback (most recent call last):

  File "<ipython-input-65-3696379ce410>", line 3, in <module>
    model.AddElement(type_move_B_position[i], value[type_move_A_position[i]], value_position[i])

TypeError: list indices must be integers or slices, not IntVar

在 MiniZinc 中，下面的代码可以工作

var int: obj = sum(i in 1..num_positions ) (value [type_move_A_position[i], type_move_B_position[i]])

我知道在 OR-Tools 中我们必须先创建一些中间变量来存储结果，所以上面的 minizinc 方法不起作用。但我很难做到这一点。

我总是可以创建一个 2 个二进制变量矩阵，一个用于 num_moves_A * num_positions，另一个用于 num_moves_B * num_positions，添加相关约束并达到目的

但我想学习如何通过

AddElement
约束来做同样的事情

非常感谢有关如何重写 

AddElement
代码片段的任何帮助。谢谢。

or-tools constraint-programming cp-sat
3个回答
5
投票

AddElement 仅是一维的。 从 minizinc 转换为 CP-SAT 的方式是创建一个中间变量 

p == index1 * max(index2) + index2
并将其用于具有展平矩阵的元素约束中。

1
投票

遵循 Laurent 的建议（使用 

AddElement
约束）：

from ortools.sat.python import cp_model

model = cp_model.CpModel()

# value achieved from combination of different moves of type A
# (moves_A (rows)) and different moves of type B (moves_B (columns))
# for e.g. 2 move of type A and 3 move of type B will give value = 2

value = [
    [-1, 5, 3, 2, 2],
    [2, 4, 2, -1, 1],
    [4, 4, 0, -1, 2],
    [5, 1, -1, 2, 2],
    [0, 0, 0, 0, 0],
    [2, 1, 1, 2, 0],
]

min_value = min([min(i) for i in value])
max_value = max([max(i) for i in value])

# 6 moves of type A
num_moves_A = len(value)

# 5 moves of type B
num_moves_B = len(value[0])

# number of positions
num_positions = 5

# flattened matrix of values
value_flat = [value[i][j] for i in range(num_moves_A) for j in range(num_moves_B)]

# flattened indices
flatten_indices = [
    index1 * len(value[0]) + index2
    for index1 in range(len(value))
    for index2 in range(len(value[0]))
]

type_move_A_position = [
    model.NewIntVar(0, num_moves_A - 1, f"move_A[{i}]") for i in range(num_positions)
]

model.AddAllDifferent(type_move_A_position)

type_move_B_position = [
    model.NewIntVar(0, num_moves_B - 1, f"move_B[{i}]") for i in range(num_positions)
]

model.AddAllDifferent(type_move_B_position)

# below intermediate decision variable is created which
# will store index corresponding to the selected move of type A and
# move of type B for each position
# this will act as index in the AddElement constraint

flatten_index_num = [
    model.NewIntVar(0, len(flatten_indices), f"flatten_index_num[{i}]")
    for i in range(num_positions)
]

# another intermediate decision variable is created which
# will store value corresponding to the selected move of type A and
# move of type B for each position
# this will act as the target in the AddElement constraint

value_position_index_num = [
    model.NewIntVar(min_value, max_value, f"value_position_index_num[{i}]")
    for i in range(num_positions)
]

objective_terms = []
for i in range(num_positions):
    model.Add(
        flatten_index_num[i]
        == (type_move_A_position[i] * len(value[0])) + type_move_B_position[i]
    )
    model.AddElement(flatten_index_num[i], value_flat, value_position_index_num[i])
    objective_terms.append(value_position_index_num[i])

model.Maximize(sum(objective_terms))

# Solve
solver = cp_model.CpSolver()
status = solver.Solve(model)

solver.ObjectiveValue()

for i in range(num_positions):
    print(
        str(i)
        + "--"
        + str(solver.Value(type_move_A_position[i]))
        + "--"
        + str(solver.Value(type_move_B_position[i]))
        + "--"
        + str(solver.Value(value_position_index_num[i]))
    )
1
投票

下面的版本使用 

AddAllowedAssignments
约束来实现相同的目的（根据 Laurent 的替代方法）：

from ortools.sat.python import cp_model

model = cp_model.CpModel()

# value achieved from combination of different moves of type A
# (moves_A (rows)) and different moves of type B (moves_B (columns))
# for e.g. 2 move of type A and 3 move of type B will give value = 2
value = [
    [-1, 5, 3, 2, 2],
    [2, 4, 2, -1, 1],
    [4, 4, 0, -1, 2],
    [5, 1, -1, 2, 2],
    [0, 0, 0, 0, 0],
    [2, 1, 1, 2, 0],
]

min_value = min([min(i) for i in value])
max_value = max([max(i) for i in value])

# 6 moves of type A
num_moves_A = len(value)

# 5 moves of type B
num_moves_B = len(value[0])

# number of positions
num_positions = 5

type_move_A_position = [
    model.NewIntVar(0, num_moves_A - 1, f"move_A[{i}]") for i in range(num_positions)
]

model.AddAllDifferent(type_move_A_position)

type_move_B_position = [
    model.NewIntVar(0, num_moves_B - 1, f"move_B[{i}]") for i in range(num_positions)
]

model.AddAllDifferent(type_move_B_position)

value_position = [
    model.NewIntVar(min_value, max_value, f"value_position[{i}]")
    for i in range(num_positions)
]

tuples_list = []
for i in range(num_moves_A):
    for j in range(num_moves_B):
        tuples_list.append((i, j, value[i][j]))

for i in range(num_positions):
    model.AddAllowedAssignments(
        [type_move_A_position[i], type_move_B_position[i], value_position[i]],
        tuples_list,
    )

model.Maximize(sum(value_position))

# Solve
solver = cp_model.CpSolver()
status = solver.Solve(model)

solver.ObjectiveValue()

for i in range(num_positions):
    print(
        str(i)
        + "--"
        + str(solver.Value(type_move_A_position[i]))
        + "--"
        + str(solver.Value(type_move_B_position[i]))
        + "--"
        + str(solver.Value(value_position[i]))
    )
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.