3

我有一个 ILP 问题，其中我表达了实现 A OR B 的一些约束，其中 A 和 B 是逻辑 AND 的结果（假设 A = A1 AND A2，B = B1 AND B2 AND B3）。在我的问题的这一点上，据说A和B之间的一个等于1。A和B都是二进制变量。

我想用 If-Then-Else 来表达这个断言：

if (A == true)
   /* Choose one between C and D */
   C_OR_D >= C;
   C_OR_D >= D;
   C_OR_D <= C + D;
   C_OR_D = 1; 
else                                     /* or if (B == true), that's the same */
   /* Choose one between E and F */
   E_OR_F >= E;
   E_OR_F >= F;
   E_OR_F <= E + F;
   E_OR_F = 1;

我知道如何编写简单的 If-Condition，例如

/* if (x == true) then y = true */
y >= x;

但我不知道如何编写一组约束来表达“复杂”的 if。

你们中有人知道如何在 LPsolve 中解决这个问题吗？

4

2 回答 2

3

回答第一部分：

AND 可以建模为

A >= A1 + A2 -1
A <= A1
A <= A2

OR 可以建模为

B >= B1
B >= B2
B <= B1 + B2

要对 if-else 约束建模，您可以使用“大 M”技术。

让 M 是一个足够大的数。

您可以通过在不等式的一侧添加 M 来“禁用”不等式。那么无论变量值如何，不等式都成立。

例如

if (A == 1)
   C_OR_D >= C;
else
   E_OR_F >= E;

可以建模为

(1-A) * M + C_OR_D >= C
A * M + E_OR_F >= E
于 2014-07-19T19:45:40.950 回答
1

一种特殊情况相当于“如果 X=N 则 SAME=true”。对于 X 中的整数值，对此的解决方案是：

  1. 相同 + 更大 + 更小 = 1
  2. X - M1 * 更大 + 更小 <= N
  3. X + M2 * 更小 - 更大 >= N

对于二进制变量 SAME、BIGGER、SMALLER 和足够大的数字 M1、M2（取决于 X 的可能范围）。

如果 X=N，BIGGER 和 SMALLER 必须为 0，否则违反后两个方程之一。因此，SAME 必须为 1（等式 1）。

如果 X > N 则 BIGGER = 1 禁用等式 2，并且由于 X >= N+1 等式 3 仍然成立。SAME = SMALLER = 0（等式 1）。

如果 X < N 则 SMALLER = 1 禁用等式 3，因为 X <= N-1 等式 2 仍然成立。相同 = 更大 = 0（等式 1）。

于 2017-05-04T20:40:43.350 回答