如何将二次转换为线性程序？

Question

我有一个优化问题,在目标函数2中有多个变量,使模型呈二次方.

我目前正在使用zimpl来解析模型,并使用glpk来解决它.由于它们不支持二次规划,我需要将其转换为MILP.

.第一个变量是实数,在[0,1]范围内,第二个变量是实数,范围从0到inf.这个可以没有问题是整数.

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

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

我在约束中遇到了类似的问题,但它们很容易解决.

我怎样才能在目标函数中解决这类问题？

Answer 1

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

考虑变量x和y,您想要x*y达到最大化问题的目标.如果我们假设x和y所界定xL <= x <= xU和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值会影响求解模型的可追溯性.

最后一个注意事项 - 你指出你的一个变量是无界的,但麦考密克包络需要两个变量的界限.您应该修复边界,求解,如果您的最佳值在边界处,那么您应该使用不同的边界重新求解.