Matlab优化-约束条件下优化变量的条件和

Question

我正在尝试使用 MATLAB (bintprog) 中的二进制变量解决 ILP 问题。我需要定义一个类似于下面的约束：

我想对二进制变量 x<sub>i, j</sub> 求和，直到其中一个等于 zero，然后停止求和。如何在 ILP 中定义此约束？

Answer 1

在我看来，这是一个非常不典型的 MIP 约束。这是我的尝试：

你要考虑：

编辑

以双倍数量的二进制辅助变量为代价，也可以在没有 bigM 常数的情况下制定它。

素描：

不要使用单边的蕴涵来设置指标，而是使用相等 == 双向蕴涵 -> 没有辅助变量是免费的；全部为 0 或 1，仅取决于 x(z)
现在构建第二层二进制辅助变量（b_i），思路如下：b_i >= smallConst * b_i-1 + smallConst * a_i (smallConst in (0, 0.5]; should not be close 0 )
使用 b-vector 作为最终的总和约束（如上文所述；但不再使用 a-vector！）

Answer 2

我读这个的方式（有点困难，因为几乎没有解释；我认为这个问题可以更清楚地表述），这基本上是在计算第一个 x(k) 是 1。在这里我假设 x(i,j) 映射到 x(k) 所以我们有一个更好定义的顺序。可以使用新的二进制变量 y(k):

进行计数

y(k) = x(k)*y(k-1)   if k>1
y(k) = x(k)          if k=1
y(k) in {0,1}

例如：

x = [1 1 1 0 1 0]
y = [1 1 1 0 0 0]

非线性表达式 x(k)*y(k-1) 可以很容易地线性化（它是两个二进制变量的乘法；参见 here；请注意，使用此公式我们甚至可以将 y(k) 放松为连续介于 0 和 1 之间）。优化版本可能如下所示：

y(k) >= x(k)+y(k-1)-1   if k>1
y(k) = x(k)             if k=1
0 <= y(k) <= 1

现在你可以做

sum(k, y(k)) <= c

这个公式也允许说：前导 1 的数量应该在 c1 和 c2 之间。

我们也可以直接写：

x(1) + ... + x(c+1) <= c

这也禁止超过 c 个前导 1，甚至更简单。

我们经常看到的另一个问题（例如在发电机调度中）是我们不能连续打开超过 c 个 x(k) 的条件（即发电机不能打开超过 c连续周期：在 c 个周期开启后，发电机必须关闭至少 1 个周期）。这意味着我们不允许超过 c 1 的序列。

Matlab optimization - conditional sum of optimization variable in constraint