不同类型优化问题建模求解

本章将会介绍如何在杉数求解器COPT中,对不同类型的优化问题进行建模和求解。章节内容构成如下:

杉数求解器COPT目前支持建模和求解的问题类型与相应求解算法如 表 22 所示:

表 22 COPT支持建模求解的问题类型与求解算法

问题类型

求解算法

线性规划(LP)

对偶单纯形法、内点法

二阶锥规划(SOCP)

内点法

凸二次规划(QP)

内点法

凸二次约束规划(QCP)

内点法

半定规划(SDP)

内点法、交替乘子下降法

混合整数线性规划(MILP)

分支切割法

混合整数二阶锥规划(MISOCP)

分支切割法

混合整数凸二次规划(MIQP)

分支切割法

混合整数凸二次约束规划(MIQCP)

分支切割法

杉数求解器COPT支持优化问题的3种输入方式:文件输入、编程接口建模、第三方建模工具包;

  1. 模型文件输入,请参考 COPT支持的文件格式

  2. COPT支持的编程语言接口有:

    • C接口

    • C++接口

    • C#接口

    • Java接口

    • Python接口

    • Fortran接口

  3. COPT目前支持的第三方建模工具接口有:

    • AMPL

    • GAMS

    • Julia

    • Pyomo

    • PuLP

    • CVXPY

线性规划(LP)

线性规划(Linear Programming,简称LP),作为运筹学中最基本和最重要的分支,有着广泛的应用场景。

线性规划问题的目标函数和约束条件都是线性的。

数学模型

数学形式如下:

(9)\[\begin{split}\min\quad &\sum_{i=0}^{m-1}c_jx_j +c^f\\ \mathrm{s.t.}\quad &l_i^c\leq \sum_{j=0}^{n-1}a_{ij}x_j\leq u_i^c,\qquad i=1,2,\cdots,m-1 \\ &l_j^v\leq x_j\leq u_j^v,\qquad j=1,2,\cdots,n-1\end{split}\]

更简洁地,也可以用向量和矩阵进行表示:

(10)\[\begin{split}\min\quad &c^Tx +c^f\\ \mathrm{s.t.}\quad &l^c\leq Ax\leq u^c \\ &l^v\leq x\leq u^v\end{split}\]

模型中的变量和参数含义如下:

  • 问题规模:\(m\) 表示约束条件的个数,\(n\) 表示决策变量的个数

  • 决策变量:\(x=(x_j)_{j=0}^{n-1}\in\mathbb{R}^n\)

  • 变量取值范围:\(l^v, u^v\in\mathbb{R}^n\),其中 \(l^v\) 表示变量下界,\(u^v\) 表示变量上界

  • 约束边界:\(l^c, u^c\in\mathbb{R}^m\),其中 \(u^c\) 表示约束下界,\(u^c\) 表示约束上界

  • 线性约束的系数矩阵:\(A=(a_{ij})_{m\times n}\in\mathbb{R}^{m\times n}\)

  • 目标函数中变量系数:\(c\in\mathbb{R}^n\) 表示目标函数中变量的系数,\(c^f\) 表示目标函数中的常数项

建模

在COPT中构建线性规划(LP)模型并求解的基本步骤如下:

  1. 创建COPT求解环境和求解模型

  2. 添加模型参数

  3. 构建线性规划模型:

    • 添加决策变量

    • 添加线性约束

    • 设置线性目标函数

  4. 设置求解参数并求解

  5. 获取求解结果

建模:添加线性约束

杉数求解器COPT提供添加线性约束的三种方式:

  1. 向模型中添加单条线性约束

  2. 批量添加一组线性约束

  3. 添加单条带上下界的线性约束

在向模型中添加线性约束时,用户可以指定的参数主要有:

  • expr/builder:线性约束表达式或线性约束构建器

  • sense:约束类型,可取值请参考 常数章节:约束类型

  • name:线性约束名称

如果是添加带上下界的线性约束,还需指定:

  • lb:线性约束下界

  • ub:线性约束上界

在不同编程接口中实现方式如 表 23 所示:

表 23 添加线性约束的函数

编程接口

添加单条约束

批量添加一组约束

C

COPT_AddRow

COPT_AddRows

C++

Model::AddConstr()

Model::AddConstrs()

C#

Model.AddConstr()

Model.AddConstrs()

Java

Model.addConstr()

Model.addConstrs()

Python

Model.addConstr()

Model.addConstrs()

注意

  • 关于线性约束的相关操作,在不同编程接口中的函数名称、调用方式,以及 参数名称略有不同 ,但是实现的功能和参数含义是一致的;

  • COPT支持使用约束类型来定义约束,但我们 推荐直接使用上下边界来定义约束

  • 在C API 中,以系数矩阵作为参数输入的方式添加线性约束;

  • 在Python API 中,另外提供添加带上下界线性约束的成员方法: Model.addBoundConstr()

线性规划问题示例

(11)\[\begin{split}\text{最大化:} & \\ & 1.2 x + 1.8 y + 2.1 z \\ \text{约束:} & \\ & 1.5 x + 1.2 y + 1.8 z \leq 2.6 \\ & 0.8 x + 0.6 y + 0.9 z \geq 1.2 \\ \text{变量范围:} & \\ & 0.1 \leq x \leq 0.6 \\ & 0.2 \leq y \leq 1.5 \\ & 0.3 \leq z \leq 2.8\end{split}\]

不同编程接口中对应代码实现请参考:COPT快速入门章节

在COPT提供的编程接口中,除C语言外,其余面向对象的编程接口(C#, C++, Java, Python)均提供线性约束相关的类:

求解

对于线性规划问题,杉数求解器COPT提供的求解算法有:单纯形法和内点法,通过设置优化参数 "LpMethod" 可以进行指定。 通过设置其他线性规划的相关优化参数,可以控制求解算法的具体工作流程,详细请参考 参数章节:线性规划相关

关于线性规划问题的求解日志请参考 求解日志章节:单纯形法内点法

相关属性和信息

线性规划相关属性

线性规划问题模型描述相关的属性如 表 24 所示:

表 24 线性规划模型描述相关属性

属性名

类型

属性含义

Cols

整数属性

变量(系数矩阵列)个数

Rows

整数属性

线性约束(系数矩阵行)数目

Elems

整数属性

系数矩阵中非零元素个数

LpObjval

浮点数属性

内点法求解的迭代数限制

SimplexIter

整数属性

单纯形法迭代循环数

BarrierIter

整数属性

内点法迭代循环数

线性规划问题求解结果相关的属性如 表 25 所示:

表 25 线性规划求解结果相关属性

属性名

类型

属性含义

LpStatus

整数属性

线性规划求解状态

HasLpSol

整数属性

是否可以提供线性规划的解值

HasBasis

整数属性

是否可以提供线性规划的基

LpObjval

浮点数属性

内点法求解的迭代数限制

SimplexIter

整数属性

单纯形法迭代循环数

BarrierIter

整数属性

内点法迭代循环数

对于线性规划问题的求解结果,COPT还提供相关信息常数,以获取对偶问题的相关信息,如 表 26 所示:

表 26 线性规划对偶问题相关信息

信息名

类型

信息含义

Slack

浮点数信息

松弛变量的取值,也叫做约束的活跃程度(activities)

Dual

浮点数信息

对偶变量的取值

RedCost

浮点数信息

变量的Reduced Cost

在不同编程接口中,属性和信息的获取方式,请参考 属性信息 章节。

二阶锥规划(SOCP)

二阶锥规划(Second-Order Cone Programming,简称SOCP),目标函数是线性函数,约束条件是二阶锥约束和线性约束。

数学模型

二阶锥(SOC):

(12)\[\mathcal{Q}^{n+1} = \left\{(t,x)\in \mathbb{R}\times\mathbb{R}^n\ |\ t\geq \|x\|_2 \right\}\]

二阶锥约束:

\(t\in \mathbb{R}\text{和} x\in \mathbb{R}^n\) 为决策变量时,形如 \(t\geq \|x\|_2\) 称为二阶锥约束。

数学形式如下:

(13)\[\begin{split}\min\quad &c^Tx +c^f\\ \mathrm{s.t.}\quad &l^c\leq Ax\leq u^c \\ &l^v\leq x\leq u^v\\ &Fx+g\in \mathcal{Q}\end{split}\]

模型中的变量和参数含义如下:

  • 决策变量:\(x=(x_j)_{j=0}^{n-1}\in\mathbb{R}^n\)

  • 决策变量取值范围:\(l^v, u^v\in\mathbb{R}^n\),其中 \(l^v\) 表示变量下界,\(u^v\) 表示变量上界

  • 约束边界:\(l^c, u^c\in\mathbb{R}^m\),其中 \(u^c\) 表示线性约束下界,\(u^c\) 表示线性约束上界

  • 线性约束的系数矩阵:\(A=(a_{ij})_{m\times n}\in\mathbb{R}^{m\times n}\)

  • 目标函数中的系数:\(c\in\mathbb{R}^n\) 表示目标函数中变量的系数,\(c^f\) 表示目标函数中的常数项

  • 问题规模:\(m\) 表示线性约束条件的个数,\(n\) 表示决策变量的个数,\(k\) 表示二阶锥约束的个数

其中,锥约束相关参数含义如下:

  • \(F\)\(F\in\mathbb{R}^{k\times n}\) 锥约束的系数矩阵

  • \(g\)\(g\in\mathbb{R}^k\) 锥约束的常数向量

  • \(\mathcal{Q}\):表示 \(k\) 个集合的笛卡尔积, \(\mathcal{Q} = \mathcal{Q}_1\times \mathcal{Q}_2\times \cdots \mathcal{Q}_p\),其中 \(p\) 表示二阶锥约束的个数,\(\mathcal{Q}_i,i\in\{1,2,\cdots,p\}\) 都表示二阶锥。

建模

在COPT中构建二阶锥规划(SOCP)模型并求解的基本步骤如下:

  1. 创建COPT求解环境和求解模型

  2. 添加模型参数

  3. 构建二阶锥规划模型

    • 添加决策变量

    • 添加约束条件(二阶锥约束、线性约束)

    • 设置目标函数

  4. 设置求解参数并求解

  5. 获取求解结果

建模:添加二阶锥约束

杉数求解器COPT支持对以下两种类型的二阶锥约束进行建模:

标准二阶锥

(14)\[Q^n= \left\{x\in \mathbb{R}^n\ \left|\ x_0\geq\sqrt{\sum_{i=1}^{n-1} x_i^2}, x_0\geq0 \right. \right\}\]

常数表示: CONE_QUAD

旋转二阶锥

(15)\[Q^n_r= \left\{x\in \mathbb{R}^n\ \left|\ 2x_0x_1\geq\sum_{i=2}^{n-1} x_i^2, x_0\geq0, x_1\geq 0 \right. \right\}\]

常数表示: CONE_RQUAD

在向模型中添加二阶锥约束时,用户可以指定的参数主要有:

  • ctype:二阶锥约束的类型

    • CONE_QUAD :标准二阶锥

    • CONE_RQUAD:旋转二阶锥

  • cvars:参与构成二阶锥约束的变量

  • dim:二阶锥约束的维度

在不同编程接口中实现方式如 表 27 所示:

表 27 添加二阶锥约束的函数

编程接口

函数

C

COPT_AddCones

C++

Model::AddCone()

C#

Model.addCone()

Java

Model.addCone()

Python

Model.addCone()

注意

  • 关于二阶锥约束建模的相关操作,在不同编程接口中的函数名称、调用方式,以及 参数名称略有不同 ,但是实现的功能和参数含义是一致的;

  • 在提供参与构成二阶锥约束变量时,请按照变量在约束表达式中的顺序依次输入;

  • 在C API 中,以行压缩存储格式提供二阶锥约束的成员,关于C API中稀疏矩阵的压缩存储,请参考 具体示例

  • 在Python API 中,对于指定二阶锥维度的方式,另外提供成员方法: Model.addConeByDim()

二阶锥约束示例

\(x_4,x_1,x_2,x_3\) 构成的标准二阶锥:

(16)\[x_4 \geq \sqrt{x_1^2 + x_2^2 + x_3^2}\]

\(x_3,x_4,x_1,x_2\) 构成的旋转二阶锥:

(17)\[2 x_3 x_4 \geq x_1^2 + x_2^2\]

\(x_4,x_1,x_2,x_3\) 构成的标准二阶锥为例,在不同编程接口中的代码实现如下:

C 接口:

int ncone = 1;
int conetype[] = {COPT_CONE_QUAD};
int conebeg[] = {0};
int conecnt[] = {4};
int coneind[] = {3, 0, 1, 2};
COPT_AddCones(prob, ncone, conetype, conebeg, conecnt, coneind)

C++ 接口:

VarArray cvars;
cvars.PushBack(x4);
cvars.PushBack(x1);
cvars.PushBack(x2);
cvars.PushBack(x3);
model.AddCone(cvars, COPT_CONE_QUAD);

C# 接口:

VarArray cvars = new VarArray();
cvars.PushBack(x4);
cvars.PushBack(x1);
cvars.PushBack(x2);
cvars.PushBack(x3);
model.AddCone(cvars, Copt.Consts.CONE_QUAD);

Java 接口:

VarArray cvars = new VarArray();
cvars.PushBack(x4);
cvars.PushBack(x1);
cvars.PushBack(x2);
cvars.PushBack(x3);
model.addCone(cvars, copt.Consts.CONE_QUAD);

Python 接口:

model.addCone([x4, x1, x2, x3], COPT.CONE_QUAD)

在COPT提供的编程接口中,除C语言外,其余面向对象的编程接口(C#, C++, Java, Python)均提供二阶锥约束相关的类:

二阶锥约束相关属性

  • COPT_INTATTR_CONES"Cones"

    整数属性。

    二阶锥约束的个数。

半定规划(SDP)

半定规划(Semidefinite Programming,简称SDP)的目标函数是线性函数,约束条件半定锥约束和线性约束。

数学模型

正半定锥:

\(\mathcal{S}^n\) 表示 \(n\) 维对称矩阵的集合,则正半定锥表示为:

(18)\[\mathcal{S}_+^n = \left\{X\in \mathcal{S}^n\ |\ u^TXu \geq 0, \forall u\in \mathbb{R}^n\right\}\]

正半定(Positive Semidefinite,简称PSD)变量:

在SDP模型中,决策变量 \(X\in \mathcal{S}_+^n\),也可表示为 \(X\succeq 0\)。决策变量被称为半定变量;构成模型的线性约束中含有半定变量。

半定锥约束和半定约束:

在SDP模型中,\(X\succeq 0\) 习惯上被称为 半定锥约束,而形如 \(A\bullet X = b\) 是含半定变量的线性约束。此处为了表述方便,下文我们将其简称为 半定约束,同时与半定锥约束(\(X\succeq 0\))区分开来。

半定规划的数学形式如下:

(19)\[\begin{split}\min\quad &\sum_{j=0}^{n-1} c_jx_j + \sum_{j=0}^{p-1} C_j \bullet X_j + c^f \\ \text{s.t.}\quad &l_i^c \leq \sum_{j=0}^{n-1} a_{ij} x_j + \sum_{j=0}^{p-1} A_j \bullet X_j \leq u_i^c,\qquad i=0,1, ..., m-1 \\ &l_j^v\leq\qquad\qquad\quad x_j\qquad\qquad \leq u_j^v,\qquad j=0,1, ..., n-1\\ &\qquad\qquad\qquad X_j \succeq 0,\qquad j = 0,1, ..., p-1\end{split}\]

这里运算符 \(\bullet\) 表示矩阵内积运算:

给定两个 \(m\times n\) 维矩阵:\(A = \{a_{ij}\} \in \mathbb{R}^{m\times n}, B = \{b_{ij}\}\in \mathbb{R}^{m\times n}\),矩阵 \(A\) 和矩阵 \(B\) 的内积定义为

(20)\[A\bullet B = \sum_{i=0}^{m-1} \sum_{j=0}^{n-1} a_{ij}b_{ij}\]

模型中的变量和参数含义如下:

  • 问题规模:\(m\) 表示约束条件的个数,\(n\) 表示非半定变量的个数,\(p\) 表示半定变量的个数

  • 决策变量:非半定变量 \(x=(x_j)_{j=0}^{n-1}\in\mathbb{R}^n\),半定变量 \(X_j\in \mathcal{S}_+^{r_j}\)\(j=0, ..., p-1\)

  • 非半定变量取值范围:\(l^v, u^v\in\mathbb{R}^n\),其中 \(l^v\) 表示非半定变量下界,\(u^v\) 表示非半定变量上界

  • 约束边界:\(l^c, u^c\in\mathbb{R}^m\),其中 \(u^c\) 表示约束下界,\(u^c\) 表示约束上界

  • 线性约束的系数矩阵:\(A=(a_{ij})_{m\times n}\in\mathbb{R}^{m\times n}\)\(A_j\in \mathbb{R}^{r_j\times r_j}\)

  • 目标函数中变量系数:\(c\in\mathbb{R}^n\) 表示目标函数中非半定变量的系数,\(C_j\in\mathbb{R}^{r_j\times r_j}\) 表示目标函数中半定变量的系数,\(c^f\) 表示目标函数中的常数项

建模

在COPT中构建半定规划(SDP)模型并求解的基本步骤如下:

  1. 创建COPT求解环境和求解模型

  2. 添加模型参数

  3. 构建半定规划模型:

    • 添加决策变量(半定变量、非半定变量)

    • 添加约束条件(半定约束)

    • 设置目标函数

  4. 设置求解参数并求解

  5. 获取求解结果

建模:添加半定变量、添加半定约束

COPT通过指定半定变量维度(dim)的方式添加半定变量:

  1. 添加单个半定变量

  2. 添加多个半定变量

杉数求解器COPT提供添加半定约束的两种方式:

  1. 先构建半定约束表达式,分别对半定项(半定变量及其对应系数矩阵)和线性项进行组合,再添加至模型中;

  2. 直接给出半定约束表达式(或半定约束构建器)作为参数输入,添加至模型中。

在向模型中添加半定约束时,用户可以指定的参数主要有:

  • expr / builder:半定约束表达式或半定约束构建器

  • rhs:二次约束右端项

  • sense:约束类型,可取值请参考 常数章节:约束类型

  • name:半定约束名称

在不同编程接口中实现方式如 表 28 所示:

表 28 添加半定变量和半定约束的函数

编程接口

添加半定变量

添加半定约束

C

COPT_AddPSDCol / COPT_AddPSDCols

COPT_AddPSDConstr

C++

Model::AddPsdVar() / Model.AddPsdVars()

Model::AddPsdConstr()

C#

Model.AddPsdVar() / Model.AddPsdVars()

Model.AddPsdConstr()

Java

Model.addPsdVar() / Model.addPsdVars()

Model.addPsdConstr()

Python

Model.addPsdVar() / Model.addPsdVars()

Model.addPsdConstr()

注意

  • 关于半定变量、半定约束建模的相关操作,在不同编程接口中的函数名称、调用方式,以及 参数名称略有不同 ,但是实现的功能和参数含义是一致的;

  • 在C API 中,添加半定约束时,需提供非零线性项系数列下标、半定变量列下标等参数,具体请参考 C API函数:构造和修改模型 的函数 COPT_AddPSDConstr

  • 在Python API 中,Model.addConstr() 可以用于添加一条线性约束、半定约束或Indicator约束至模型中,具体请参考 Python API函数:Model类

半定变量和半定约束示例

(21)\[\begin{split}&A\bullet X + x_1 + x_2 = 0.6 \\ &x_1 \geq 0, x_2 \geq 0, X\succeq 0\end{split}\]

其中:

(22)\[\begin{split}&A=\begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix}\end{split}\]

在不同编程接口中的代码实现如下:

C 接口:

{
  /* Matrix A */
  int ndim = 3;
  int nelem = 6;
  int rows[] = {0, 1, 2, 1, 2, 2};
  int cols[] = {0, 0, 0, 1, 1, 2};
  double elems[] = {1.0, 1.0, 1.0, 1.0, 1.0, 1.0};
  retcode = COPT_AddSymMat(prob, ndim, nelem, rows, cols, elems);
  if (retcode) goto exit_cleanup;
}
/* Add PSD columns */
int nPSDCol = 1;
int colDims[] = {3};
retcode = COPT_AddPSDCols(prob, nPSDCol, colDims, NULL);
if (retcode) goto exit_cleanup;
/* Add columns */
int nCol = 2;
retcode = COPT_AddCols(prob, nCol, NULL, NULL, NULL, NULL, NULL, NULL,
NULL, NULL, NULL);
if (retcode) goto exit_cleanup;
/* Add PSD constraints */
{
  int nRowMatCnt = 2;
  int rowMatIdx[] = {0, 1};
  double rowMatElem[] = {1.0, 1.0};
  int nColCnt = 1;
  int psdColIdx[] = {0};
  int symMatIdx[] = {2};
  char cRowSense = COPT_EQUAL;
  double dRowBound = 0.6;
  retcode = COPT_AddPSDConstr(prob, nRowMatCnt, rowMatIdx, rowMatElem, nColCnt,
    psdColIdx, symMatIdx, cRowSense, dRowBound, 0.0, NULL);
  if (retcode) goto exit_cleanup;
}

C++ 接口:

SymMatrix A = model.AddOnesMat(3);
Var x1 = model.AddVar(0.0, COPT_INFINITY, 0, COPT_CONTINUOUS, "x1");
Var x2 = model.AddVar(0.0, COPT_INFINITY, 0, COPT_CONTINUOUS, "x2");
PsdVar barX = model.AddPsdVar(3, "X");
model.AddPsdConstr(A * barX + x1 + x2 == 0.6, "PSD_R");

C# 接口:

SymMatrix A = model.AddOnesMat(3);
Var x1 = model.AddVar(0.0, Copt.Consts.INFINITY, 0, Copt.Consts.CONTINUOUS, "x1");
Var x2 = model.AddVar(0.0, Copt.Consts.INFINITY, 0, Copt.Consts.CONTINUOUS, "x2");
PsdVar barX = model.AddPsdVar(3, "X");
model.AddPsdConstr(A * barX + x1 + x2 == 0.6, "PSD_R");

Java 接口:

SymMatrix A = model.addOnesMat(3);
Var x1 = model.addVar(0.0, copt.Consts.INFINITY, 0, copt.Consts.CONTINUOUS, "x1");
Var x2 = model.addVar(0.0, copt.Consts.INFINITY, 0, copt.Consts.CONTINUOUS, "x2");
PsdVar barX = model.addPsdVar(3, "X");
PsdExpr pexpr = new PsdExpr(x1, 1.0);
pexpr.addTerm(x2, 1.0);
pexpr.addTerm(barX, A);
model.addPsdConstr(pexpr, copt.Consts.EQUAL, 0.6, "PSD_R");

Python 接口:

A = m.addOnesMat(3)
x1 = m.addVar(lb=0.0, ub=COPT.INFINITY, name="x1")
x2 = m.addVar(lb=0.0, ub=COPT.INFINITY, name="x2")
X = m.addPsdVars(3, "BAR_X")
psdc = model.addConstr(A * X + x1 + x2 == 0.6, name="PSD_C")

在COPT提供的编程接口中,除C语言外,其余面向对象的编程接口(C#, C++, Java, Python)均提供半定约束相关的类:

求解

对于半定规划问题,杉数求解器COPT提供的求解算法有:内点法和交替乘子下降法,通过设置优化参数 SDPMethod 可以进行指定。

详细请参考 参数章节:半定规划相关

相关属性

半定规划模型描述相关属性如 表 29 所示:

表 29 半定变量和半定约束相关属性

属性名

类型

属性含义

PSDCols

整数属性

半定变量的个数

PSDElems

整数属性

目标函数中半定项个数

SymMats

整数属性

模型中对称矩阵的个数

PSDConstrs

整数属性

半定约束的个数

HasPSDObj

整数属性

模型的目标函数是否包含半定项

二次规划(QP)

数学模型

凸二次规划(Convex Quadratic Programming,简称QP)的目标函数是凸二次函数,约束条件是线性约束。

数学形式如下:

(23)\[\begin{split}\min\quad &\frac{1}{2} x^TQx + c^Tx + c^f\\ \text{s.t.}\quad &l_i^c\leq\sum_{j=0}^{n-1}a_{ij}x_j\leq u_i^c,\qquad i=0,\cdots,m-1\\ &l_j^v\leq x_j\leq u_j^v,\qquad j=0,1,\cdots,n-1\end{split}\]

模型中的变量和参数含义如下:

  • 决策变量:\(x=(x_j)_{j=0}^{n-1}\in\mathbb{R}^n\)

  • 变量取值范围:\(l^v, u^v\in\mathbb{R}^n\);其中,\(l^v\) 表示变量下界,\(u^v\) 表示变量上界;

  • 约束边界:\(l^c, u^c\in\mathbb{R}^m\);其中,\(l^c\) 表示约束下界,\(u^c\) 表示约束上界;

  • 线性约束系数矩阵:\(A=(a_{ij})_{m\times n}\in\mathbb{R}^{m\times n}\)

  • 目标函数中变量系数:

    • \(Q\in\mathbb{R}^{n\times n}\) 表示目标函数中二次项系数

    • \(c\in\mathbb{R}^n\) 表示目标函数中线性项系数,\(c^f\) 表示目标函数中的常数项

  • 问题规模:\(m\) 表示约束条件数目,\(n\) 表示决策变量个数。

二次约束规划(QCP)

凸二次约束规划(Convex Quadratically Constrained Programming,简称QCP)的目标函数是凸二次函数,约束条件是凸二次约束和线性约束。

数学模型

数学形式如下:

(24)\[\begin{split}\min\quad &\frac{1}{2} x^TQx + c^Tx + c^f\\ \text{s.t.}\quad&\frac{1}{2}x^TP_ix+a^T_ix_j\leq u_i^c,\qquad i=0,\cdots,m-1\\ &l^v\leq x_j\leq u^v,\qquad j=0,1,\cdots,n-1\end{split}\]

模型中的变量和参数含义如下:

  • 决策变量:\(x=(x_j)_{j=0}^{n-1}\in\mathbb{R}^n\)

  • 变量取值范围:\(l^v, u^v\in\mathbb{R}^n\),其中 \(l^v\) 表示变量下界,\(u^v\) 表示变量上界;

  • 约束边界:\(u^c\in\mathbb{R}^m\),其中 \(u^c\) 表示约束上界;

  • 二次约束中的系数:

    • \(P_i\in \mathbb{R}^{n\times n}\)\(i=0,...,m-1\)),

    • \(a_i = (a_{ij})_{n}\in\mathbb{R}^{n}\)

  • 目标函数中变量系数:

    • \(Q\in\mathbb{R}^{n\times n}\) 表示目标函数中二次项系数

    • \(c\in\mathbb{R}^n\) 表示目标函数中线性项系数,\(c^f\) 表示目标函数中的常数项

  • 问题规模:\(m\) 表示约束条件数目,\(n\) 表示决策变量个数。

注意:

  • 杉数求解器COPT目前支持求解凸二次规划和凸二次约束规划问题,此处的 \(Q\)\(P_i\)\(i=0,1,\cdots,n\)) 需要为 正半定矩阵

  • 当约束类型为 >= 时(形如:\(\quad\frac{1}{2}x^TP_ix+\sum_{j=0}^{n-1}a_{ij}x_j\geq l_i^c\)),此处的 \(Q\) 则为 负半定矩阵

  • 从以上数学形式看出,二次约束表达式中包含二次项、线性项和常数项。

建模

在COPT中构建二次约束规划(QCP)模型并求解的基本步骤如下:

  1. 创建COPT求解环境和求解模型

  2. 添加模型参数

  3. 构建二次约束规划模型:

    • 添加变量

    • 添加二次约束

    • 设置二次目标函数

  4. 设置求解参数并求解

  5. 获取求解结果

建模:添加二次约束

杉数求解器COPT提供添加二次约束的两种方式:

  1. 先对构建二次约束表达式,分别对二次项和线性项变量进行组合,再添加至模型中;

  2. 直接给出二次约束表达式(或二次约束构建器)作为参数输入,添加至模型中。

在向模型中添加二次约束时,用户可以指定的参数主要有:

  • expr / builder:二次约束表达式或二次约束构建器

  • rhs:二次约束右端项

  • sense:约束类型,可取值有:COPT_LESS_EQUALCOPT_GREATER_EQUAL

  • name:二次约束名称

在不同编程接口中实现方式如 表 30 所示:

表 30 添加二次约束的函数

编程接口

函数

C

COPT_AddQConstr

C++

Model::AddQConstr()

C#

Model.AddQConstr()

Java

Model.addQConstr()

Python

Model.addQConstr()

注意:

  • 关于二次约束建模相关操作,在不同编程接口中的函数名称、调用方式,以及 参数名称略有不同 ,但是实现的功能和参数含义是一致的;

  • 在C API 中,添加二次约束时,需提供非零线性项系数列下标,二次项下标等参数,具体请参考 C API函数:构造和修改模型 的函数 COPT_AddQConstr

  • 在Python API 中,Model.addQConstr() 可以用于添加一条线性约束二次约束至模型中,具体请参考 Python API函数:Model类 。具体请参考 Python API函数:Model类

二次约束示例

(25)\[x_1^2 + x_2^2 + x_3^2 + x_1 + 2x_2 <= 0\]

在不同编程接口中的代码实现如下:

C 接口:

int nRowMatCnt = 2;
int rowMatIdx[] = {0, 1};
double rowMatElem[] = {1.0, 2.0};

int nQMatCnt = 2;
int qMatRow[] = {0, 1};
int qMatCol[] = {0, 1};
double qMatElem[] = {1.0, 1.0};
char cRowSense = COPT_LESS_EQUAL;
double dRowBound = 0.0;
char *name = "q1";
errcode = COPT_AddQConstr(prob, nRowMatCnt, rowMatIdx, rowMatElem,
                          nQMatCnt, qMatRow, qMatCol, qMatElem,
                          cRowSense, dRowBound, name);

C++ 接口:

model.AddQConstr(x1*x1 + x2*x2 + x1 + 2*x2 <= 0, "q1");

C# 接口:

model.AddQConstr(x1*x1 + x2*x2 + x1 + 2*x2 <= 0, "q1");

Java 接口:

QuadExpr q1 = new QuadExpr(0.0);
q1.addTerm(x1, x1, 1);
q1.addTerm(x2, x2, 1);
q1.addTerm(x1, 1);
q1.addTerm(x2, 2);
model.addQConstr(q1, copt.Consts.LESS_EQUAL, 0, "q1");

Python 接口:

model.addConstr(x1*x1 + x2*x2 + x1 + 2*x2 <= 0, name="q1")

在COPT提供的编程接口中,除C语言外,其余面向对象的编程接口(C#, C++, Java, Python)均提供二阶锥约束相关的类:

相关属性

二次规划和二次约束规划模型描述相关属性如 表 31 所示:

表 31 二次规划和二次约束规划相关属性

属性名

类型

属性含义

QConstrs

整数属性

二次约束的个数

QElems

整数属性

二次目标函数中非零二次项个数

HasQObj

整数属性

模型是否包含二次项目标函数

混合整数规划(MIP)

建模

混合整数规划问题(MIP)指的是模型中部分决策变量的取值为整数型。目前杉数求解器COPT支持整数变量和线性规划、二阶锥规划、二次规划、二次约束规划结合。

MIP问题类型

求解算法

混合整数线性规划(MILP)

分支切割法

混合整数二阶锥规划(MISOCP)

分支切割法

混合整数凸二次规划(MIQP)

分支切割法

混合整数凸二次约束规划(MIQCP)

分支切割法

在COPT中,支持的整数型变量及对应常数表示如下:

  • BINARY

    二进制变量(0-1变量)

  • INTEGER

    整数变量

在向模型中添加决策变量时,

  • 指定参数 vtypeBINARY 添加 0-1 变量;

  • 指定参数 vtypeINTEGER 添加 整数变量。

求解

对于整数规划问题,杉数求解器COPT提供的求解算法有:分支切割法,通过设置优化参数 "MipMethod" 可以进行指定。 通过设置其他整数规划的相关优化参数,可以控制分支切割求解算法的具体工作流程,详细请参考 参数章节:整数规划相关

关于线性规划问题的求解日志请参考 求解日志章节:分支切割法

相关属性

表 32 MIP相关属性总览

属性名

类型

属性含义

Bins

整数属性

二进制变量(列)的个数

Ints

整数属性

整数变量(列)的个数

Indicators

整数属性

Indicator约束的个数

IsMIP

整数属性

模型是否为整数规划模型

NodeCnt

整数属性

分支定界搜索的节点数。

HasMipSol

整数属性

是否存在整数解。

BestObj

浮点数属性

整数规划求解结束时最好的目标函数值。

BestBnd

浮点数属性

整数规划求解结束时最好的下界。

BestGap

浮点数属性

整数规划求解结束时最好的相对容差。

特殊约束

COPT支持构建两种特殊的约束:SOS约束和Indicator约束。

SOS约束

SOS 约束(Special Ordered Set)是一类限制一组变量取值的特殊约束。目前,COPT 支持两种类型的 SOS 约束:

  1. SOS1约束 :该类型约束中指定的一组变量至多有一个变量可取非零值;

  2. SOS2约束 :该类型约束中指定的一组变量至多有两个变量可取非零值,且取非零值的变量顺序要求相邻。

以上两种SOS约束在COPT中分别对应常数如下,在向模型添加SOS约束时可以进行指定:

  • SOS_TYPE1

    SOS1约束

  • SOS_TYPE2

    SOS2约束

在向模型中添加SOS约束时,用户可以指定以下参数:

  • sostype :设置SOS约束的类型

  • vars :参与SOS约束的变量

  • weights :参与SOS约束变量的权重,可选参数,默认为 None

注意

  • 参与构成SOS约束中的变量类型可以为连续变量、二进制变量或整数变量;

  • 若模型中包含SOS约束,则模型为整数规划模型;

  • 关于SOS约束的具体操作和用法,在不同编程接口中的函数名称、调用方式,以及 参数名称略有不同 ,但是实现的功能和参数含义是一样的。

杉数求解器COPT提供相关函数,支持对SOS约束进行一些操作。下面罗列不同编程接口中,添加和获取SOS约束对应的函数:

表 33 添加和获取SOS约束

编程接口

添加SOS约束

获取模型中所有SOS约束

C

COPT_AddSOSs

COPT_GetSOSs

C++

Model::AddSos()

Model::GetSoss()

C#

Model.AddSos()

Model.GetSoss()

Java

Model.addSos()

Model.getSoss()

Python

Model.addSOS()

Model.getSOSs()

关于SOS约束的相关操作,在不同编程接口中,函数的名称、调用方式,以及参数名称略有不同,但是实现的功能和参数含义是一致的。请进一步参考各编程语言API参考手册的对应章节,以获取具体介绍:

在COPT提供的编程接口中,除C语言外,其余面向对象的编程接口(C#, C++, Java, Python)均提供SOS约束相关的类:

  • SOS约束相关操作的封装:

    1. Sos 类:杉数求解器COPT中 SOS 约束相关操作的封装

    2. SosArray 类:方便用户对一组 Sos 类对象进行操作,

  • SOS约束构建器的封装:

    1. SosBuilder 类:是杉数求解器COPT中构建 SOS 约束的构建器的封装,提供了以下成员方法:

    2. SosBuilderArray 类:为方便用户对一组 SosBuilder 类对象进行操作,

以上SOS约束相关的类中成员方法和具体介绍,请进一步参考各编程语言 API 参考手册中的对应内容:

Indicator约束

Indicator约束是一类逻辑关系约束,它以一个二进制类型变量 \(y\) 作为Indicator变量, 根据变量 \(y\) 的取值决定线性约束 \(a^{T}x \leq b\) 是否成立。Indicator约束 的一般表达式:

(26)\[\begin{split} y &= f \rightarrow a^{T}x \leq b\\ f &\in \{0, 1\}\end{split}\]
  • \(y = f\) 时,线性约束成立;

  • \(y \neq f\) 时,线性约束无效(可以被违反)。

构建Indicator约束时,用户需要指定以下参数:

  • binVar :二进制的Indicator变量

  • binval :要求线性约束必须满足的Indicator变量的取值(0或1)

  • builder :线性约束构建器

注意

  • 以上给出的线性约束的一般表达式 \(a^{T}x \leq b\),实际上,线性约束的方向可取 \(\leq\)\(\geq\)\(=\) 三种情形;

  • 若模型包含Indicator约束,则模型为整数规划模型;

  • 关于SOS约束的具体操作和用法,在不同编程接口中的函数名称、调用方式,以及 参数名称略有不同 ,但是实现的功能和参数含义是一样的。

杉数求解器COPT提供相关函数,支持对添加Indicator约束、获取指定Indicator约束对应的Indicator约束构建器,罗列如下:

表 34 不同编程接口添加和获取Indicator约束

编程接口

添加Indicator约束

获取指定Indicator约束构建器

C

COPT_AddIndicator

COPT_GetIndicator

C++

Model::AddGenConstrIndicator()

Model::GetGenConstrIndicator()

C#

Model.AddSos()

Model.GetGenConstrIndicator()

Java

Model.addSos()

Model.getGenConstrIndicator()

Python

Model.addGenConstrIndicator()

Model.getGenConstrIndicator()

关于Indicator约束的构建、添加等操作,在不同编程接口中,函数的名称、调用方式,以及参数名称略有不同,但是实现的功能和参数含义是一致的。请进一步参考各编程语言API参考手册的对应章节,以获取具体介绍:

在COPT支持的编程接口中,除C语言外,其余面向对象的编程接口(C#, C++, Java, Python)均提供Indicator约束相关的类:

  • Indicator约束相关操作的封装:

    1. GenConstr 类:杉数求解器COPT的 Indicator 约束相关操作的封装;

    2. GenConstrArray 类:方便用户对一组 GenConstr 类对象进行操作。

  • Indicator约束构建器的封装:

    1. GenConstrBuilder 类:杉数求解器COPT中构建 Indicator 约束时构建器的封装;

    2. GenConstrBuilderArray 类:方便用户对一组 GenConstrBuilder 类对象进行操作。

以上Indicator约束相关的类中成员方法和具体介绍,请进一步参考各编程语言 API 参考手册中的对应内容:

特殊约束相关属性

COPT提供以下属性,用来描述模型中特殊约束的数目,如 表 35 所示。

不同编程接口中的属性获取方法,请参考:属性章节

表 35 特殊约束相关属性总览

属性名

类型

属性含义

Soss

整数属性

SOS约束的个数

Indicators

整数属性

Indicator约束的个数

IISSOSs

整数属性

组成IIS的SOS约束的数目

IISIndicators

整数属性

组成IIS的Indicator约束的数目

特殊约束的IIS状态

关于不可行模型的IIS计算结果,COPT提供相关函数,以获取SOS约束的IIS状态,请参考 不可行模型的处理章节:获取特殊约束IIS状态