0

我想根据我使用 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

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

这是我的代码：

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)
4

3 回答 3

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}")

通过这些变化，模型变得可行。

希望这可以帮助。

菲利普。

于 2020-04-27T15:39:37.413 回答
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 变量，因此不能用于发布约束。

为了实现您的约束，这是 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. 使用一个松弛器对象并尝试放松问题：松弛器将放松一些约束，告诉你他必须放松哪些约束才能达到可行的解决方案：
    solution = model.solve()
    if solution is None:
        from docplex.mp.relaxer import Relaxer
        rx = Relaxer()
        rs = rx.relax(model)
        rx.print_information()

希望这可以帮助。

于 2020-04-27T14:41:38.533 回答
0

“不超过 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()）

于 2020-05-04T14:54:01.330 回答