matlab - MATLAB 中 CPLEX "cplexmilp"函数的奇怪结果

Question

根据 my previous question ，我想使用二进制整数线性规划(所有变量都是二进制的)优化目标函数，如下所示:

Minimize f = (c1*x1) + (c2*x2) + MAX((c3*x3),(c4*x4)) + (c5*x5)
Subject to: some equality and inequality constraints

对于 MAX 运算符，我使用了辅助变量 x6 并添加了 x6>=(c3*x3) 和 x6>= (c4*x4) 约束问题所以问题变成:

Minimize f = (c1*x1) + (c2*x2) + x6 + (c5*x5),  with added constraints.

我使用 CPLEX API for MATLAB 来优化目标函数。
因为除了一个变量((x6) 是连续的)之外所有变量都是二进制的，并且系数具有double 值，所以问题变成了混合整数线性规划 所以我在这个配置中使用了 cplexmilp 函数:

• 变量类型:ctype='BBBBBC'(B:二进制，C:连续)
• 下限:lb=[0 0 0 0 0 0]
• 上限:ub=[0 0 0 0 0 inf]
• 函数调用:[fval] = cplexmilp(f, Aineq, bineq, Aeq, beq,[],[],[],lb,ub,ctype)

但有时在结果中我会看到 x3 和 x4 具有连续值(介于 0 和 1 之间)和 x3+x4=1。所以我的问题是:

1. 谁能告诉我x3 和x4 有什么问题？
2. 是否有不使用辅助变量并使用 cplexbilp 解决此优化问题的解决方案？

提前致谢

[更新]:
我的代码的一部分有逻辑错误，我修复了它们，现在在所有 x3 和 x4 不是二进制的情况下，我们有 x3*(1-x3)< 10^(-5), x4*(1-x4)< 10 ^(-5) 和 x3+x4=1，所以 @David Nehme 是对的(根据他的有用评论)，但我的第二个问题仍然存在!

Answer 1

David 的解决方案向您展示了为什么您的公式已线性化但不是二元的。您还可以尝试以 LP 或 MPS 格式打印问题，以查看所有由此产生的约束。

您询问了一个仍然是纯二元的公式。这是一种方法:

将其转换为纯二元公式

这里有一种方法可以使 Max() 的问题也是二进制的。它涉及额外的辅助。变量，但一旦应用标准的 if-then IP 技巧，它就相对简单了。

首先，让我们在一个简单的表格中列出四种可能的情况，看看 max() 项可以取什么值。这些情况是相互排斥的。

  x3 | x4 | max (c3.x4, c4.x3)
 -------------------------------
  0   | 0 | 0
  1   | 0 | c3
  0   | 1 | c4
  1   | 1 | max(c3, c4) - a constant

现在，让 C34 成为最大值 (c3, c4)。请注意，C34 是一个数字，而不是问题中的变量。我们需要这个用于新的目标函数。

引入新的二进制变量

对于上述四种情况中的每一种，我们都引入一个辅助 BINARY 变量。为清楚起见，将它们称为 y0、y3、y4、y34。

只有上表中的一种情况可以成立，所以我们补充:

y0 + y3 + y4 + y34 = 1 
yi are BINARY

现在，剩下的就是添加链接约束以确保:

 If x3=0 AND x4=0 then y0=1
 If x3=1 AND x4=0 then y3=1
 If x3=0 AND x4=1 then y4=1
 If x3=1 AND x4=1 then y34=1

我们可以通过为上述每个条件添加一对线性约束来确保这一点。

   2 y0 <= (1- x3) + (1 -x4)
  (1-x3) + (1-x4) <= y0 + 1

   2 y3 <= x3 + (1-x4)
  x3+(1-x4) <= y3 + 1

   2 y4 <= x4 + (1-x3)
  x4+(1-x3) <= y4 + 1

   2 y34 <= x3 + x4
  x3+x4 <= y34 + 1

新的目标函数现在变成了:

   Minimize f = (c1*x1) + (c2*x2) + (c5*x5) + 0*Y0 + C3*Y3 + C4*Y4 + C34*Y34

请注意，我们在目标函数中不再有 Max() 项。并且所有 x 和 y 变量都是二进制的。应包括所有原始约束加上上面的新约束(8+1 = 9 个)。一旦你这样做了，你就可以使用 cplexbilp 因为它是一个纯粹的 BILP 问题。

希望对您有所帮助。