如何将二次方转换为线性程序? [英] How to convert quadratic to linear program?

问题描述

我有一个优化问题，目标函数中有2个相乘的变量，使模型成为二次方.

I have an optimization problem that has in the objective function 2 multiplied variables, making the model quadratic.

我目前正在使用zimpl来解析模型，并使用glpk来解决它.由于他们不支持二次编程，因此我需要将其转换为MILP.

I am currently using zimpl, to parse the model, and glpk to solve it. As they don't support quadratic programming, I would need to convert this to an MILP.

.第一个变量为实数，范围为[0，1]，第二个变量为实数，范围为0到inf.毫无疑问，这可以是整数.

. The first variable is real, in range [0, 1], the second one is real, from range 0 to inf. This one could without a problem be integer.

目标函数中的关键部分如下:

The critical part in the objective function looks like this:

max ... + var1 * var2 + ...

我在约束方面也遇到了类似的问题，但是很容易解决.

I had similar problems in the constraints, but they were easily solvable.

我该如何解决目标函数中的此类问题?

How could I solve this kind of a problem in the objective function?

推荐答案

这种形式的模型实际上称为双线性优化问题.使双线性项线性化的典型方法是通过称为McCormick包络的东西.

Models in this form are actually called bilinear optimization problems. The typical approach to linearizing bilinear terms is through something called the McCormick envelope.

考虑变量x和y，以达到最大化问题的目的在x*y位置.如果假设x和y分别受xL <= x <= xU和yL <= y <= yU限制，则可以将x*y替换为w(数量的上限)，并具有以下约束(您可以看到派生此处):

Consider variables x and y, where you want x*y in the objective of your maximization problem. If we assume x and y are bounded by xL <= x <= xU and yL <= y <= yU, then we can replace x*y with w, an upper bound for the quantity, with the following constraints (you can see the derivation here):

w <= xU*y + x*yL - xU*yL
w <= x*yU + xL*y - xL*yU
xL <= x <= xU
yL <= y <= yL

请注意，这些约束在决策变量中都是线性的.麦考密克信封中有相应的下限，但是由于您要使它们最大化，因此在您的情况下不重要.

Note that these constraints are all linear in the decision variables. There are corresponding lower bounds in the McCormick envelope, but since you're maximizing they're unimportant in your case.

如果您想更紧密地绑定在x*y上，则可以将其中一个变量的间隔(我将在此处使用x)拆分为范围[xL1，xU1]，[xL2，xU2]，... ，[xLn，xUn]，引入辅助连续变量{x1，x2，...，xn}和{w1，w2，...，wn}以及辅助二进制变量{z1，z2，...，zn }，它将指示选择了哪个x值范围.上面的约束可以替换为(我将显示索引为1的情况，但所有n个索引都需要使用这些约束):

If you want a tighter bound on x*y, you can split up the interval on one of the variables (I'll use x here) into ranges [xL1, xU1], [xL2, xU2], ..., [xLn, xUn], introducing auxiliary continuous variables {x1, x2, ..., xn} and {w1, w2, ..., wn} as well as auxiliary binary variables {z1, z2, ..., zn}, which will indicate which range of x values was selected. The constraints above could be replaced by (I'll show the index 1 case, but you would need these for all n indices):

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包络.范围已选择.)

Basically you will have x1=0 and w1 <= 0 whenever z1=0 (aka this part of the range is not selected), and you will have the normal McCormick envelope if z1=1 (aka this part of the range is selected).

最后一步是生成这些变量的范围特定版本之外的x和w.这可以通过以下方式完成:

The last step is to generate x and w out of range-specific versions of these variables. This can be done with:

x = x1 + x2 + ... + xn
w = w1 + w2 + ... + wn

您做出n越大，对双线性项的估计就越准确.但是，较大的n值会影响模型求解的可处理性.

The larger you make n, the more accurate of an estimation you will have for the bilinear term. However large values of n will affect the tractability of solving your model.

最后一个注释-您指出变量之一是无界的，但麦考密克信封要求两个变量都具有界.您应该修复边界，求解，如果最优值在边界处，则应该使用其他边界重新求解.

One final note -- you indicate that one of your variables in unbounded, but the McCormick envelope requires bounds on both variables. You should fix bounds, solve, and if your optimal value is at the boundary then you should re-solve with a different boundary.

这篇关于如何将二次方转换为线性程序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！