OR-Tools CP SAT: глобальные AddForbiddenAssignments на уровне модели, например AddAllDifferent

У меня есть список переменных и список возможных назначений для каждой переменной, которые добавляются как обычные AddAllowedAssignments (переменные, tuples_list). Это упрощено из моего приложения, у меня есть более жесткие ограничения на это, но это не влияет на мой вопрос здесь.

Пример:

var1, possible values = [1,2,3,4,5]
var2, possible values = [1,3,4,5,6,7]
var3, possible values = [1,2,5,6,7,8,9]

Мне определенно нужны AddAllDifferent (переменные), которые я могу сделать на уровне модели следующим образом:

model.AddAllDifferent([var1,var2,var3])

Но тогда мне также нужны некоторые ограничения, основанные на значениях, исключающих друг друга. Пример:

value [1] excludes values [3,5,6]     (1)
value [2] excludes values [5,7,9]     (2)

Итак, я продолжаю и создаю AddForbiddenAssignment (переменные, tuples_list) на уровне переменных для каждой пары переменных (я написал ограничения в двух строках, чтобы их было легче понять, но я знаю, что могу добавить их в один оператор):

AddForbiddenAssignment([var1, var2], [(1,3), (1,5), (1,6)])     (1)
AddForbiddenAssignment([var1, var2], [(2,5), (2,7)])            (2)

AddForbiddenAssignment([var1, var3], [(1,5), (1,6)])            (1)
AddForbiddenAssignment([var1, var3], [(2,5), (2,7), (2,9)])     (2)

AddForbiddenAssignment([var2, var3], [(1,5), (1,6)])            (1)
AddForbiddenAssignment([var2, var3], [(2,5), (2,7)])            (2)

Это прекрасно работает.

В настоящее время я не уверен, нужны ли они мне и в другом направлении, но я думаю, что да:

AddForbiddenAssignment([var2, var1], [(1,3), (1,5)])            (1)

AddForbiddenAssignment([var3, var1], [(1,3), (1,5)])            (1)
AddForbiddenAssignment([var3, var1], [(2,5)])                   (2)

AddForbiddenAssignment([var3, var2], [(1,3), (1,5), (1,6)])     (1)
AddForbiddenAssignment([var3, var2], [(2,5), (2,7)])            (2)

Как видите, это создает множество ограничений, особенно когда количество переменных увеличивается. Создание всех этих ограничений в настоящее время является довольно плохо выполняемой задачей.

Вопрос: Есть ли способ добавить запрещенные назначения на уровне модели, например AddAllDifferent ()? Я хотел бы использовать что-то вроде AddForbiddenAssignment (hibited_tuples_list), для которого не нужны переменные. Пример:

AddForbiddenAssignment([(1,3), (1,5), (1,6)])     (1)
AddForbiddenAssignment([(2,5), (2,7), (2,9)])     (1)

Другой вариант - иметь AddForbiddenAssignment (значение, список запрещенных_значений)

AddForbiddenAssignment(1, [3, 5, 6])     (1)
AddForbiddenAssignment(2, [5, 7, 9])     (1)

Надеюсь, мой вопрос имеет смысл. Заранее спасибо за помощь.


person bechtold    schedule 08.02.2020    source источник


Ответы (1)


Вам действительно нужны целочисленные переменные? Почему бы не использовать только логические переменные, sum () ‹= 1 и clauses. ?

person Laurent Perron    schedule 08.02.2020
comment
На самом деле я пытаюсь расставить струны. Но поскольку OR-Tools не поддерживает их, я смоделировал их как целые числа. Таким образом, выбранное целое число для переменной представляет собой выбранную строку. Использование логических переменных означает только то, что переменная заполнена, а не то, чем она заполнена. - person bechtold; 08.02.2020
comment
Я имел в виду, можете ли вы заменить intvar вектором логических значений с sum () == 1? Скорее всего, это все равно произойдет внутри компании. - person Laurent Perron; 08.02.2020
comment
Извините, но я не понимаю, как это могло бы помочь. Вы имеете в виду что-то вроде one-hot-encoding? Это создало бы еще больше переменных, верно? У меня около 100 переменных и 30000 возможных значений и около 10000 вышеуказанных ограничений для значений. Если я теперь создаю логические переменные для каждого присваивания между переменными и значениями, я получу еще больше переменных и больше ограничений, не так ли? - person bechtold; 08.02.2020
comment
Ваша идея сделать это, как здесь, с NewIntVar (0, 1, 'x_% i_% i'% (idx, b)) в строке 85? github.com/google/or-tools/ blob / stable / ortools / sat / samples / Я полагаю, что мои переменные, домен и пространство ограничений слишком велики для этого. Создание этого на стороне питона потребовало бы слишком много памяти и времени. - person bechtold; 08.02.2020
comment
Другая проблема, которую я вижу, заключается в том, что мне тоже нужны AddAllowedAssignments из-за других ограничений. Вот почему у меня есть ячейки с размером ячейки 1 элемент на ячейку, но этот один элемент должен ссылаться на значение из пространства домена. - person bechtold; 08.02.2020
comment
Нет, только одно логическое значение для каждого значения var ==. Ваша проблема слишком велика, но, как я уже сказал, решатель все равно создаст эти логические переменные. - person Laurent Perron; 09.02.2020