Gurobi+Python 求解NLP、MIP、QCP问题_miqcp

摘要：

对NLP、MIP、QCP、PWL问题进行介绍，利用Gurobi+Python 求解规划问题。

非线性规划（NLP）

简介：

非线性规划模型(Nonlinear Programming, NLP)，是指目标函数和约束条件中至少有一个是非线性的优化问题。非线性规划是实际问题中经常遇到且具有挑战性的问题。与线性规划不同，非线性规划涉及到非线性函数的求解，因此需要使用不同的求解方法和工具。

非线性规划问题的解决需要采用专门的算法和方法。其中一些方法包括：

1. 梯度法（Gradient method）：梯度法是一种常见的求解非线性规划问题的方法。通过计算目标函数的梯度和Hessian矩阵，来找到函数的最优解。但梯度法无法保证找到全局最优解。

2. 牛顿法（Newton's method）：牛顿法基于泰勒级数做近似，通过一阶导数和二阶导数来逼近原目标函数。牛顿法有较快的收敛速度，但需要计算Hessian矩阵的逆矩阵，计算量大，且不保证全局最优解。

3. 共轭梯度法（Conjugate Gradient method）：共轭梯度法是牛顿法的改进版，可以提高计算效率和精度，但还是无法保证全局最优解。

4. 动态规划（Dynamic Programming）：动态规划是一种用于优化决策问题的算法，它可以通过构建状态转移方程来求解非线性规划问题，该方法保证找到全局最优解，但计算量较大。

5. 遗传算法（Genetic Algorithm）：遗传算法是一种模拟生物进化的算法，通过产生随机种群，交叉和变异的方式逐步进化，以找到适应度最高的个体。该方法适用于复杂的非线性规划问题，但计算效率较低。

6. 粒子群算法（Particle Swarm Optimization）：粒子群算法是一种模拟鸟群或鱼群等自组织行为的算法。通过不断寻找最优解和试图逃离局部最优解之间的平衡，来优化目标函数。该方法适用于高维非线性规划问题，对参数的设置比较敏感。

NLP广泛应用于经济学、工程学、物理学、生物学等领域。例如，在经济学中，非线性规划可用于最优化投资组合，最小化生产成本等问题。在工程学中，它可用于最优化设计、最小化成本等问题。

非线性规划算例：

此时需对参数进行设置！且最高次数不超过2！

参数设置方法：M_NLP.Params.NonConvex=2

输出：使用函数 m.getVars()，得到变量名：{v.varName}，取值：{v.x}

# 这是一个非线性规划模型(NLP,Nonlinear Programming)
 
#  max a+d(a+b+c)+b
#  s.t ab+cd>=20
#      a^2+b^2+c^2+d^2<=30
#      1<=a,b,c,d<=3
 
 
# 这是一个非线性规划模型(NLP,Nonlinear Programming)
 
#  max a+d(a+b+c)+b
#  s.t ab+cd>=20
#      a^2+b^2+c^2+d^2<=30
#      1<=a,b,c,d<=3
 
 
import gurobipy as gp
from gurobipy import GRB
 
# 模型定义
m = gp.Model("NLP")  # 非线性
 
# 变量声明
x = m.addVars(4,vtype=GRB.CONTINUOUS,  lb=1, ub=3)  # num_x个变量，类型为连续
 
 
 
# 添加约束
m.addConstr(x[0] * x[0] + x[1] * x[1] + x[2] * x[2] + x[3] * x[3] <= 30,  "a")
m.addConstr(x[0] * x[1]+ x[2] * x[3] <= 20,"b")
m.Params.NonConvex=2
 
# 目标函数
m.setObjective(x[0] + x[3] * (x[0] + x[1] + x[2])+x[1], sense=GRB.MAXIMIZE)
 
# 模型求解
 
m.optimize()
 
# 获取结果并打印
for v in m.getVars():
    print(f'变量名：{v.varName},取值：{v.x}')
print(f'目标值：{m.ObjVal}')

 输出：

混合整数规划（MIP）

简介：

 官网教程：Mixed-Integer Programming (MIP) – A Primer on the Basics - Gurobi Optimization

整数规划是一种数学优化问题，它的目标是在满足某些线性约束条件的前提下，找到一组整数解，使得目标函数的值最小或最大。

求解整数规划问题是一个NP-hard问题，即不存在一个多项式时间的算法可以精确地解决所有的整数规划问题。因此，通常采用启发式算法（Heuristics）、分支定界法（Branch-and-Bound）、割平面法（Cutting Planes）等近似求解方法来解决整数规划问题。可分为纯整数规划，0-1整数规划、混合整数规划。

混合整数规划（Mixed Integer Programming，MIP），指的是在一个线性规划问题中，既包含实数变量，又包含整数变量的情况。通常采用类似于整数规划的分支定界算法等方法来求解。

• MIQP（Mixed Integer Quadratic Programming）：具有二次目标但没有二次约束的混合整数二次规划问题。
• MIQCP（Mixed Integer Quadratically Constrained Programming）：具有二次约束的混合整数二次约束规划问题。
• MILP（Mixed Integer Linear Programming）：没有任何二次特征的模型，混合整数线性规划问题。
   

混合整数规划算例：

官网案例：mip1.py - Gurobi Optimization，mip2.py - Gurobi Optimization

变量类型：

常用vtype： GRB.BINARY（01）, GRB.INTEGER（整数）, GRB.CONTINUOUS（连续） 

# This example formulates and solves the following simple MIP model:
#  maximize
#        x +   y + 2 z
#  subject to
#        x + 2 y + 3 z <= 4
#        x +   y       >= 1
#        x, y  binary
#        0 <= z <= 1
 
import gurobipy as gp
from gurobipy import GRB
 
# Create a new model
m = gp.Model("mip")
 
# Create variables
x = m.addVar(vtype=GRB.BINARY, name="x")
y = m.addVar(vtype=GRB.BINARY, name="y")
z = m.addVar(vtype=GRB.CONTINUOUS, ub=1, lb=0, name="z")
# Set objective
m.setObjective(x + y + 2 * z, GRB.MAXIMIZE)
 
# Add constraint: x + 2 y + 3 z <= 4
m.addConstr(x + 2 * y + 3 * z <= 4, "c0")
 
# Add constraint: x + y >= 1
m.addConstr(x + y >= 1, "c1")
 
# Optimize model
m.optimize()
 
for v in m.getVars():
    print('%s %g' % (v.VarName, v.X))
 
print('Obj: %g' % m.ObjVal)

输出：

二次约束规划（QCP）

简介：

二次约束规划（Quadratically Constrained Programming，QCP），旨在寻求包含二次约束条件的目标函数的最小值。这些约束条件通常采用二次不等式或者等式的形式来描述。

1. 信赖域法：该方法将QCP问题转化为一个等价的最小化问题，并利用Trust Region算法进行求解。

2. 内点法：该方法将QCP问题转化为一个等价的凸优化问题，并使用迭代法令目标函数达到极小值。

3. 全局优化方法：该方法使用分支定界、遗传算法等全局优化方法寻求全局最优解。

4. 半定规划法：该方法将QCP问题转化为等价的半定规划问题，并使用内点法等优化算法进行求解。

5. 分解法：该方法将QCP问题拆分为多个小的二次规划问题，并使用牛顿法、共轭梯度法、广义梯度法等求解子问题。

6. 符号推导法：该方法使用数学符号分析和推导技术来求解问题。

QCP问题在实际应用中广泛存在，例如在机器学习中的支持向量机、数据拟合、模式识别等领域，都需要利用QCP问题来寻求最优解。

二次约束规划算例：

变量约束：

1. 变量、约束条件、目标的系数取值合适的范围，使得变量的优化值范围在 [1e+4,1e+4] 之间，约束取值在 [-1e+4, 1e+4] 之间，目标取值 [-1e+4, 1e+4] 之间；

2. 最大系数/最小系数 的比值在 1e+9 之内。

参数设置方法：M_NLP.Params.NonConvex=2，且最高次数不超过2！

# 这是一个二次约束规划模型(QCP)
 
#  max -3a^2-10a+b^2-3b
#  s.t a+b^2>=2.5
#     2a+b=1
 
import gurobipy as gp
from gurobipy import GRB
 
# 模型定义
m = gp.Model("QCP")  # 非线性
 
# 变量声明
a = m.addVar(vtype=GRB.CONTINUOUS, lb=-1e+4, ub=1e+4, name="a")
b = m.addVar(vtype=GRB.CONTINUOUS, lb=-1e+4, ub=1e+4, name="b")
 
# 添加约束
m.addConstr(a + b * b >= 2.5, "con1")
m.addConstr(2 * a + b == 1, "con2")
m.Params.NonConvex = 2
 
# 目标函数
m.setObjective(-3 * a *a - 10 * a + b *b - 3 * b, sense=GRB.MAXIMIZE)
 
# 模型求解
 
m.optimize()
 
# 获取结果并打印
for v in m.getVars():
    print(f'变量名：%s,取值：%f' % (v.varName, v.x))
print(f'目标值：{m.ObjVal}')

输出：