Завершение двоичной матрицы с помощью программирования cplex-ограничений

Question

Я хочу сгенерировать двоичную матрицу 20x38, основываясь на некоторых ограничениях, которые я использую, используя модель dpcplex. Некоторые ячейки матрицы имеют предопределенные значения, как показано ниже (строка, столбец, параметр):

[(8,3,0), (14,0,0), (14,2,0), (16 , 0,0), (16,1,0), (12,0,0), (10,0,0), (10,8,0), (10,9,0), (17,7 , 0), (17,8,0), (8,0,0), (13,8,0), (13,9,0), (1,0,1), (15,19,0 )]

Мне нужно заполнить другие ячейки матрицы некоторыми ограничениями:

• сумма столбцов должна быть равна 10
• сумма строк должна быть равна 19
• последние 4 ячейки каждой строки должны быть альтернативными: допускается только 1010 или 0101
• не более 2 последовательных 0 или 1 с
• сумма каждых 5 ячеек в каждой строке должно быть в диапазоне [2,3]: нет 11011 или 00100
• сумма пары последовательных нулей должна быть <= 3: в каждой строке нам не разрешено иметь более 3 пар 00 и 3 пары из 11 </li>

Проблема в том, что моя модель не возвращает никаких решений. Я не уверен, что моя модель верна.

вот мой код:

from docplex.mp.model import Model

cond=[[8,3,0],[1,37,0],[6,9,0]]

model = Model("MatrixComple")

R = [i for i in range(20)]
R1=[i for i in range(38)]
R2=[34,35,36,37]
R3=[i for i in range(36)]
R4=[i for i in range(34)]
R5=[i for i in range(37)]
idx = [(i, j) for i in R for j in R1 ]

x = model.binary_var_dict(idx,name= "x")

"""pre-defined cells"""
for i in R:
    for j in R1:
        for item in cond:
            i1,i2,i3=item
            model.add_constraint(x[i1, i2] == i3)

"""sum of columns must be equal to 10   """    
model.add_constraints(model.sum(x[i, j] for i in R) == 10 for j in R2)

"""sum of rows must be equal to 19  """
model.add_constraints(model.sum(x[i, j] for j in R1) == 19 for i in R)

"""(apply to all rows)last 4 cells of each row must be alternative: just 1010 or 0101 is allowed"""
model.add_constraints(model.sum(x[(i, j)] for j in R2 ) == 2 for i in R  )
model.add_constraints(x[(i, 34)] ==x[(i, 36)]  for i in R  )


"""no more that 2 consecutive 0s or 1s : 110 or 001 or 101 or 010
this rule can not be applied to pre-defined cells. For example if we have 000 or 111 in pre-defined conditions,
we need to apply this rule for the rest of matrix not the pre-defined cells
""" 
model.add_constraints(model.sum(x[i, j]+x[i,j+1]+x[i,j+2] for j in R3) <=2 for i in R)
model.add_constraints(model.sum(x[i, j]+x[i,j+1]+x[i,j+2] for j in R3) >=1 for i in R)


""" (apply to all rows) sum of every 5 cells in each row must be in range [2,3] : no 11011 or 00100 is allowed """
model.add_constraints(model.sum(x[i, j]+x[i,j+1]+x[i,j+2]+x[i,j+3]+x[i,j+4]for j in R4) <=3 for i in R)
model.add_constraints(model.sum(x[i, j]+x[i,j+1]+x[i,j+2]+x[i,j+3]+x[i,j+4]for j in R4) >=2 for i in R)

""" (apply to all rows) sum of pair of consecutive 0s must be <=3 : in each row we are not allowed to have 
more than 3 pair of 00 """

for i in R:
    s=0
    for j in R5:
            if x[i, j]==x[i,j+1]==0:
                    s+=1
    model.add_constraint(s<= 3)

""" (apply to all rows) sum of pair of consecutive 1s must be <=3 : in each row we are not allowed to have 
more than 3 pair of 11 """
for i in R:
    s=0
    for j in R5:
            if x[i, j]==x[i,j+1]==1:
                    s+=1
    model.add_constraint(s<= 3)

solution = model.solve()
print(solution)

Answer 1

Я выяснил, что делает модель невозможной: ограничение «не более двух последовательных 0 или 1» было неправильным (как и ограничение около 5 последовательных ячеек. Вы не должны суммировать по всей строке, а располагать один диапазон на ячейку:

"""no more that 2 consecutive 0s or 1s : 110 or 001 or 101 or 010
this rule can not be applied to pre-defined cells. For example if we have 000 or 111 in pre-defined conditions,
we need to apply this rule for the rest of matrix not the pre-defined cells
"""
for i in R:
    for j in R3:
        s3ij = x[i, j]+x[i,j+1]+x[i,j+2]
        model.add_range(1, s3ij, 2, f"range3_{i}_{j}")

Аналогично, ограничение на пять последовательных ячеек может быть записано как:

for i in R:
for j in R4:
    s5ij = x[i, j]+x[i,j+1]+x[i,j+2] +x[i,j+3] +x[i,j+4]
    model.add_range(2, s5ij, 3, f"range5_{i}_{j}")

С этими изменениями модель становится выполнимой.

Надежда это помогает.

Филипп.

Answer 2

У меня нет времени, чтобы решить всю проблему, но я могу обнаружить серьезные проблемы в последних двух блоках (ограничения последовательных значений). Во-первых, код в том виде, в котором он задан, вызывает ошибку TypeError:

TypeError: Cannot use == to test expression equality, try using Python is operator or method equals: x_0_0 == x_0_1

Это по веским причинам: в DOcplex оператор '==' между переменными перегружен для построения ограничения объект модели. Этот объект не имеет Python истинного значения и не может использоваться в операторе Python if.

Кроме того, используемая переменная s не является переменными DOcplex, поэтому ее нельзя использовать для опубликовать ограничение.

Для реализации вашего ограничения в Docplex возможен следующий подход: для каждой (i, j) ячейки определите ограничение , которое выполняется, когда (i, j ) и (i, j + 1) равны нулю и сохраняют все ограничения строки в списке:

for i in R
   twozs = [x[i,j] + x[i, j+1] == 0 for j in R5]

Обратите внимание, что эти ограничения НЕ добавляются в модель, так как мы этого не делаем независимо от того, удовлетворены ли они или нет, мы просто хотим, чтобы сумма удовлетворенных ограничений (на строку) была меньше 3. AS-ограничения могут быть преобразованы в двоичные переменные без проблем, вы можете использовать их как простые выражения, и мы должны добавить, что сумма этих ограничений меньше 3: это означает, что не более трех из них будут выполнены. Полный код этого блока:

for i in R
   twozs = [x[i,j] + x[i, j+1] == 0 for j in R5]
   model.add(model.sum(twozs) <= 3)

Вы можете легко понять, как аналогичным образом исправить второй блок для ограничения "две ячейки равны 1".

Однако, окончательная модель не решается.

Чтобы исследовать недопустимые модели, в Docplex есть два основных трюка:

1. присваивает имена вашим ограничениям
2. использует объект Relaxer и попытаться ослабить проблему: расслабляющий расслабит некоторые ограничения, которые скажут вам, какие из них ему пришлось расслабить, чтобы найти реальное решение:

    solution = model.solve()
    if solution is None:
        from docplex.mp.relaxer import Relaxer
        rx = Relaxer()
        rs = rx.relax(model)
        rx.print_information()

Надеюсь, это поможет.

Answer 3

Исправленный код для ограничения «не более 3 последовательных 1 0r 0s»:

for i in r_rows:
    all_consecs = (x[i,j] == x[i,j+1] for j in range(n_cols-1))
    model.add(model.sum(all_consecs) <= 2, f"no_more_than_2_consecs_{i}")

Основной интерес здесь заключается в том, как логические ограничения могут использоваться в качестве выражений. Логическое ограничение может быть истинным или ложным, и его значение истинности фактически сохраняется в скрытой двоичной переменной, которую можно свободно использовать в выражениях (как в Model.sum () здесь)