优化 |
您所在的位置：网站首页 › python将list转换为绝对值 › 优化 |
优化
|
优化 | 线性化：含绝对值的线性化
非线性整数规划模型Gurobi求解代码
绝对值的线性化技巧利用上面的技巧进行线性化
总结
作者：刘兴禄， 清华大学 清华-伯克利深圳学院，博士在读 欢迎关注我们的微信公众号 运小筹
考虑下面的非线性整数规划 max 2 ∣ x 1 ∣ + ∣ x 2 ∣ s . t . ∣ x 1 ∣ + 2 ∣ x 2 ∣ ⩽ 8 − 5 ⩽ x 1 , x 2 ⩽ 5 \begin{aligned} \max \quad \,\,\,& 2|x_1| + |x_2| \\ s.t. \quad \,\,\,& |x_1| + 2|x_2| \leqslant 8 \\ & -5 \leqslant x_1, x_2 \leqslant 5 \end{aligned} maxs.t.2∣x1∣+∣x2∣∣x1∣+2∣x2∣⩽8−5⩽x1,x2⩽5 Gurobi求解代码 from gurobipy import * model = Model('non-linear model') x1 = model.addVar(lb=-5, ub=5, vtype=GRB.CONTINUOUS, name='x1') x2 = model.addVar(lb=-5, ub=5, vtype=GRB.CONTINUOUS, name='x2') x1_abs = model.addVar(lb=0, ub=5, vtype=GRB.CONTINUOUS, name='x1_abs') x2_abs = model.addVar(lb=0, ub=5, vtype=GRB.CONTINUOUS, name='x2_abs') model.setObjective(2 * x1_abs + x2_abs, GRB.MAXIMIZE) model.addConstr(x1_abs + 2*x2_abs = -x1) model.addConstr(x2_abs >= x2) model.addConstr(x2_abs >= -x2) model.optimize() print('x1:', x1.x) print('x2:', x2.x) print('x1_pos_abs:', x1_pos_abs.x) print('x1_neg_abs:', x1_neg_abs.x) print('x2_pos_abs:', x2_pos_abs.x) print('x2_neg_abs:', x2_neg_abs.x)求解结果为 Iteration Objective Primal Inf. Dual Inf. Time 0 1.6000000e+01 3.000000e+00 0.000000e+00 0s 2 1.1500000e+01 0.000000e+00 0.000000e+00 0s Solved in 2 iterations and 0.01 seconds Optimal objective 1.150000000e+01 x1: 5.0 x2: 1.5 x1_pos_abs: 5.0 x1_neg_abs: 0.0 x2_pos_abs: 1.5 x2_neg_abs: 0.0可见结果是一致的。 注意，如果约束里有一个不是绝对值，会出错的。经过了测试 x 1 + 2 ∣ x 2 ∣ ⩽ 8 x_1 + 2|x_2| \leqslant 8 x1+2∣x2∣⩽8，上述引入了 x 1 abs x_1^{\text{abs}} x1abs的方法也是等价的。 但是，下面的情形是不等价的，如果是 max 2 ∣ x 1 ∣ + ∣ x 2 ∣ s . t . x 1 + 2 ∣ x 2 ∣ ⩽ 8 − 5 ⩽ x 1 , x 2 ⩽ 5 \begin{aligned} \max \quad \,\,\,& 2|x_1| + |x_2| \\ s.t. \quad \,\,\,& x_1 + 2|x_2| \leqslant 8 \\ & -5 \leqslant x_1, x_2 \leqslant 5 \end{aligned} maxs.t.2∣x1∣+∣x2∣x1+2∣x2∣⩽8−5⩽x1,x2⩽5 然后我们转化成 max 2 ( x 1 + + x 1 − ) + ( x 2 + + x 2 − ) s . t . x 1 + 2 ( x 2 + + x 2 − ) ⩽ 8 x 1 = x 1 + − x 1 − x 2 = x 2 + − x 2 − ( 可以删去 ) − 5 ⩽ x 1 , x 2 ⩽ 5 0 ⩽ x i + , x i − ⩽ 5 , ∀ i = 1 , 2 \begin{aligned} \max \quad \,\,\,& 2(x_1^{+} + x_1^{-}) + (x_2^{+} + x_2^{-}) \\ s.t. \quad \,\,\,& x_1 + 2(x_2^{+} + x_2^{-}) \leqslant 8 \\ & x_1 = x_1^{+} - x_1^{-} \\ & x_2 = x_2^{+} - x_2^{-} (\text{可以删去}) \\ & -5 \leqslant x_1, x_2 \leqslant 5 \\ & 0 \leqslant x_i^{+}, x_i^{-}\leqslant 5, \forall i = 1, 2 \end{aligned} maxs.t.2(x1++x1−)+(x2++x2−)x1+2(x2++x2−)⩽8x1=x1+−x1−x2=x2+−x2−(可以删去)−5⩽x1,x2⩽50⩽xi+,xi−⩽5,∀i=1,2 这个是不等价的。可以自行验证。这样的话，会出现 x 1 = 0 , x 1 + = 5 , x 1 − = 5 x_1 = 0, x_1^{+} =5, x_1^{-}=5 x1=0,x1+=5,x1−=5， 也满足 x 1 = x 1 + − x 1 − x_1 = x_1^{+} - x_1^{-} x1=x1+−x1−。 总结含有绝对值形式的线性化。 情况1： 目标函数为 min \min min，例如 min ∣ x ∣ x ⩾ 0 \begin{aligned} \min \,\,\,& |x| \\ &x \geqslant 0 \end{aligned} min∣x∣x⩾0 则可以引入辅助变量 y y y，用下面的形式等价线性化 min y s . t . y ⩾ x y ⩾ − x \begin{aligned} \min \,\,\, y \\ s.t. \,\,\, &y \geqslant x \\ &y \geqslant -x \end{aligned} minys.t.y⩾xy⩾−x 情况2： 目标函数为 max \max max例如下面 max 2 ∣ x 1 ∣ + ∣ x 2 ∣ s . t . ∣ x 1 ∣ + 2 ∣ x 2 ∣ ⩽ 8 − 5 ⩽ x 1 , x 2 ⩽ 5 \begin{aligned} \max \quad \,\,\,& 2|x_1| + |x_2| \\ s.t. \quad \,\,\,& |x_1| + 2|x_2| \leqslant 8 \\ & -5 \leqslant x_1, x_2 \leqslant 5 \end{aligned} maxs.t.2∣x1∣+∣x2∣∣x1∣+2∣x2∣⩽8−5⩽x1,x2⩽5 则需要引入两组辅助变量 x i + , x i − , ∀ i = 1 , 2 x_i^{+}, x_i^{-}, \forall i =1,2 xi+,xi−,∀i=1,2。其中 x i + = max { 0 , x i } x i − = max { 0 , − x i } \begin{aligned} &x_i^{+} = \max\{0, x_i\} \\ &x_i^{-} = \max\{0, -x_i\} \end{aligned} xi+=max{0,xi}xi−=max{0,−xi} 因此，就有 x i = x i + − x i − ∣ x i ∣ = x i + + x i − \begin{aligned} &x_i = x_i^{+} - x_i^{-} \\ &|x_i| = x_i^{+} + x_i^{-} \end{aligned} xi=xi+−xi−∣xi∣=xi++xi− 最终变化为 max 2 ( x 1 + + x 1 − ) + ( x 2 + + x 2 − ) s . t . ( x 1 + + x 1 − ) + 2 ( x 2 + + x 2 − ) ⩽ 8 x 1 = x 1 + − x 1 − x 2 = x 2 + − x 2 − x 1 abs = x 1 + + x 1 − x 2 abs = x 2 + + x 2 − x 1 abs ⩾ x 1 x 1 abs ⩾ − x 1 x 2 abs ⩾ x 2 x 2 abs ⩾ − x 2 − 5 ⩽ x 1 , x 2 ⩽ 5 0 ⩽ x i + , x i − , x i abs ⩽ 5 , ∀ i = 1 , 2 \begin{aligned} \max \quad \,\,\,& 2(x_1^{+} + x_1^{-}) + (x_2^{+} + x_2^{-}) \\ s.t. \quad \,\,\,& (x_1^{+} + x_1^{-}) + 2(x_2^{+} + x_2^{-}) \leqslant 8 \\ & x_1 = x_1^{+} - x_1^{-} \\ & x_2 = x_2^{+} - x_2^{-} \\ & x_1^{\text{abs}} = x_1^{+} + x_1^{-} \\ & x_2^{\text{abs}} = x_2^{+} + x_2^{-} \\ & x_1^{\text{abs}} \geqslant x_1 \\ & x_1^{\text{abs}} \geqslant -x_1 \\ & x_2^{\text{abs}} \geqslant x_2 \\ & x_2^{\text{abs}} \geqslant -x_2 \\ & -5 \leqslant x_1, x_2 \leqslant 5 \\ & 0 \leqslant x_i^{+}, x_i^{-}, x_i^{\text{abs}}\leqslant 5, \forall i = 1, 2 \end{aligned} maxs.t.2(x1++x1−)+(x2++x2−)(x1++x1−)+2(x2++x2−)⩽8x1=x1+−x1−x2=x2+−x2−x1abs=x1++x1−x2abs=x2++x2−x1abs⩾x1x1abs⩾−x1x2abs⩾x2x2abs⩾−x2−5⩽x1,x2⩽50⩽xi+,xi−,xiabs⩽5,∀i=1,2 注意：在一些特定 的情况下，表示绝对值的辅助变量 x i abs x_i^{\text{abs}} xiabs也是可以不引入的，也同样可以保证等价。主要看对应的约束和目标函数是否能够在共同的耦合下，使得 x 1 = 0 , x 1 + = 5 , x 1 − = 5 x_1 = 0, x_1^{+} =5, x_1^{-}=5 x1=0,x1+=5,x1−=5， 此时 x 1 = x 1 + − x 1 − x_1 =x_1^{+} - x_1^{-} x1=x1+−x1−，但是 ∣ x 1 ∣ ≠ x 1 + + x 1 − |x_1| \ne x_1^{+} + x_1^{-} ∣x1∣=x1++x1−的这种情况出现。欢迎关注我们的微信公众号 运小筹
公众号往期推文如下
|
【本文地址】
今日新闻 |
推荐新闻 |