1

我正在尝试优化决策变量 (X) 是 NxN 二进制矩阵的问题。我发现使问题的约束之一起作用时遇到了麻烦。

第一个约束意味着每行中 X 的总和必须 == 1。（已覆盖）

第二个约束（我无法使用的约束）要求对于对角线 == 1 的那些列，X 的总和必须 >= 2。我在 PuLP 中生成了以下约束：

for j in W:
    prob +=  sum(X[i][j] for i in W if X[j][j] >= 1) >= 2

PuLP 指示解决方案状态为“不可行”。¿ 我做错了什么？¿ 这个约束不能在纸浆中实现？

本质上，涵盖先前要求的示例解决方案矩阵将是：

[0,0,0,1,0]
[0,0,0,1,0]
[0,0,0,1,0]
[0,0,0,0,1]
[0,0,0,0,1]
4

1 回答 1

1

这是一个线性规划框架，因此只能使用线性函数。任意 python 表达式，如：

  • if
  • abs
  • min

不会传递给求解器，而是先验地评估（建模框架/求解器看不到这一点）通常会导致垃圾。

这类事情必须线性化。一些框架可以自动提供其中的一些，但这通常是一项非常艰巨的任务（因为如果没有特定于模型的假设，大多数线性化是不可能的！）。

（例如cvxpy支持重新制定abs并min与某些规则集兼容）

在这里，您需要自己执行此操作。

如果我正确理解了任务，它看起来像：

  • 二进制矩阵
  • 每行总和为 1
  • 每个列总和都是不受约束的，除了一列，在对角线位置有一个 1 -> 然后这个列总和的下限为 2

示例解决方案：

D!    D!

1  0  0  0   sum = 1 
1  0  0  0   sum = 1
0  0  1  0   sum = 1
0  0  1  0   sum = 1

sums
2  0  2  0

我们可以将表达式线性化为：

for column in columns:
    (1-diag_elem_of_column) * bigM + sum(column) >= 2

    <-> 

    (1-diag_elem_of_column) * 2 + sum(column) >= 2

这是一个经典的 big-M 公式，其中有一些二进制指示变量（对角元素）使用一些大常数 big-M激活/停用一些线性表达式。这个大常数使这些方法依赖于假设，但在您的情况下，这个大常数不需要非常大（并且紧缩对于完整性间隙很重要 -> 对求解器更好）。

这个想法是：

  • sum(column) >= 2 除非没有对角元素命中，否则强制执行
  • 当存在对角元素命中时 -> (1-diag_elem_of_column) * 2 = 0 -> 总和被限制为 >= 2（因为我们需要在剩余变量中获得 2 个非零）
  • 当没有对角元素命中时 -> (1-diag_elem_of_column) * 2 = 2 >= 2 （剩余元素的总和是免费的-> 没有限制，因为我们已经满足了最小值 2）

代码方面，这可能看起来像（未经测试）：

# assumption: square-matrix
# assumption: X[row][col] storage-order

N = 5

for diag_element_index, col in enumerate(N):
  prob += (1 - X[diag_element_index][col]) * 2 + sum([X[row][col] for row in range(N)]) >= 2
于 2020-04-19T12:09:21.743 回答