OR-Tools CP SAT: глобальные AddForbiddenAssignments на уровне модели, такие как AddAllDifferent - PullRequest
0 голосов
/ 08 февраля 2020

У меня есть список переменных и список возможных назначений для каждой переменной, которые добавляются как обычные 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)

Итак, я go вперед и создаю AddForbiddenAssignment (variable, 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 (forbidden_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)

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

1 Ответ

1 голос
/ 08 февраля 2020

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...