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

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

线性规划（LP）
二阶锥规划（SOCP）
半定规划（SDP）
二次规划（QP）
二次约束规划（QCP）
混合整数规划（MIP）
特殊约束

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

表 23 COPT支持建模求解的问题类型与求解算法
问题类型	求解算法
线性规划(LP)	对偶单纯形法、内点法
二阶锥规划(SOCP)	内点法
凸二次规划(QP)	内点法
凸二次约束规划(QCP)	内点法
半定规划(SDP)	内点法、交替乘子下降法
混合整数线性规划(MILP)	分支切割法
混合整数二阶锥规划(MISOCP)	分支切割法
混合整数凸二次规划(MIQP)	分支切割法
混合整数凸二次约束规划(MIQCP)	分支切割法

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

模型文件输入，请参考 COPT支持的文件格式。
COPT支持的编程语言接口有：
- C接口
- C++接口
- C#接口
- Java接口
- Python接口
- Fortran接口
COPT目前支持的第三方建模工具接口有：
- AMPL
- GAMS
- Julia
- Pyomo
- PuLP
- CVXPY

线性规划（LP）

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

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

数学模型

数学形式如下：

(11)\[\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}\]

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

(12)\[\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）模型并求解的基本步骤如下：

创建COPT求解环境和求解模型
添加模型参数
构建线性规划模型：
- 添加决策变量
- 添加线性约束
- 设置线性目标函数
设置求解参数并求解
获取求解结果

建模：添加线性约束

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

向模型中添加单条线性约束
批量添加一组线性约束
添加单条带上下界的线性约束

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

expr/builder：线性约束表达式或线性约束构建器
sense：约束类型，可取值请参考常数章节：约束类型
name：线性约束名称

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

lb：线性约束下界
ub：线性约束上界

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

表 24 添加线性约束的函数
编程接口	添加单条约束	批量添加一组约束
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() 。

线性规划问题示例

(13)\[\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）均提供线性约束相关的类：

线性约束相关操作的封装
1. Constraint 类：杉数求解器COPT中线性约束相关操作的封装；
2. ConstrArray 类：方便用户对一组 Constraint 类对象进行操作。
线性约束构建器的封装
1. ConstrBuilder 类：杉数求解器COPT中构建线性约束构建器的封装；
2. ConstrBuilderArray 类：为方便用户对一组 ConstrBuilder 类对象进行操作。
C++ API： Constraint类， ConstrArray类， ConstrBuilder类， ConstrBuilderArray类
C# API： Constraint类， ConstrArray类， ConstrBuilder类， ConstrBuilderArray类
Java API： Constraint类， ConstrArray类， ConstrBuilder类， ConstrBuilderArray类
Python API： Constraint类， ConstrArray类， ConstrBuilder类， ConstrBuilderArray类

求解

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

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

二阶锥规划（SOCP）

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

数学模型

二阶锥(SOC)：

(14)\[\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\) 称为二阶锥约束。

数学形式如下：

(15)\[\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）模型并求解的基本步骤如下：

创建COPT求解环境和求解模型
添加模型参数
构建二阶锥规划模型
- 添加决策变量
- 添加约束条件（二阶锥约束、线性约束）
- 设置目标函数
设置求解参数并求解
获取求解结果

建模：添加二阶锥约束

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

标准二阶锥

(16)\[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

旋转二阶锥

(17)\[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：二阶锥约束的维度

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

表 28 添加二阶锥约束的函数
编程接口	函数
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\) 构成的标准二阶锥：

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

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

(19)\[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）均提供二阶锥约束相关的类：

二阶锥约束相关操作的封装
1. Cone 类：杉数求解器的二阶锥约束的相关操作的封装；
2. ConeArray 类：方便用户对一组 Cone 类对象进行操作。
二阶锥约束构建器的封装
1. ConeBuilder 类：杉数求解器中构建二阶锥约束的构建器的封装；
2. ConeBuilderArray 类：为方便用户对一组 ConeBuilder 类对象进行操作。
C++ API： Cone类， ConeArray类， ConeBuilder类， ConeBuilderArray类
C# API： Cone类， ConeArray类， ConeBuilder类， ConeBuilderArray类
Java API： Cone类， ConeArray类， ConeBuilder类， ConeBuilderArray类
Python API： Cone类， ConeArray类， ConeBuilder类， ConeBuilderArray类

二阶锥约束相关属性

COPT_INTATTR_CONES 或 "Cones"

整数属性。

二阶锥约束的个数。

半定规划（SDP）

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

数学模型

正半定锥：

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

(20)\[\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\)）区分开来。

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

(21)\[\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\) 的内积定义为

(22)\[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）模型并求解的基本步骤如下：

创建COPT求解环境和求解模型
添加模型参数
构建半定规划模型：
- 添加决策变量（半定变量、非半定变量）
- 添加约束条件（半定约束）
- 设置目标函数
设置求解参数并求解
获取求解结果

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

COPT通过指定半定变量维度（dim）的方式添加半定变量：

添加单个半定变量
添加多个半定变量

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

先构建半定约束表达式，分别对半定项（半定变量及其对应系数矩阵）和线性项进行组合，再添加至模型中；
直接给出半定约束表达式（或半定约束构建器）作为参数输入，添加至模型中。

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

expr / builder：半定约束表达式或半定约束构建器
rhs：二次约束右端项
sense：约束类型，可取值请参考常数章节：约束类型
name：半定约束名称

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

表 29 添加半定变量和半定约束的函数
编程接口	添加半定变量	添加半定约束
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类。

半定变量和半定约束示例

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

其中：

(24)\[\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）均提供半定约束相关的类：

构建半定表达式相关操作的封装
1. PsdExpr 类：杉数求解器COPT中用于构建半定表达式时对半定变量的相关组合操作的封装。
半定约束相关操作的封装
1. PsdConstraint 类：杉数求解器半定约束的相关操作的封装；
2. PsdConstrArray 类：方便用户对一组 PsdConstraint 类对象进行操作。
半定约束构建器的封装
1. PsdConstrBuilder 类：杉数求解器中构建半定约束构建器的封装；
2. PsdConstrBuilderArray 类：为方便用户对一组 PsdConstrBuilder 类对象进行操作。
C++ API： PsdExpr类， PsdConstrArray类， PsdConstrBuilder类， PsdConstrBuilderArray类
C# API： PsdExpr类， PsdConstraint类， PsdConstrArray类， PsdConstrBuilder类， PsdConstrBuilderArray类
Java API： PsdExpr类， PsdConstraint类， PsdConstrArray类， PsdConstrBuilder类， PsdConstrBuilderArray类
Python API： PsdExpr类， PsdConstraint类， PsdConstrArray类， PsdConstrBuilder类， PsdConstrBuilderArray类

求解

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

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

二次规划（QP）

数学模型

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

数学形式如下：

(25)\[\begin{split}\min\quad 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）的目标函数是凸二次函数，约束条件是凸二次约束和线性约束。

数学模型

数学形式如下：

(26)\[\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）模型并求解的基本步骤如下：

创建COPT求解环境和求解模型
添加模型参数
构建二次约束规划模型：
- 添加变量
- 添加二次约束
- 设置二次目标函数
设置求解参数并求解
获取求解结果

建模：添加二次约束

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

先对构建二次约束表达式，分别对二次项和线性项变量进行组合，再添加至模型中；
直接给出二次约束表达式（或二次约束构建器）作为参数输入，添加至模型中。

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

expr / builder：二次约束表达式或二次约束构建器
rhs：二次约束右端项
sense：约束类型，可取值有：COPT_LESS_EQUAL 和 COPT_GREATER_EQUAL
name：二次约束名称

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

表 31 添加二次约束的函数
编程接口	函数
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类。

二次约束示例

(27)\[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）均提供二阶锥约束相关的类：

构建二次表达式相关操作的封装
1. QuadExpr 类：杉数求解器COPT中用于构建二次表达式时对变量的相关组合操作的封装。
二次约束相关操作的封装
1. QConstraint 类：杉数求解器二次约束的相关操作的封装；
2. QConstrArray 类：为方便用户对一组 QConstraint 类对象进行操作。
二次约束构建器的封装
1. QConstrBuilder 类：杉数求解器中构建二次约束时的构建器的封装；
2. QConstrBuilderArray 类：为方便用户对一组 QConstrBuilder 类对象进行操作。
C++ API： QuadExpr类， QConstraint类， QConstrArray类， QConstrBuilder类， QConstrBuilderArray类
C# API： QuadExpr类， QConstraint类， QConstrArray类， QConstrBuilder类， QConstrBuilderArray类
Java API： QuadExpr类， QConstraint类， QConstrArray类， QConstrBuilder类， QConstrBuilderArray类
Python API： QuadExpr类， QConstraint类， QConstrArray类， QConstrBuilder类， QConstrBuilderArray类

混合整数规划（MIP）

建模

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

MIP问题类型

求解算法

混合整数线性规划(MILP)

分支切割法

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

分支切割法

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

分支切割法

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

分支切割法

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

BINARY

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

INTEGER

整数变量

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

指定参数 vtype 为 BINARY 添加 0-1 变量；
指定参数 vtype 为 INTEGER 添加整数变量。

求解

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

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

特殊约束

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

SOS约束

SOS 约束（Special Ordered Set）是一类限制一组变量取值的特殊约束。目前，COPT 支持两种类型的 SOS 约束：

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

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

SOS_TYPE1

SOS1约束
SOS_TYPE2

SOS2约束

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

sostype ：设置SOS约束的类型
vars ：参与SOS约束的变量
weights ：参与SOS约束变量的权重，可选参数，默认为 None

注意

参与构成SOS约束中的变量类型可以为连续变量、二进制变量或整数变量；
若模型中包含SOS约束，则模型为整数规划模型；
关于SOS约束的具体操作和用法，在不同编程接口中的函数名称、调用方式，以及 参数名称略有不同 ，但是实现的功能和参数含义是一样的。

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

表 34 添加和获取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参考手册的对应章节，以获取具体介绍：

C API：构造和修改模型
C++ API： Model类
C# API： Model类
Java API： Model类
Python API： Model类

在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 参考手册中的对应内容：

C++ API： Sos类， SosArray类， SosBuilder类， SosBuilderArray类
C# API： Sos类， SosArray类， SosBuilder类， SosBuilderArray类
Java API： Sos类， SosArray类， SosBuilder类， SosBuilderArray类
Python API： SOS类， SOSArray类， SOSBuilder类， SOSBuilderArray类

Indicator约束

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

(28)\[\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约束构建器，罗列如下：

表 35 不同编程接口添加和获取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参考手册的对应章节，以获取具体介绍：

C API：构造和修改模型
C++ API： Model类
C# API： Model类
Java API： Model类
Python API： Model类

在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 参考手册中的对应内容：

C++ API：GenConstr类，GenConstrArray类，GenConstrBuilder类，GenConstrBuilderArray类
C# API：GenConstr类，GenConstrArray类，GenConstrBuilder类，GenConstrBuilderArray类
Java API：GenConstr类，GenConstrArray类，GenConstrBuilder类，GenConstrBuilderArray类
Python API：GenConstr类，GenConstrArray类，GenConstrBuilder类，GenConstrBuilderArray类

特殊约束相关属性

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

不同编程接口中的属性获取方法，请参考：属性章节。

表 36 特殊约束相关属性总览
属性名	类型	属性含义
`Soss`	整数属性	SOS约束的个数
`Indicators`	整数属性	Indicator约束的个数
`IISSOSs`	整数属性	组成IIS的SOS约束的数目
`IISIndicators`	整数属性	组成IIS的Indicator约束的数目

特殊约束的IIS状态

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

属性名	类型	属性含义
`Cols`	整数属性	变量（系数矩阵列）个数
`Rows`	整数属性	线性约束（系数矩阵行）数目
`Elems`	整数属性	系数矩阵中非零元素个数
`LpObjval`	浮点数属性	内点法求解的迭代数限制
`SimplexIter`	整数属性	单纯形法迭代循环数
`BarrierIter`	整数属性	内点法迭代循环数

属性名	类型	属性含义
`LpStatus`	整数属性	线性规划求解状态
`HasLpSol`	整数属性	是否可以提供线性规划的解值
`HasBasis`	整数属性	是否可以提供线性规划的基
`LpObjval`	浮点数属性	内点法求解的迭代数限制
`SimplexIter`	整数属性	单纯形法迭代循环数
`BarrierIter`	整数属性	内点法迭代循环数

信息名	类型	信息含义
`Slack`	浮点数信息	松弛变量的取值，也叫做约束的活跃程度（activities）
`Dual`	浮点数信息	对偶变量的取值
`RedCost`	浮点数信息	变量的Reduced Cost

属性名	类型	属性含义
`Bins`	整数属性	二进制变量（列）的个数
`Ints`	整数属性	整数变量（列）的个数
`Indicators`	整数属性	Indicator约束的个数
`IsMIP`	整数属性	模型是否为整数规划模型
`NodeCnt`	整数属性	分支定界搜索的节点数。
`HasMipSol`	整数属性	是否存在整数解。
`BestObj`	浮点数属性	整数规划求解结束时最好的目标函数值。
`BestBnd`	浮点数属性	整数规划求解结束时最好的下界。
`BestGap`	浮点数属性	整数规划求解结束时最好的相对容差。

表 30 半定变量和半定约束相关属性
属性名	类型	属性含义
`PSDCols`	整数属性	半定变量的个数
`PSDElems`	整数属性	目标函数中半定项个数
`SymMats`	整数属性	模型中对称矩阵的个数
`PSDConstrs`	整数属性	半定约束的个数
`HasPSDObj`	整数属性	模型的目标函数是否包含半定项

表 32 二次规划和二次约束规划相关属性
属性名	类型	属性含义
`QConstrs`	整数属性	二次约束的个数
`QElems`	整数属性	二次目标函数中非零二次项个数
`HasQObj`	整数属性	模型是否包含二次项目标函数

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

线性规划（LP）

数学模型

建模

求解

相关属性和信息

二阶锥规划（SOCP）

数学模型

建模

半定规划（SDP）

数学模型

建模

求解

相关属性

二次规划（QP）

数学模型

二次约束规划（QCP）

数学模型

建模

相关属性

混合整数规划（MIP）

建模

求解

相关属性

特殊约束

SOS约束

Indicator约束

特殊约束相关属性

特殊约束的IIS状态