Как выбрать элемент из матрицы (список списка в python) на основе переменных решения (одна для строки и одна для столбца) | ИЛИ-инструменты, Python

avatar
Bhartendu Awasthi
9 августа 2021 в 04:33
217
3
1

Я новичок в программировании в ограничениях и инструментах ИЛИ. Коротко о проблеме. Есть 8 позиций, для каждой позиции мне нужно решить, какой ход типа A (move_A) и какой ход типа B (move_B) следует выбрать так, чтобы значение, полученное в результате комбинации двух ходов (в каждой позиции), было максимизирован. (Хотя это только часть большой проблемы). И я хочу использовать подход 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, приветствуется. Спасибо.

Источник

Ответы (3)

avatar
Laurent Perron
9 августа 2021 в 09:02
5

AddElement — только 1D. Способ перевода из minizinc в CP-SAT заключается в создании промежуточной переменной p == index1 * max(index2) + index2 и использовании ее в ограничении элемента со сглаженной матрицей.

Bhartendu Awasthi
9 августа 2021 в 10:49
0

Большое спасибо Лоран за быстрый ответ. Я смог последовать вашему совету, и это решило мою проблему. Я опубликую решение ниже, если оно может помочь кому-то с аналогичным вопросом в будущем. С уважением.

avatar
Bhartendu Awasthi
10 августа 2021 в 04:29
1

В приведенной ниже версии используется ограничение AddAllowedAssignments для достижения той же цели (согласно альтернативному подходу Лорана): 

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]))
    )
avatar
Bhartendu Awasthi
9 августа 2021 в 10:53
1

По предложению Лорана (используя ограничение 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]))
    )
Laurent Perron
9 августа 2021 в 11:16
1

Обратите внимание, что вы также можете использовать ограничение AllowedAssignment с кортежами (i, j, value[i][j])

Bhartendu Awasthi
9 августа 2021 в 11:51
0

Еще раз спасибо Лоран. Пробовал успешно ограничения AddAllowedAssignments. Это выглядит более элегантно, чем решение AddElement (меньшее количество промежуточных переменных решения, созданных с ограничениями AddAllowedAssignments). С уважением.