我有一个优化问题，它在目标函数中包含 2 个乘法变量，使模型成为二次方。
我目前正在使用 zimpl 来解析模型，并使用 glpk 来解决它。由于它们不支持二次规划，我需要将其转换为 MILP。
. 第一个变量是实数，在 [0, 1] 范围内，第二个变量是实数，范围从 0 到 inf。这个可以毫无问题地是整数。
目标函数中的关键部分如下所示：
max ... + var1 * var2 + ...
我在约束中遇到了类似的问题，但它们很容易解决。
我该如何解决目标函数中的这种问题？
问问题
7578 次
1 回答
16
这种形式的模型实际上称为双线性优化问题。线性化双线性项的典型方法是通过称为 McCormick 包络的方法。
x*y考虑变量 x 和 y，这是您在最大化问题的目标中想要的。如果我们假设 x 和 y 以xL <= x <= xUand为界yL <= y <= yU，那么我们可以用 替换x*y为w数量的上限，具有以下约束（您可以在此处查看推导）：
w <= xU*y + x*yL - xU*yL
w <= x*yU + xL*y - xL*yU
xL <= x <= xU
yL <= y <= yL
请注意，这些约束在决策变量中都是线性的。McCormick 信封中有相应的下限，但是由于您要最大化它们，因此它们在您的情况下并不重要。
如果您想要更严格的界限x*y，您可以将其中一个变量的区间（我将在此处使用 x）拆分为范围 [xL1, xU1], [xL2, xU2], ..., [xLn, xUn] , 引入辅助连续变量 {x1, x2, ..., xn} 和 {w1, w2, ..., wn} 以及辅助二元变量 {z1, z2, ..., zn}，这将指示哪个选择了 x 值的范围。上面的约束可以替换为（我将显示索引 1 的情况，但所有 n 索引都需要这些）：
w1 <= xU1*y + x1*yL - xU1*yL*z1
w1 <= x1*yU + xL1*y - xL1*yU*z1
xL*z1 <= x1 <= xU*z1
基本上，只要 z1=0（也就是未选择范围的这一部分），您将拥有 x1=0 和 w1 <= 0，如果 z1=1（也就是选择了范围的这一部分），您将拥有正常的 McCormick 包络.
最后一步是从这些变量的特定范围版本中生成 x 和 w。这可以通过以下方式完成：
x = x1 + x2 + ... + xn
w = w1 + w2 + ... + wn
n 越大，对双线性项的估计就越准确。然而，较大的 n 值会影响求解模型的易处理性。
最后一点——你指出你的变量之一是无界的，但麦考密克信封要求两个变量都有界。您应该修复边界，求解，如果您的最佳值在边界处，那么您应该使用不同的边界重新求解。
于 2015-06-12T22:18:32.477 回答