非线性整数规划模型
Gurobi求解代码 线性化
作者：刘兴禄， 清华大学
清华-伯克利深圳学院，博士在读
欢迎关注我们的微信公众号 运小筹
非线性整数规划模型考虑下面的非线性0-1整数规划
max y + x z s . t . 2 x + 3 y ⩽ 3 y + z ⩽ 1 x , y , z ∈ { 0 , 1 } begin{aligned} max quad & y + xz \ s.t. quad & 2x + 3y leqslant 3 \ & y + z leqslant 1 \ & x, y, z in {0, 1} end{aligned} maxs.t.y+xz2x+3y⩽3y+z⩽1x,y,z∈{0,1}
Gurobi求解代码from gurobipy import *
model = Model('non-linear model')
x = model.addVar(lb=0, ub=1, vtype=GRB.BINARY, name='x')
y = model.addVar(lb=0, ub=1, vtype=GRB.BINARY, name='y')
z = model.addVar(lb=0, ub=1, vtype=GRB.BINARY, name='z')
model.setObjective(y + x*z, GRB.MAXIMIZE)
model.addConstr(2 * x + 3*y <= 3)
model.addConstr(y + z <= 1)
model.optimize()
print('x:', x.x)
print('y:', y.x)
print('z:', z.x)
求解结果
Optimal solution found (tolerance 1.00e-04) Best objective 1.000000000000e+00, best bound 1.000000000000e+00, gap 0.0000% x: 0.0 y: 1.0 z: 0.0线性化
令
w
=
x
z
w=xz
w=xz，且
w
∈
{
0
,
1
}
win {0, 1}
w∈{0,1}引入下面的辅助约束
w
⩽
x
w
⩽
z
w
⩾
x
+
z
−
1
begin{aligned} &w leqslant x \ &w leqslant z \ &w geqslant x + z - 1 end{aligned}
w⩽xw⩽zw⩾x+z−1
原模型等价为
max y + w s . t . 2 x + 3 y ⩽ 3 y + z ⩽ 1 w ⩽ x w ⩽ z w ⩾ x + z − 1 x , y , z , w ∈ { 0 , 1 } begin{aligned} max quad &y + w \ s.t. quad &2x + 3y leqslant 3 \ &y + z leqslant 1 \ &w leqslant x \ &w leqslant z \ &w geqslant x + z - 1 \ &x, y, z, w in {0, 1} end{aligned} maxs.t.y+w2x+3y⩽3y+z⩽1w⩽xw⩽zw⩾x+z−1x,y,z,w∈{0,1}
具体推导见视频详解。
from gurobipy import *
model = Model('non-linear model')
x = model.addVar(lb=0, ub=1, vtype=GRB.BINARY, name='x')
y = model.addVar(lb=0, ub=1, vtype=GRB.BINARY, name='y')
z = model.addVar(lb=0, ub=1, vtype=GRB.BINARY, name='z')
w = model.addVar(lb=0, ub=1, vtype=GRB.BINARY, name='w')
model.setObjective(y + w, GRB.MAXIMIZE)
model.addConstr(2 * x + 3*y <= 3)
model.addConstr(y + z <= 1)
model.addConstr(w <= x)
model.addConstr(w <= z)
model.addConstr(w >= x + z - 1)
model.optimize()
print('x:', x.x)
print('y:', y.x)
print('z:', z.x)
print('w:', z.x)
求解结果为
Optimal solution found (tolerance 1.00e-04) Best objective 1.000000000000e+00, best bound 1.000000000000e+00, gap 0.0000% x: 0.0 y: 1.0 z: 0.0 w: 0.0
可见结果是一致的。
欢迎关注我们的微信公众号 运小筹
公众号往期推文如下
