用复杂的约束规划完成二元矩阵

Question

我想根据使用 dpcplex 模型的一些约束生成一个 20x38 二进制矩阵。一些矩阵单元格预定义如下（行，列，参数）：

[(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
一对连续 0 的总和必须 <=3 : 在每一行中我们不允许有多于 3 对 00 和 3 对 11

问题是我的模型没有 return 任何解决方案。我不确定我的模型是否正确。

这是我的代码：

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

我没有时间解决整个问题，但我可以在最后两个块（连续值约束）中发现严重的问题。首先，给出的代码会引发 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变量，因此不能用于post约束。

要实现您的约束，这里是 Docplex 中的一种可能方法：对于每个 (i, j) 单元格，定义一个 constraint，当 (i,j) 和 (i,j+1) 都等于 0 时满足该约束并存储所有约束条件列表中的一行：

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

请注意，这些约束并未添加到模型中，因为我们不关心哪些满足或不满足，我们只希望满足的约束（每行）的总和小于 3。AS 约束可以无缝转换为二进制变量，你可以将它们用作普通表达式，我们必须添加这些约束的 sum 小于 3：这意味着它们中最多三个将满意。这个块的完整代码是：

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

您可以很容易地找出如何以类似的方式修复 "two cells equal 1" 约束的第二个块。

但是，最终模型并没有解决。

为了研究不可行的模型，这里有两个 Docplex 中的通用技巧：

为您的约束命名
使用 Relaxer 对象并尝试放松问题：放松器会放松一些约束，告诉您他必须放松哪些约束才能达到可行的解决方案：

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

希望对您有所帮助。

Answer 2

我发现了使模型无法运行的原因：约束 "no more than two consecutive 0s or 1s" 不正确（关于 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 3

"no more than 3 consecutive 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()这里）

用复杂的约束规划完成二元矩阵

Completing binary matrix with cplex constraint programming

python

matrix

constraint-programming

cplex

docplex