不可行模型的处理

本章将介绍杉数求解器COPT对不可行问题的两种处理方式，章节内容构成如下：

不可行模型的IIS
不可行模型的可行化松弛

在对现实问题进行建模时，我们通常会遇到模型不可行的情况，对应的解状态码为 COPT.INFEASIBLE 。导致模型不可行的原因通常有以下两种：

描述模型的参数数据输入出错（例如某条约束左端项为空）；
问题本身就不可行，某些约束条件或变量范围之间冲突。

COPT提供两种不可行模型的分析和处理方式，支持的问题类型包括线性规划（LP）和混合整数线性规划（MILP）：

计算不可行模型的IIS：定位导致模型不可行的关键约束和变量范围；
可行化松弛（FeasRelax）：定量给出导致模型不可行的约束或变量范围的冲突值（Violations）。

不可行模型的IIS

IIS（不可约不一致子系统，Irreducible Inconsistent Subsystem）是导致模型不可行的最小冲突集，具有以下特点：

仍然是不可行的；
剔除IIS中任意一条约束或变量范围，这个子系统会变得可行；

注意： COPT计算得到的IIS不一定是最小的，也不是唯一的。因此有时需要多次调整约束条件后，重新计算IIS，才能使模型最终变得可行。

下面是一个不可行线性规划模型的例子：

(39)\[\begin{split}\max\quad &z=12x_{1}+8x_{2}\\ \text{s.t.}\quad &5 x_{1} + 2 x_{2} \geq 140\\ &2 x_{1} + 3 x_{2} \leq 90\\ &4 x_{1} + 2 x_{2} \leq 100\\ &x_{1}, x_{2}\geq0\end{split}\]

模型的可行域如下图所示：

从图示中我们可以清楚看出，相互冲突的两条约束为：

(40)\[\begin{split}&c1:5 x_{1} + 2x_{2} \geq 140\\ &c3:4 x_{1} + 2x_{2} \leq 100\end{split}\]

计算上述模型的IIS结果并写入文件（ .iis 格式），文件内容如下，和图示结果一致：

\Generated by Cardinal Operations

Maximize
   12 x[1] + 8 x[2]
Subject To
 c1: 5 x[1] + 2 x[2] >= 140
 c3: 4 x[1] + 2 x[2] <= 100
END

计算IIS

COPT支持的编程接口提供计算不可行模型IIS的函数，得到一个包含模型中相互冲突约束和变量的集合。用户也可以将IIS计算结果写入文件，指定文件名后缀为 .iis (如： example.iis )，相关函数名称如表 37 所示：

表 37 不可行模型IIS计算功能的函数
编程接口	计算IIS	将IIS计算结果写入文件
C	`COPT_ComputeIIS`	`COPT_WriteIIS`
C++	`Model::ComputeIIS()`	`Model::WriteIIS()`
C#	`Model.ComputeIIS()`	`Model.WriteIIS()`
Java	`Model.computeIIS()`	`Model.writeIIS()`
Python	`Model.computeIIS()`	`Model.writeIIS()`

获取变量和约束的IIS状态

获取变量IIS状态相关函数

计算不可行模型IIS完成后，可以通过获取变量（下/上界）的IIS状态，状态输出值表明变量边界是否在IIS中：

1：指定变量（下界/上界）在IIS中
0：指定变量（下界/上界）不在IIS中

不同编程语言接口提供函数如表 38 所示：

表 38 获取变量IIS状态相关函数
编程接口	变量下界IIS状态	变量上界IIS状态
C	`COPT_GetColLowerIIS`	`COPT_GetColUpperIIS`
C++	`Model::GetVarLowerIIS()`	`Model::GetVarUpperIIS()`
C#	`Model.GetVarLowerIIS()`	`Model.GetVarUpperIIS()`
Java	`Model.getVarLowerIIS()`	`Model.getVarUpperIIS()`
Python	`Model.getVarLowerIIS()`	`Model.getVarUpperIIS()`

注意

以上函数的输入值均可以为单个变量( Var 类对象)或一组变量（ VarArray 类或 tupledict 类对象）；
除C API外，其余编程语言接口的 Var 类还提供获取单个变量IIS状态的函数。

以Python为例， Var.getLowerIIS() 和 Var.getUpperIIS() ；
在Python API中，还可以直接访问 Var 类对象的成员属性获取单个变量的IIS状态：

Var.iislb 获取变量下界IIS状态， Var.iisub 获取变量上界IIS状态。

获取约束IIS状态相关函数

计算不可行模型IIS完成后，COPT支持获取约束（下/上边界）的IIS状态，状态输出值表明约束边界是否在IIS中：

1：指定约束（下边界/上边界）在IIS中
0：指定约束（下边界/上边界）不在IIS中

不同编程语言接口提供函数如表 39 所示：

表 39 获取约束边界IIS状态相关函数
编程接口	约束下边界IIS状态	约束上边界IIS状态
C	`COPT_GetRowLowerIIS`	`COPT_GetRowUpperIIS`
C++	`Model::GetConstrLowerIIS()`	`Model::GetConstrUpperIIS()`
C#	`Model.GetConstrLowerIIS()`	`Model.GetConstrUpperIIS()`
Java	`Model.getConstrLowerIIS()`	`Model.getConstrUpperIIS()`
Python	`Model.getConstrLowerIIS()`	`Model.getConstrUpperIIS()`

以上函数的输入值均可以为单条约束（ Constraint 类对象）或一组约束（ Constraint 类或 ConstrArray 类对象）；
除C API外，其余编程语言接口的 Constraint 类还提供获取单条约束IIS状态的函数。

以Python为例， Constraint.getLowerIIS() 和 Constraint.getUpperIIS() ；
在Python API中，还可以直接访问 Constraint 类对象的成员属性获取单条约束的IIS状态：

Constraint.iislb 获取约束下边界IIS状态， Constraint.iisub 获取约束上边界IIS状态。

获取特殊约束IIS状态

此外，COPT提供如表 40 所示函数，分别获取 SOS 约束和 Indicator 约束的IIS状态。

表 40 获取特殊约束IIS状态相关函数
编程接口	SOS约束	Indicator约束
C	`COPT_GetSOSIIS`	`COPT_GetIndicatorIIS`
C++	`Model::GetSOSIIS()`	`Model::GetIndicatorIIS()`
C#	`Model.GetSOSIIS()`	`Model.GetIndicatorIIS()`
Java	`Model.getSOSIIS()`	`Model.getIndicatorIIS()`
Python	`Model.getSOSIIS()`	`Model.getIndicatorIIS()`

关于计算和获取IIS状态的函数具体用法和详细介绍，请进一步参考不同编程接口API参考手册的对应章节：

IIS相关参数、属性和信息

优化参数

用户可以通过设置参数 "IISMethod" 的不同取值，选择计算IIS的方法。不同编程接口的参数设置方法，请参考：参数章节。

IISMethod

整数参数。

计算IIS的方法。

默认值 -1

可选值

-1: 自动选择。

0: 计算结果质量优先。

1: 计算效率优先。

属性

COPT提供相关属性，用来描述IIS的计算结果，主要包括判断IIS是否存在以及统计IIS中变量和约束数目两类属性。不同编程接口的属性获取方法，请参考：属性章节。

表 41 IIS计算结果相关属性总览
属性名	类型	属性含义
HasIIS	整数属性	是否存在IIS。
IsMinIIS	整数属性	计算出的IIS是否为极小。
IISCols	整数属性	组成IIS的变量边界的数目。
IISRows	整数属性	组成IIS的约束的数目。
IISSOSs	整数属性	组成IIS的SOS约束的数目。
IISIndicators	整数属性	组成IIS的Indicator约束的数目。

示例代码

用户可以将不可行问题写成模型文件的格式，COPT支持读取模型文件后，直接计算不可行模型的IIS。以Python为例，具体实现示例如下：

from coptpy import *
env = Envr()
model = env.createModel("example")
model.read("example.lp")
model.computeIIS()
model.writeIIS ("example.iis")

用户可以在COPT安装包的 "examples" 文件夹下找到不同编程语言处理不可行模型IIS的示例代码，文件名为： "iis_ex1.py" ，以COPT 7.0版本和Python语言为例，相应的文件路径为： "copt70/examples/python/iis_ex1.py" 。

不可行模型的可行化松弛

可行化松弛（Feasibility Relaxation）的过程就是通过最小化原不可行模型约束和变量的冲突值，求解变量和约束上下界的松弛量。用户可以根据可行化松弛定量计算的结果，相应地调整约束或变量范围，从而使得模型变得可行。

计算可行化松弛

COPT支持的编程接口提供计算可行化松弛的函数，同时也可以将可行化松弛模型写入文件，指定文件名后缀为 .relax (如： example.relax )，相关函数名称如表 42 所示：

表 42 不可行模型IIS计算功能的函数
编程接口	计算可行化松弛	将可行化松弛模型写入文件
C	`COPT_FeasRelax`	`COPT_WriteRelax`
C++	`Model::FeasRelax()`	`Model::WriteRelax()`
C#	`Model.FeasRelax()`	`Model.WriteRelax()`
Java	`Model.feasRelax()`	`Model.writeRelax()`
Python	`Model.feasRelax()`	`Model.writeRelax()`

COPT提供了两种方式计算可行化松弛，在除Python之外的编程接口中，用户可以通过对函数的不同参数进行赋值来实现：

简化版：对模型中全部变量和约束的可行化松弛，只需提供2个参数，以选择全部变量或全部约束
- ifRelaxVars ：是否对变量进行松弛，默认值为： True
- ifRelaxCons ：是否对约束进行松弛，默认值为： True
完整版：可以提供更多参数输入（指定变量/约束，设置变量/约束边界的惩罚因子）
- vars：待松弛变量
- cons：待松弛约束
- colLowPen：变量下界的惩罚因子
- colUppPen：变量上界的惩罚因子
- rowBndPen：约束边界的惩罚因子
- rowUppPen：若 cons 为双边约束，则表示约束上边界的惩罚因子
注意： 一般情况下，设置 rowUppPen 为 NULL 即可。

可行化松弛计算函数在不同编程接口中的调用方式和参数名称 略有不同 ，但是函数功能和参数含义是一致的，请进一步参考不同编程接口API参考手册的对应章节获取具体介绍：

C API：可行化松弛计算功能函数
C++ API：Model类
C# API：Model类
Java API：Model类
Python API：Model类

注意

针对简化版（Simplified）的可行化松弛计算方式，COPT的Python接口另外提供函数： Model.feasrelaxS(vrelax, crelax)，只需输入两个参数( vrelax 和 crelax )：
- vrelax ：是否对变量进行松弛，默认值为： True
- crelax ：是否对约束进行松弛，默认值为： True

可行化松弛的相关参数、属性和信息

优化参数

用户可以通过设置参数 "FeasRelaxMode" 的不同取值，选择计算可行化松弛的方法。不同编程接口的参数设置方法，请参考：参数章节。

FeasRelaxMode

整数参数。

计算可行化松弛的方法。

默认值 0

可选值

0: 最小化加权冲突值。

1: 计算最小化加权冲突下的原始模型最优可行化松弛。

2: 最小化冲突数目。

3: 计算最小化冲突数目下的原始模型最优可行化松弛。

4: 最小化加权平方冲突值。

5: 计算最小化加权平方冲突下的原始模型最优可行化松弛。

属性

COPT提供相关属性，用来描述可行化松弛的结果，如表 43 所示。不同编程接口的属性获取方法，请参考：属性章节。

表 43 可行化松弛结果相关属性总览
属性名	类型	属性含义
HasFeasRelaxSol	整数属性	是否存在可行化松弛结果。
FeasRelaxObj	浮点数属性	可行化松弛值。

信息

COPT提供以下信息，分别表示变量（或约束）下界的可行化松弛量，以及变量（或约束）上界的可行化松弛量。不同编程接口的信息获取方法，请参考：信息章节。

RelaxLB

浮点数信息。

变量（列）或者约束（行）下界的可行化松弛量。

RelaxUB

浮点数信息。

变量（列）或者约束（行）上界的可行化松弛量。

示例代码

用户可以在COPT安装包的 "examples" 文件夹下找到不同编程语言实现可行化松弛的示例代码，文件名为： "feasrelax_ex1.py" ，以COPT 7.0版本和Python语言为例，相应的文件路径为： "cop70/examples/python/feasrelax_ex1.py" 。