COPT求解器

COPT

简介

杉数求解器COPT（Cardinal Optimizer）是杉数自主研发的针对大规模优化问题的高效数学规划求解器套件，也是支撑杉数端到端供应链平台的核心组件，是目前同时具备大规模混合整数规划、线性规划（单纯形法和内点法）、半定规划、（混合整数）二阶锥规划以及（混合整数）凸二次规划和（混合整数）凸二次约束规划问题求解能力的综合性能数学规划求解器。

其实现在感觉这个 COPT 在国内挺冷门的，自己就来看看官方文档以及一些课程，同步写在这篇文档下吧。

注意事项

在写代码找到了一些很难被发现的东西，就写在这里吧。

  • 对于COPT的变量，在addVar()中默认lb=0,rb=COPT.INFINITY，也就是 $[0,+\infty)$

模型的求解状态

可以通过访问Model.status查看模型求解状态，COPT.UNSTARTED表示当前模型未开始求解。下面列出4个常见的求解状态。

模型求解状态 对应取值
COPT.UNSTARTED 0
COPT.OPTIMAL 1
COPT.INFEASIBLE 2
COPT.UNBOUNDED 3

求解器的优化参数

通过 Model.setParam()设置求解器的优化参数

setParam(paramname, newval)

paramname 为指定的优化参数，newval 为指定的优化参数新值。

下面有一些可能会用到的优化参数，可以随时查看全部：

  • TimeLimit

    • 浮点数参数，优化求解的时间限制（秒）。
    • 默认值 $10^{20}$
    • 最小值 $0$
    • 最大值 $10^{20}$

  • LpMethod

    • 整数参数，求解线性规划问题的算法。
    • 默认值 -1
    • 可选值
      • -1：自动选择：对于线性规划问题，选择对偶单纯形法，对于混合整数线性规划问题，选择对偶单纯形法或内点法之一。
      • 1：对偶单纯形法。
      • 2：内点法
      • 3：直接Crossover。
      • 4：并发求解（同时启动单纯形法与内点法求解）。
      • 5：基于稀疏和数值范围等特征自动选择单纯形法或者内点法。
      • 6：使用一阶算法（PDLP)求解。

结果获取及分析

求解完成后，若模型有最优解，则可以获取模型求解状态、决策变量最优解、目标函数最优值等信息，通过访问Model, Val类的成员属性获取。

Model.getVars()获取模型中所有的决策变量，Model.getConstrs()获取模型中所有的约束条件。

获取模型结果的主要成员属性和方法如下表所示：

信息项 成员属性/方法
模型求解状态 Model.status
目标函数值 Model.objval
所有决策变量 Model.getVars()
变量名称 Var.name, Var.getName()
变量取值 Var.x
变量状态 Var.basis

Model.status == COPT.OPTIMAL 表示模型成功求得最优解，更多模型可能状态如下表所示：

模型求解的状态 含义
COPT.UNSTARTED 未开始求解
COPT.OPTIMAL 成功求解
COPT.INFEASIBLE 模型无解
COPT.UNBOUNDED 最优值无界
COPT.INF_OR_UNB 模型无解或最优值无界
COPT.NUMERICAL 求解遇到数值问题
COPT.NODELIMIT 节点限制前未成功求解
COPT.TIMEOUT 时间限制前未成功求解
COPT.UNFINISHED 求解终止。但由于数值问题，求解器无法给出结果

multidict()

摘要

multidict(data)

描述

将输入的字典对象拆分为键与多个字典对象并返回。

可以将输入的字典对象data拆分为键和多个字典对象。参数data是待拆分的字典对象，每个key映射 n 个值，拆分后会形成 n 个新的字典对象。

例子

1
2
3
4
5
6
7
8
nutrition, minNutrition, maxNutrition = multidict({
    'Vitamin A':  [700, 10000],
    'Vitamin C':  [700, 10000],
    'Vitamin B1': [700, 10000],
    'Vitamin B2': [700, 10000]})
# nutrition = ['Vitamin A', 'Vitamin C', 'Vitamin B1', 'Vitamin B2']
# minNutrition = {'Vitamin A': 700, 'Vitamin C': 700, 'Vitamin B1': 700, 'Vitamin B2': 700}
# maxNutrition = {'Vitamin A': 10000, 'Vitamin C': 10000, 'Vitamin B1': 10000, 'Vitamin B2': 10000}

Model.addGenConstrAnd()

摘要

addGenConstrAnd(resvar, vars, name="")

描述

添加一条逻辑 and 约束，$y=x_1 \ \text{and} \ x_2 \dots\text{and} \ x_n$ 至模型中。

参量

resvar ：等式左端项 y，二进制型

vars：用 and 连接的变量，一般为列表类型

name：约束名称，可选参数

例子

1
2
# Add logical constraint: y = x1 & x2
model.addGenConstrAnd(y, [x1, x2], name="and_constr")

同理，添加一条逻辑 or 约束，为Model.addGenConstrOr()，这里不再赘述。

Model.addGenConstrAbs()

摘要

addGenConstrAbs(resvar, argvar, name="")

描述

添加⼀条形如 $cy+d=|ax+b|$ 的约束到模型中。

参量

resvar：$cy+d$ ，可取值为 Var 类、 MVar 类、 LinExpr 类 或 MLinExpr 对象。

argvar：$ax+b$ ，可取值为 Var 类、 MVar 类、 LinExpr 类 或 MLinExpr 对象。

name：约束名称，可选参数

Model.addGenConstrMin()

摘要

addGenConstrMin(resvar, vars, constant=None, name="")

描述

添加⼀条形如 $y=\min{x_1,x_2,\dots,x_n,c}$ 的约束到模型中。

参量

resvar：等式左端项 y

vars：等式右端 $\min{}$ 函数的变量

constant：等式右端 $\min{}$ 函数中的常数项，可选参数

name：约束名称，可选参数

添加最大值同理：Model.addGenConstrMax()

Model.addGenConstrPWL()

摘要

addGenConstrPWL(xvar, yvar, xpts, ypts, name="")

描述

添加形如 $y=f(x)$ 的约束。

参量

xvar：x ，可取值为 Var 类对象或 MVar 类对象。

yvar：等式左端项 y

xpts： $\hat{x}$，分段点的横坐标，需按照取值从小到大的顺序排列，可取值为 List 类。

ypts：$\hat{y}$，分段点的纵坐标，可取值为 List 类。

name：约束名称，可选参数

例子

1
2
3
4
5
6
7
8
9
10
11
12
13
# Set non-linear functions f(x) and g(z) (converting to PWL constraints)
npts = 101	# 分成 100 份
ptu = []
ptf = []
ptg = []
for i in range(npts):
    ptu.append(lb + (ub - lb) * i / (npts - 1))		# ptu 是间断的 100 个点
    ptf.append(f(ptu[i]))		# ptf 是对应 f(x) 的 100 个点的函数值
    ptg.append(g(ptu[i]))		# ptg 是对应 g(x) 的 100 个点的函数值
print("Ptu:", ptu)
print("Ptf:", ptf)
m.addGenConstrPWL(x, s, ptu, ptf, name='f_exp')
m.addGenConstrPWL(z, t, ptu, ptg, name='g_sqrt')

quicksum()

摘要

quicksum(data)

描述

快速构建表达式，求和

参量

data：生成表达式待加项

例子

1
2
cp.quicksum(fixed_costs[i] * y[i] for i in lines)
# 可以这种写法：列表推导式

这里提一下这里的写法有点奇怪：列表推导式的基本语法如下：[表达式 for 元素 in 可迭代对象 if 条件]，这种可以比较优美的写出一个列表，感觉还挺符合阅读习惯的。

Model.addGenConstrIndicator()

摘要

addGenConstrIndicator(binvar, binval, lhs, sense=None, rhs=None, type=COPT.INDICATOR_IF, name="")

描述

添加一个指定类型的指示约束(Indicator)到模型中

参量

binvar：Indicator变量。

binval：Indicator变量的取值，可取值为 True 或 False 。

lhs：Indicator约束中线性约束的左端项或线性约束构建器。

sense：Indicator约束中线性约束的类型。可选参量（其实可以省略，直接放到 lhs 上一起写））

rhs：Indicator约束中线性约束的左端项或线性约束构建器。（其实可以省略，直接放到 lhs 上一起写）

type：Indicator约束的类型。可选参量。有以下参数可以选：

  • COPT.INDICATOR_IF（If-Then约束）

  • COPT.INDICATOR_ONLYIF （Only-If约束）

  • COPT.INDICATOR_ONLYIF（If-and-Only-If约束）

model.addVars()

摘要

addVars(*indices, lb=0.0, ub=COPT.INFINITY, obj=0.0, vtype=COPT.CONTINUOUS, nameprefix="C")

描述

添加一组变量到模型中，并返回一个 tupledict 类对象， 其键为变量的下标，值为相应的 Var 类对象。

这里的 lb,ub,vtype 与 addVar() 中一致，但是其中 *indices和nameprefix两个参数的设置有所区别，如下表所示：

参数 含义 描述
*indices 变量下标 2种指定方式
nameprefix 变量名称前缀 默认C，实际名称：前缀+下标

参数 *indices 指定决策变量的下标，方式有如下两种：

  1. 指定决策变量的维度规模（dense的形式）

    model.addVars(2)创建2个决策变量，存储在一维数组中，形如$x[0],x[1],x[2]$

    model.addVars(2,3)创建6个决策变量，存储在二维数组中，形如$x[0,0],x[0,1],…,x[1,2]$

    model.addVars(2,3,4)创建24个决策变量，存储在三维数组中，形如$x[0,0,0],x[0,0,1],…,x[1,1,2]$

  2. 通过提供具体的下标列表(tuplelist)(sparse的形式)，tuplelist是list的子类，其中的每个元素是tuple类型：

可以看这个例子，

数学建模
Math 线性规划 COPT求解器

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！