如何将二次程序转换为线性程序？
How to convert quadratic to linear program?
我有一个优化问题，在 objective 函数中有 2 个相乘的变量，使模型成为二次方。
我目前正在使用 zimpl 来解析模型，并使用 glpk 来解决它。由于它们不支持二次规划，因此我需要将其转换为 MILP。
。第一个变量是实数，范围 [0, 1]，第二个是实数，范围从 0 到 inf。这个可以毫无问题地是整数。
objective 函数中的关键部分如下所示：
max ... + var1 * var2 + ...
我在约束中遇到了类似的问题，但很容易解决。
如何解决 objective 函数中的此类问题？
这种形式的模型实际上称为双线性优化问题。线性化双线性项的典型方法是通过称为麦考密克包络的东西。
考虑变量 x 和 y，您希望 x*y 在您的最大化问题的 objective 中。如果我们假设 x 和 y 以 xL <= x <= xU 和 yL <= y <= yU 为界，那么我们可以将 x*y 替换为 w，数量的上限，具有以下约束（您可以看到推导here):
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 值会影响求解模型的易处理性。
最后一点——你指出你的一个变量是无界的，但麦考密克信封要求两个变量都有界限。你应该固定边界，求解，如果你的最优值在边界处，那么你应该用不同的边界重新求解。
我有一个优化问题，在 objective 函数中有 2 个相乘的变量，使模型成为二次方。
我目前正在使用 zimpl 来解析模型，并使用 glpk 来解决它。由于它们不支持二次规划，因此我需要将其转换为 MILP。
。第一个变量是实数，范围 [0, 1]，第二个是实数，范围从 0 到 inf。这个可以毫无问题地是整数。
objective 函数中的关键部分如下所示：
max ... + var1 * var2 + ...
我在约束中遇到了类似的问题，但很容易解决。
如何解决 objective 函数中的此类问题？
这种形式的模型实际上称为双线性优化问题。线性化双线性项的典型方法是通过称为麦考密克包络的东西。
考虑变量 x 和 y，您希望 x*y 在您的最大化问题的 objective 中。如果我们假设 x 和 y 以 xL <= x <= xU 和 yL <= y <= yU 为界，那么我们可以将 x*y 替换为 w，数量的上限，具有以下约束（您可以看到推导here):
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 值会影响求解模型的易处理性。
最后一点——你指出你的一个变量是无界的，但麦考密克信封要求两个变量都有界限。你应该固定边界，求解，如果你的最优值在边界处，那么你应该用不同的边界重新求解。