根据 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
。
所以我的问题是:
- 谁能告诉我
x3
和x4
有什么问题? - 是否有不使用辅助变量并使用
cplexbilp
解决此优化问题的解决方案?
提前致谢
[更新]:
我的代码的一部分有逻辑错误,我修复了它们,现在在所有 x3 和 x4 不是二进制的情况下,我们有 x3*(1-x3)< 10^(-5), x4*(1-x4)< 10 ^(-5) 和 x3+x4=1,所以 @David Nehme 是对的(根据他的有用评论),但我的第二个问题仍然存在!
最佳答案
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 问题。
希望对您有所帮助。
关于matlab - MATLAB 中 CPLEX "cplexmilp"函数的奇怪结果,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20875750/